求二进制数中1的个数

  很经典的一道题，但是觉得还是有必要总结一下。
 最简单也最直观的做法，不断右移，判断最右边是不是1：
 

int NumberOf1_1(int n)
{
    int count = 0;
    while (n)
    {
       if (n & 1) //判断最右边是不是1
           count++;

       n = n >> 1;
    }

    return count;
}

这个算法的时间复杂度是O(log₂n)，log₂n是二进制数的位数。但是这个算法有一个问题，例如输入0x80000000，右移一位时得到的数并不是
0x40000000，而是0xC0000000，这样如果一直做右移运算，最终这个数字会变成0xFFFFFFFF，陷入了死循环。所以这个算法只适合求无符号数。
  为了规避死循环的问题，可以换一种思路，将右移变为左移：

int NumberOf1_2(int n)
{
    int count = 0;
    unsigned int flag = 1;

    while (flag)
    {
       if (n & flag)
           count++;

       flag = flag << 1;
    }

    return count;
}

这样复杂度就取决于所求的数n的类型大小，对于32位的整数需要循环32次，如果对于较小的整数，复杂度是高于前一个算法的。
下面看一个最简单的算法，算法基于这样一个事实，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0：

int NumberOf1_3(int n)
{
   int count = 0;

   while (n)
   {
      ++count;
      n = (n - 1) & n;
   }

   return count;
}

这个整数有多少个1，就会进行多少次这样的操作，算法的复杂度取决于整数的二进制表示中1的个数。这应该是一种效率比较高的算法了，至此这个问题也应该是讨论结束了，但是《编程之美》上又提出了一个效率更高的做法，时间复杂度可以达到O(1)：

int countTable[256] =
{
  //数组内容略
};

int NumberOf1_4(BYTE v)
{
   return countTable[v];
}

BYTE型表示无符号8位整数，表示整数范围0~255，countTable数组直接求出0~255整数中“1“的个数，存放入表中，例如：“255”，则其“1”的个数为“8”，存储于countTable[255]中，直接调用就可得到值，这是典型的以空间换时间的算法，但有其适用范围，一旦n值较大，例如是int型，则有32位，如果一一求出每一个数的“1”的个数，则计算量太大，也会占用很大的空间。
下面再整理一下这个问题的推广应用：
1. 判断一个整数是不是2的整数次方：一个整数如果是2的整数次方，那么它的二进制表示中有且只有一位是1，而其他所有位都是0。于是把这个整数减1之后再和它自己做与运算，这个整数中唯一的1就会变成0，判定代码如下：
     if (n & n-1 == 0)
2. 输入两个整数m和n，计算需要改变m的二进制表示中的多少位才能得到n。可以分两步解决这个问题：第一步求这两个数的异或，第二步统计异或结果中1的位数：
  

int CalDifferInTwoNumber(int m, int n)
{
     int s = m^n;

     int bitNumber = NumberOf1_3(s);

     return bitNumber;
}

这个问题到这一步可以划一个句号了。

参考资料：
         《编程之美》 2.1
          《剑指Offer》 面试题10