数目字之魅(一) 关于“出现数字1”
节选自编程之美。注意这里部分只给出算法的思想和伪代码。
如果仔细想来，其实编程的过程就是和数字打交道的过程，所以对bit很熟练的操作，应该是程序员需要掌握的一项基本技能。
下面开始第一个问题：
1. 统计一个32位无符号整数中，1出现的个数。
其实这道题是一个比较老的题目了，网上有好多解法，我自己在面试的时候也被问过这个问题。但是当时候给出的算法是o(n)的，注意这里的n是数字的位数。
解法一：算法的思想是：每次测试最后的一位，测试的方法是n和二进制的01进行相与，如果是1那么就加一，然后左移1位。网上称这种方法为普通法。
下面是伪代码。
//o(n)的移位操作对应的伪代码 count = 0; while n > 0 if ((n &0x01) == 1) count ++; n >>=1; retuen count;
解法二：时间复杂度为 o(k) 注意这里的k是n中1出现的次数，即算法的复杂度只和1出现的次数有关，虽然和o(n)的算法在时间复杂度在本质上相同，但是还是有很大的提高。
网上称这种方法为快速法。这种算法的关键是; 怎么每次找到1，然后再将它去除。
算法的思想是：因为 n = (n-1) + 1; 所以如果每次将n 和 n-1 进行“与”的话，那么就可以去掉n对应二进制最右边的1，然后将"与"值继续与比它小一的数进行重复操作，直至n为0；伪代码如下：
//o(k)的移位操作 count = -1; while n > 0 n &=(n-1); count +=1; return count;
其实上面是我们比较容易想到的方法，尤其是第一种，如果用辗转相除的话也可以实现，但是没有移位快。
这时候我的面试官为我有没有o(1)的算法，当时我就懵了，最后他给我提示用空间替换时间，我最后想到了用hash表，key为每0-2^32-1的每一个值，value为事先算好的对应的“1” 的个数，当然直接用数组来实现了。但是最后想想没敢说，这个空间的代价太大了，因为2^32大约是4G的内存，知道后来我在网上看到类似的但是跟巧妙的算法：
解法三：o(1) 的时间复杂度+ o(256)的空间复杂度；网上称这种方法为建表法；
算法思想是： 提前算出任意8bit整数对应的1出现的次数，然后放到一个表中。然后循环取n的后8位，进行hash然后将结果进行相加，下面是用c写的代码;
int BitCount3(unsigned int n)
{
unsigned int table[256] =
{
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 table[n &0xff] +
table[(n >>8) &0xff] +
table[(n >>16) &0xff] +
table[(n >>24) &0xff] ;
}暂且不去考虑你是否有条件得到table[256]，如果你得不到需要自己建怎么办，那么下面这种方法就是它的延伸，网上称为动态建表法：
解法四：这个算法主要实现了动态的建表，其中建表的思想是，这个很关键，请读者自己体会：
对于n 如果 n是偶数，那么n和n/2中含有1的个数是一样的，因为n是n/2左移1位来的，而左移最后是补0的，例如6 (0110) 和3 (0011) 个数是一样的。而如果n是奇数的话，
那么n = n/2 + 1 ; 所以n中1出现的次数是n/2出现的次数加1.
所以就有;
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 ;
}对于这个解法还有一个解释就是，这里用char型地址来分四次存储int型地址，达到每次存取8Bit的目的。
总结：对于上面四中解法，熟练掌握即可。3,4两种用空间换时间不一定比1,2好，但这种思想要学会应用。
2. 如何计算一个整数A和整数B的二进制表示中有多少位数不一样，换一种说法就是整数A如果变为整数B需要变换多少位？
其实，这个题目是1的延伸，如果对1理解的很清楚了，那么借助位运算可以很快的的得出算法：
先将A和B进行异或运算(c语言中是 ^) , 不同位的话异或会得出1，所以对异或的值选择1中的某个算法进行运算就可以了：
代码如下：
int get_diff(unsigned int A, unsigned int B)
{
unsigned int diff = A ^ B;
return BitCount3(diff);
}下面再看一个和“1的数目”有关的题目：