题目
请实现一个函数，输入一个整数，输出该二进制表示中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++; // 个数加1
flag = 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》
