数字之魅------求二进制数中1的个数

今天看了编程之美的数字之魅章节，一个小小的“求二进制中1个数”的问题书中就给出了5中方法，着实让我开了眼界。现总结如下：

方法一：

估计大家最先想到的也是这种求余的思路

int Count(BYTE v)
{
    int num = 0;
    while(v)
    {
       if(v % 2 == 1)
       {
          num++;
       }
    }
   return num;
}
           

方法二：

使用位操作

int Count(BYTE v)
{
    int num = 0;
    while(v)
    {
        num += v & 0x01;  //取v的最低位，并求和
        v >> 1;
    }
    return num;
}
           

该方法的时间复杂度仍为O(log2 v)，log2 v 为二进制的位数

方法三：

int Count(BYTE v)
{
    int num = 0;
    while(v)
    {
        v &= (v - 1);    //将二进制形式的v从低位到高位中的1逐次消掉
        num++;
    }
    return num;
}
           

该方法的时间复杂度已经降到O(M),其中M是v中1的个数。

方法四使用的方法是使用switch分支，将数值作为分支，这样的话执行效率可能会低于上面的三种方法，因为分支语句具体要看字节的值，如果为0，那自然在第一个case就得到了答案，但是如果是255，则要正在最后一个case才能到到答案，即进行了255次比较操作！

该方法代码略。

方法五：查表法

该方法用了一个容纳256个整数的数组作为存储空间，该数组中存储的是对应下标的值中的1的个数，这样对于给定的整数v,可以用a[v]直接得到v中1的个数，时间复杂度仅为O(1),是典型的空间换时间。//a为数组名

该方法代码略。

本节后面的扩展练习2：

题目：给定两个整数(二进制形式表示)A和B，问把A变为B需要改变多少为(bit)?也就是说A和B的二进制表示中有多少位是不同的 ？

我的思路：将A和B进行异或操作，所得的结果中含有的1的个数(用上面的方法)就是A和B中不同的bit数，欢迎小伙伴们提出更好的思路。