剑指offer|剑指offer - 二进制中1的个数剑指offer-二进制中1的个数

题目请实现一个函数，输入一个整数，输出该二进制表示中1的个数。例如：把9表示成二进制是1001，有2位1。因此，如果输入9，则该函数输出2
思路1 要判断二进制中1的个数，那么就需要一位一位的判断是否是1。

最直观的想法就是判断整数二进制表示中的最右边是不是1，接着把输入的整数右移一位，此时原来处于从右边数起的第二位被移动最右边了，再判断是不是1，这样每次移动一位，直到整数变成0为止

算法实现

int NumberOf1_Solution1(int n) { int count = 0; while (n) { if (n & 1) count++; n = n >> 1; // 右移一位 } return count; }

上面代码看似正确，对于正整数，0都OK，但是如果我们输入负整数的话，那么程序就会陷入死循环。因为负数的最高位是1，移位之后仍然要保证是负数，最后会变成0xFFFFFFFF，二进制为1111 1111 1111 1111 1111 1111 1111 1111从而变成死循环
注意：虽然右移位和除2是等价的，但是执行的效率不一样，位移操作比除法效率高

为了避免上述问题，我们可以设定一个标志位flag，让标志位flag与整数n进行与运算并移动

算法实现

int NumberOf1_Solution1(int n) { int count = 0; unsigned int flag = 1; // 标志位 while (flag) { if (n & flag) // 当前位置是否是1 count++; // 个数加1flag = flag << 1; // 移动标志位 }return count; }

上面代码简单来说就是把n和1做与运算，判断n的最低位是不是1。接着把1左移一位得到2，再和n做与运算，就能判断n的次低位是不是1，这样反复左移，每次都能判断n的其中一位是不是1。
循环的次数等于整数二进制的位数，32位的整数需要循环32次。
思路2 思路1进行优化，整数中有几个1就只需要循环几次

即把一个整数减去1，再和原整数做与运算，会把该整数最右边的1变成0，那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。

举个例子
二进制数1100，减去1后，第二位变成0，它后面的两位0变成1，而前面的1保持不变，因此得到的结果是1011，然后与1100进行与算法，结果为1000
再次循环，将1000减去1，那么为0111，然后与1000进行与运算，结果为0，退出循环。
所以1100中二进制1的个数为2
算法实现

int NumberOf1_Solution2(int n) { int count = 0; while (n) { ++count; n = (n - 1) & n; } return count; }

思路3 静态查表法
把0~255这256个数的结果全部存储在数组中，n直接作为下标，countTable[n]即为结果。典型的用空间换时间。

int NumberOf1_Solution3(int val) { int countTable[] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8}; return countTable[val]; }

更多有趣的解法可以参考这里
参考 【剑指offer|剑指offer - 二进制中1的个数】《剑指offer》