问题描述：
任意给定一个32位无符号整数n，求n的二进制表示中1的个数，比如n = 5（0101）时，返回2，n = 15（1111）时，返回4
这也是一道比较经典的题目了，相信不少人面试的时候可能遇到过这道题吧，下面介绍了几种方法来实现这道题
1.移位+统计
这种方法的运算次数与输入n最高位1的位置有关，最多循环32次。
int BitCount(unsigned int n) { unsigned int c =0 ; // 计数器 while (n >0) { if((n &1) ==1) // 当前位是1 ++c ; // 计数器加1 n >>=1 ; // 移位 } return c ; }
2.快速法
int BitCount2(unsigned int n) { unsigned int c =0 ; for (c =0; n; ++c) { n &= (n -1) ; // 清除最低位的1 } return c ; }
为什么n &= (n – 1)能清除最右边的1呢？因为从二进制的角度讲，n相当于在n - 1的最低位加上1。举个例子，8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）= 0（0000），清除了8最右边的1（其实就是最高位的1，因为8的二进制中只有一个1）。再比如7（0111）= 6（0110）+ 1（0001），所以7 & 6 = （0111）&（0110）= 6（0110），清除了7的二进制表示中最右边的1（也就是最低位的1）。
3.动态建表
由于表示在程序运行时动态创建的，所以速度上肯定会慢一些，把这个版本放在这里，有两个原因
（1）. 介绍填表的方法，因为这个方法的确很巧妙。
（2）. 类型转换，这里不能使用传统的强制转换，而是先取地址再转换成对应的指针类型。也是常用的类型转换方法。
int BitCount3(unsigned int n) { // 建表 unsigned char BitsSetTable256[256] = {0} ; // 初始化表 for (int i =0; i <256; i++) { BitsSetTable256[i] = (i &1) + BitsSetTable256[i /2]; } unsigned int c =0 ; // 查表 unsigned char* p = (unsigned char*) &n ; c = BitsSetTable256[p[0]] + BitsSetTable256[p[1]] + BitsSetTable256[p[2]] + BitsSetTable256[p[3]]; return c ; }
先说一下填表的原理，根据奇偶性来分析，对于任意一个正整数n
1.如果它是偶数，那么n的二进制中1的个数与n/2中1的个数是相同的，比如4和2的二进制中都有一个1，6和3的二进制中都有两个1。为啥？因为n是由n/2左移一位而来，而移位并不会增加1的个数。
2.如果n是奇数，那么n的二进制中1的个数是n/2中1的个数+1，比如7的二进制中有三个1，7/2 = 3的二进制中有两个1。为啥？因为当n是奇数时，n相当于n/2左移一位再加1。
再说一下查表的原理
对于任意一个32位无符号整数，将其分割为4部分，每部分8bit，对于这四个部分分别求出1的个数，再累加起来即可。而8bit对应2^8 = 256种01组合方式，这也是为什么表的大小为256的原因。
注意类型转换的时候，先取到n的地址，然后转换为unsigned char*，这样一个unsigned int（4 bytes）对应四个unsigned char（1 bytes），分别取出来计算即可。举个例子吧，以87654321（十六进制）为例，先写成二进制形式-8bit一组，共四组，以不同颜色区分，这四组中1的个数分别为4，4，3，2，所以一共是13个1，如下面所示。
10000111 01100101 01000011 00100001 = 4 + 4 + 3 + 2 = 13