【剑指offer】面试题十：二进制中 1 的个数
题目：请实现一个函数，输入一个整数。输出该数二进制中 1 的个数。例如把 9 表示成二进制是 1001， 有 2 位是1.因此如果输入 9，该函数输出 2.
此题考查的是二进制和位运算的基本面试题之一。题目不是很难。
解法一：
基本思路
1、将该数字 i 和 1 做与运算，判断 i 的最低位是不是为 1。
2、接着把 1 左移一位得到 2，再和 i 做与运算就能判断 i 的次低位是不是 1 ···
3、重复 2 操作，将 1 反复左移，每次都能判断 i 的其中一位是不是 1 。
4、循环结束的条件为 当 1 左移 n 位的值 flag 大于该数字 i。
代码如下：
1 // numof1.c 2 #include "stdio.h" 3 #include "stdlib.h" 4 5 int numOf1(int n) 6 { 7 int count = 0; 8 int flag = 1; 9 10 while(flag <= n) 11 { 12 if(flag & n) 13 count ++; 14 flag = flag << 1; 15 } 16 return count; 17 } 18 19 int main(int argc, char const *argv[]) 20 { 21 int val = 0, i = 0; 22 23 while(i++ < 10) 24 { 25 val = rand() % 100; 26 printf("%3d's num of 1: %d ", val, numOf1(val)); 27 } 28 29 return 0; 30 }
循环的总次数为整数二进制的位数。 例如 86 用二进制表示为 1010110，那么该循环的总次数为 7次。
解法二：
整数中有几个 1 就只需要循环几次。例如上面的 1010110，共有 4 位为 1，我们就只需要循环四次就可以了。
具体介绍：
把一个整数（假设为 val）减去 1，再和原整数 val做与运算，会把 val的最右边一个 1 变成 0.那么一个整数的二进制表示中有多少个 1，就可以进行多少次这样的操作。
现在我们以 1010110（86）为例，详细介绍以上思路：
1、将 1010110（86） 减去 1 之后的二进制表示为 1010101（85），将1010101（85）与1010110（86）做与运算，1010110 & 1010101 = 1010100（1还剩3个）
2、将上述得到的结果 1010100 做与步骤1相同的操作，即 先减 1，得到 1010001， 再将1010100 和1010001 做与运算，1010100 & 1010001 = 1010000（1还剩2个）
3、再次重复步骤1，知道与运算的结果变为 0为止；
基于上面所述，我们可以写出如下代码：
1 // numOf1.c 2 #include "stdio.h" 3 #include "stdlib.h" 4 5 int numOf1(int n) 6 { 7 int count = 0; 8 while(n) 9 { 10 n = n & (n-1); 11 count ++; 12 } 13 return count; 14 } 15 16 int main(int argc, char const *argv[]) 17 { 18 int val = 0, i = 0; 19 20 while(i++ < 10) 21 { 22 val = rand() % 100; 23 printf("%3d's num of 1: %d ", val, numOf1(val)); 24 } 25 26 return 0; 27 }