编程之美---求二进制数中1的个数

转载自：http://blog.csdn.net/jiqiren007/article/details/6403133

问题描述：对于一个字节的无符号整型变量，求其二进制表示中1的个数。

解答：

看到这个问题，一个最直接的想法就是%2来统计1的个数了，实现如下：

int count(type n)

{

int count = 0;

while(n != 0)

{

if(n%2 == 1)

{

count++;

}

n = n/2;

}

return count;

}

解法二：

int count(type n)

{

int count = 0;

while(n != 0)

{

n = n & (n-1);

count++;

}

return count;

}

这个其实是很经典而且常见的一个解法

当然，对于题目要求的byte类型，可以使用书上推荐的查表法来解决，这样是使用空间来换时间的做法，但对于16位或者更多位的数来说，查表法基本是不可能的。

===============================华丽的分割线===============================

上面的几个解法是比较常见的答案，但深入研究发现，这个问题其实是经典的Hamming weight() ,其定义是 The Hamming weight of a  is the number of symbols that are different from the zero-symbol of the  used. 而且wiki上给出了一种神奇的高效率的解法，不得不佩服hamming！

其做法是采用这样的思想，类似归并的做法。对于相邻的两位，先计算这两位的1的个数(最大是2)，比如对于32位的数来说，分成 16组，每组计算的是相邻两位的1的个数和，并且将这个和用新得到的数的两位表示(2位可以最大表示4，所以可以存得下这个和，和此时最大为2)；然后对相邻四位进行操作，计算每两位两位的和（这样操作后其实是计算了原来32位数的相邻四位的1的个数）；这样依次类推，对于32位的数来说，只要操作到将其相邻16位的1的个数相加就可以得到其包含的1的个数了。

对于这种思想，wiki上给出了大概的解法：

int count(int num) //假设int是32位

{

int count = num;

int a = 0x55555555; //010101010101010101010101010101 //用于相邻的两位相加

int b = 0x33333333; //用于相邻的四位相加

int c = 0x0f0f0f0f;

int d = 0x00ff00ff;

int e = 0x0000ffff;

count = (count & a) + ((count>>1) & a);

count = (count & b) +((count>>2) & b);

count = (count & c) + ((count>>4) & c);

count = (count & d) + ((count>>8) & d);

count = (count & e) + ((count>>16) & e);

return count;

}

另外还有一个解法，MIT HAKMEM算法，没有去研究，囧

还有一个更巧妙的HAKMEM算法

   1:  int Count(unsigned x) { 
   2:     unsigned n;     
   3:       
   4:     n = (x >> 1) & 033333333333;     
   5:     x = x - n;    
   6:     n = (n >> 1) & 033333333333;    
   7:     x = x - n;     
   8:     x = (x + (x >> 3)) & 030707070707;    
   9:     x = modu(x, 63);   
   10:     return x;    
   11:  }  
首先是将二进制各位三个一组，求出每组中1的个数，然后相邻两组归并，得到六个一组的1的个数，最后很巧妙的用除63取余得到了结果。

因为2^6 = 64，也就是说 x_0 + x_1 * 64 + x_2 * 64 * 64 = x_0 + x_1 + x_2 (mod 63)，这里的等号表示同余。

这个程序只需要十条左右指令，而且不访存，速度很快。

由此可见，衡量一个算法实际效果不单要看复杂度，还要结合其他情况具体分析。

关于后面的两道扩展问题，问题一是问32位整型如何处理，这个上面已经讲了。

问题二是给定两个整数A和B，问A和B有多少位是不同的。

这个问题其实就是数1问题多了一个步骤，只要先算出A和B的异或结果，然后求这个值中1的个数就行了。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝华丽的分割线＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

问题扩展：

给定两个正整数Ａ和Ｂ，问把Ａ变成Ｂ需要改变多少位？也就是Ａ和Ｂ的二进制中有多少位是不同的？

解法：其他这个问题是ｈａｍｍｉｎｇ ｗｅｉｇｈｔ的扩展，先将Ａ和Ｂ进行异或操作（＾），那么就得到的这个数的hamming weight就是A变成B需要改变的位数。

参考资料：

http://blog.csdn.net/bvbook/archive/2008/04/15/2292823.aspx