统计整数二进制表示中1的个数(汉明重量)

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

第一次见到这个问题应该是icephone第一次例会的时候，问题虽然简单，但也值得深思。

后来查阅资料的时候才知道这个问题有个正式的名字叫，也被一些公司当做面试题。

下面通过几个不同阶段的算法，谈谈这个问题。

一、逐个数

刚刚接触这个问题的时候是上学期吧，大一，还刚接触软件工程，接触c语言，对一些问题的看法也比较单纯。

那时候，就想着纯粹的一个个数来着，声明一个计数变量，满足条件(尾数是1)，就加一，然后 / 2（二进制），直到该数为0为止。

当然，就可行性来说，这样的算法完全没有问题。简单，明了。

下面给出具体代码：

#include
//Hamming_weight算法1---逐个数
int Hamming_weight_1( int n )
{
    int count_ = 0; //声明计数变量

    while ( n != 0 )  //遍历
    {
        if( n%2 == 1 ) //满足尾数是1.
            count_++;
        n /= 2;        //除2，右移一位。(二进制)
    }
    return count_;
}

int main()
{
    int n;
    while ( scanf("%d", &n) != EOF )  //读入整数和打印1的个数
    {
        printf("%d \n", Hamming_weight_1( n ));
    }
    return 0;
}

上面的这种算法很常规，也很简单，就不多做说明。

因为今天的主角是位运算，所以相应的，给出位运算的版本，虽然比较简单，但是还是写出来，便于做比较。

#include
//Hamming_weight算法1---逐个数(位运算)
int Hamming_weight_1( int n )
{
    int count_ = 0; //声明计数变量

    while ( n != 0 )  //遍历
    {
        count_ += n & 1; //尾数按位与1
        n >>= 1;   // 右移一位
    }
    return count_;
}

int main()
{
    int n;
    while ( scanf("%d", &n) != EOF )  //读入整数和打印1的个数
    {
        printf("%d \n", Hamming_weight_1( n ));
    }
    return 0;
}

好了，现在分析下逐个数算法的性能。不难看出，对于任何一个整数n（对应的二进制数有位），它都要进行次判断。可以说，算法效率比较低，每一位都进行了判断。

当然，我们不能排斥效率低的算法，任何算法，没有绝对的优越，都是在比较中体现。

下面谈谈另外一种位运算，也比较易懂。

二、number&= number-1 -----只与二进制中1的位数相关的算法

逐个数的方法效率是比较低下的，因为它把每一位都考虑进去了，没有进行筛选，一个劲的蛮干。

现在，我们可以考虑每次找到从最低位开始遇到的第一个1，计数，再把它清零，清零的位运算操作是与一个零（任何数与零都等于零）。

但是在有1的这一位与零的操作要同时不影响未统计过的位数和已经统计过的位数，于是可以有这样一个操作number&= number-1。

这个操作对比当前操作位高的位没有影响，对低位则完全清零。

拿6（110）来做例子，

第一次 110&101=100，这次操作成功的把从低位起第一个1消掉了，同时计数器加1。

第二次100&011=000，同理又统计了高位的一个1，此时n已变为0，不需要再继续了，于是110中有2个1。

下面先看代码，一会再举例说明。

#include
//Hamming_weight算法二---只考虑1的位数
int Hamming_weight_2( int number )
{
    int count_ = 0; //声明计数变量

    while ( number != 0 )  //遍历
    {
        number &= number-1;
        count_ ++;
    }
    return count_;
}

int main()
{
    int n;
    while ( scanf("%d", &n) != EOF )  //读入整数和打印1的个数
    {
        printf("%d \n", Hamming_weight_2( n ));
    }
    return 0;
}

这里，关键是：number &=(number-1)，也是巧妙所在。

精髓就是：这个操作对比当前操作位高的位没有影响，对低位则完全清零。

［ 2. 判断一个数是否是2的方幂
n > 0 && ((n & (n - 1)) == 0 ) ］

看完代码，再举一例、

拿7（111）来做例子，

第一次 111&110=110，这次操作成功的把从低位起第一个1消掉了，同时计数器加1。

第二次110&101=100，同理又统计了高位的一个1，同时计数器加1。

第三次100&011=000，同理又统计了高位的一个1，同时计数器加1。

此时n已变为0，不需要再继续了，于是111中有3个1。

相信看完代码和例子不难理解了。

以我目前水平，我觉得这个算法已经很巧妙了。不过,,,看了wikipedia上解的问题，才知道什么叫大神...

三、wiki上高效解法。

先给代码,,

#include
//Hamming_weight
int Hamming_weight_3( int n )
{
    n = (n&0x55555555) + ((n>>1)&0x55555555);
    n = (n&0x33333333) + ((n>>2)&0x33333333);
    n = (n&0x0f0f0f0f) + ((n>>4)&0x0f0f0f0f);
    n = (n&0x00ff00ff) + ((n>>8)&0x00ff00ff);
    n = (n&0x0000ffff) + ((n>>16)&0x0000ffff);

    return n;
}

int main()
{
    int n;
    while ( scanf("%d", &n) != EOF )  //读入整数和打印1的个数
    {
        printf("%d \n", Hamming_weight_3( n ));
    }
    return 0;
}

说实在，以我个人的能力。

我看这个跟看天书一样，完全不懂。

下面通过学习过程，附带一些大牛的讲解，来解释下。

本段讲解来源:http://www.sandy-sp.com/blog/article.asp?id=11

说简单点，就是一个 错位分段相加，然后递归合并的过程 。

下面是细节分析：

首先先看看那些诡异的数字都有什么特点：
0x5555……这个换成二进制之后就是0101010101010101……
0x3333……这个换成二进制之后就是0011001100110011……
0x0f0f……...这个换成二进制之后就是0000111100001111……
看出来点什么了吗？
如果把这些二进制序列看作一个循环的周期序列的话，

那么第一个序列的周期是2，每个周期是01，第二个序列的周期是4，每个周期是0011，第三个的周期是8，每个是00001111……

这样的话，我们可以看看如果一个数和这些玩意相与之后的结果：

整个数按照上述的周期被分成了n段，每段里面的前半截都被清零，后半截保留了数据。不同在于这些数分段的长度是2倍增长的。于是我们可以姑且命名它们为“分段截取常数”。

这样，如果我们按照分段的思想，每个周期分成一段的话，你或许就可以感觉到这个分段是二分法的倒过来——类似二段合并一样的东西！


现在回头来看问题，我们要求的是1的个数。这就要有一个清点并相加的过程（查表法除外）。使用&运算和移位运算可以帮我们找到1，但是却无法计算1的个数，需要由加法来完成。最传统的逐位查找并相加，每次只加了1位，显然比较浪费，我们能否一次用加法来计算多次的位数呢？

再考虑问题，找到了1的位置，如何把这个位置变成数量。最简单的情况，一个2位的数，比如11，只要把它的第二位和第一位相加，不就得到了1的个数了吗？！所以对于2位的x，有x中1的个数=(x>>1)+(x&1)。是不是和上面的式子有点像？

再考虑稍复杂的，一个字节内的情况。
一个字节的x，显然不能用(x>>1)+(x&1)的方法来完成，但是我们受到了启发，如果把x分段相加呢？把x分成4个2位的段，然后相加，就会产生4个2位的数，每个都代表了x对应2位地方的1的个数。

本段讲解来源：http://www.cnblogs.com/kevinferry/archive/2011/03/03/2013962.html

所以，该解法的核心如下：

对于n位二进制数，最多有n个1，而n必定能由n位二进制数来表示，因此我们在求出某k位中1的个数后，可以将结果直接存储在这k位中，不需要额外的空间。
以4位二进制数abcd为例，最终结果是a+b+c+d，循环的话需要4步加法

那么我们让abcd相邻的两个数相加，也就是 a+b+c+d=[a+b]+[c+d]

[0 b 0 d]

[0 a 0 c]

------------

[e f] [ g h]

ef=a+b   gh=c+d

 而 0b0d=(abcd)&0101,0a0c=(abcd)>>1 &0101

[ef]  [gh]再相邻的两组相加

[00 ef]

    [gh]

----------

i j k l

ijkl=ef+gh  gh=(efgh)& 0011 ,ef=(efgh)>>2 & 0011

依次入次递推。需要log(N)次

下面通过具体的例子再说明一下。

例子一：（来源：http://www.sandy-sp.com/blog/article.asp?id=11）

例子，若求156中1的个数，156二进制是10011100
最终：

[1][0][0][1][1][1][0][0] //初始，每一位是一组
---
|0  0 |0  1 |0  1 |0  0|  //与01010101相与的结果，同时2个一组分组
+
|0  1 |0  0 |0  1 |0  0|  //右移一位后与01010101相与的结果
=
[0  1][0  1][1  0][0  0]  //相加完毕后，现在每2位是一组，每一组保存的都是最初在这2位的1的个数
----
|0  0  0  1 |0  0  0  0|  //与00110011相与的结果，4个一组分组
+
|0  0  0  1 |0  0  1  0|  //右移两位后与00110011相与的结果
=
[0  0  1  0][0  0  1  0] //相加完毕后，现在每4位是一组，并且每组保存的都是最初这4位的1的个数
----
|0  0  0  0  0  0  1  0|
+
|0  0  0  0  0  0  1  0|
=
[0  0  0  0  0  1  0  0] //最终合并为8位1组，保存的是整个数中1的个数，即4。

再举一个例子：（来源：http://www.cnblogs.com/xianghang123/archive/2011/08/24/2152408.html）

比如这个例子，143的二进制表示是10001111，这里只有8位，高位的0怎么进行与的位运算也是0，所以只考虑低位的运算，按照这个算法走一次

+---+---+---+---+---+---+---+---+
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |   <---143
+---+---+---+---+---+---+---+---+
|  0 1  |  0 0  |  1 0  |  1 0  |   <---第一次运算后
+-------+-------+-------+-------+
|    0 0 0 1    |    0 1 0 0    |   <---第二次运算后
+---------------+---------------+
|        0 0 0 0 0 1 0 1        |   <---第三次运算后，得数为5
+-------------------------------+

这里运用了分治的思想，先计算每对相邻的2位中有几个1，再计算每相邻的4位中有几个1，下来8位，16位，32位，因为2^5＝32，所以对于32位的机器，5条位运算语句就够了。

像这里第二行第一个格子中，01就表示前两位有1个1，00表示下来的两位中没有1，其实同理。再下来01+00=0001表示前四位中有1个1，同样的10+10=0100表示低四位中有4个1，最后一步0001+0100=00000101表示整个8位中有5个1。

再举一个例子：（来源：维基百科）

例如，要计算二进制数 A=0110110010111010 中 1 的个数，这些运算可以表示为：

符号	二进制	十进制	注释
A	0110110010111010		原始数据
B = A & 01 01 01 01 01 01 01 01	01 00 01 00 00 01 00 00	1,0,1,0,0,1,0,0	A 隔一位检验
C = (A >> 1) & 01 01 01 01 01 01 01 01	00 01 01 00 01 01 01 01	0,1,1,0,1,1,1,1	A 中剩余的数据位
D = B + C	01 01 10 00 01 10 01 01	1,1,2,0,1,2,1,1	A 中每个双位段中 1 的个数列表
E = D & 0011 0011 0011 0011	0001 0000 0010 0001	1,0,2,1	D 中数据隔一位检验
F = (D >> 2) & 0011 0011 0011 0011	0001 0010 0001 0001	1,2,1,1	D 中剩余数据的计算
G = E + F	0010 0010 0011 0010	2,2,3,2	A 中 4 位数据段中 1 的个数列表
H = G & 00001111 00001111	00000010 00000010	2,2	G 中数据隔一位检验
I = (G >> 4) & 00001111 00001111	00000010 00000011	2,3	G 中剩余数据的计算
J = H + I	00000100 00000101	4,5	A 中 8 位数据段中 1 的个数列表
K = J & 0000000011111111	0000000000000101	5	J 中隔一位检验
L = (J >> 8) & 0000000011111111	0000000000000100	4	J 中剩余数据的检验
M = K + L	0000000000001001	9	最终答案

最后，给出维基百科上面该问题的逐步优化过程..反正我是看不懂了。

做个标记，哪天有兴趣，有能力了再来瞅瞅

//types and constants used in the functions below

typedef unsigned __int64 uint64;  //assume this gives 64-bits
const uint64 m1  = 0x5555555555555555; //binary: 0101...
const uint64 m2  = 0x3333333333333333; //binary: 00110011..
const uint64 m4  = 0x0f0f0f0f0f0f0f0f; //binary:  4 zeros,  4 ones ...
const uint64 m8  = 0x00ff00ff00ff00ff; //binary:  8 zeros,  8 ones ...
const uint64 m16 = 0x0000ffff0000ffff; //binary: 16 zeros, 16 ones ...
const uint64 m32 = 0x00000000ffffffff; //binary: 32 zeros, 32 ones ...
const uint64 hff = 0xffffffffffffffff; //binary: all ones
const uint64 h01 = 0x0101010101010101; //the sum of 256 to the power of 0,1,2,3...

//This is a naive implementation, shown for comparison,
//and to help in understanding the better functions.
//It uses 24 arithmetic operations (shift, add, and).
int popcount_1(uint64 x) {
    x = (x & m1 ) + ((x >>  1) & m1 ); //put count of each  2 bits into those  2 bits
    x = (x & m2 ) + ((x >>  2) & m2 ); //put count of each  4 bits into those  4 bits
    x = (x & m4 ) + ((x >>  4) & m4 ); //put count of each  8 bits into those  8 bits
    x = (x & m8 ) + ((x >>  8) & m8 ); //put count of each 16 bits into those 16 bits
    x = (x & m16) + ((x >> 16) & m16); //put count of each 32 bits into those 32 bits
    x = (x & m32) + ((x >> 32) & m32); //put count of each 64 bits into those 64 bits
    return x;
}

//This uses fewer arithmetic operations than any other known
//implementation on machines with slow multiplication.
//It uses 17 arithmetic operations.
int popcount_2(uint64 x) {
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits
    x += x >>  8;  //put count of each 16 bits into their lowest 8 bits
    x += x >> 16;  //put count of each 32 bits into their lowest 8 bits
    x += x >> 32;  //put count of each 64 bits into their lowest 8 bits
    return x &0xff;
}

//This uses fewer arithmetic operations than any other known
//implementation on machines with fast multiplication.
//It uses 12 arithmetic operations, one of which is a multiply.
int popcount_3(uint64 x) {
    x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits
    x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits
    return (x * h01)>>56;  //returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}

在最坏的情况下，上面的实现是所有已知算法中表现最好的。但是，如果已知大多数数据位是 0 的话，那么还有更快的算法。这些更快的算法是基于这样一种事实即 X 与 X-1 相与得到的最低位永远是 0。例如：

Expression	Value
X	0 1 0 0 0 1 0 0 0 1 0 0 0 0
X-1	0 1 0 0 0 1 0 0 0 0 1 1 1 1
X & (X-1)	0 1 0 0 0 1 0 0 0 0 0 0 0 0

减 1 操作将最右边的符号从 0 变到 1，从 1 变到 0，与操作将会移除最右端的 1。如果最初 X 有 N 个 1，那么经过 N 次这样的迭代运算，X 将减到 0。下面的算法就是根据这个原理实现的。

//This is better when most bits in x are 0
//It uses 3 arithmetic operations and one comparison/branch per "1" bit in x.
int popcount_4(uint64 x) {
    uint64 count;
    for (count=0; x; count++)
        x &= x-1;
    return count;
}

//This is better if most bits in x are 0.
//It uses 2 arithmetic operations and one comparison/branch  per "1" bit in x.
//It is the same as the previous function, but with the loop unrolled.
#define f(y) if ((x &= x-1) == 0) return y;
int popcount_5(uint64 x) {
    if (x == 0) return 0;
    f( 1) f( 2) f( 3) f( 4) f( 5) f( 6) f( 7) f( 8)
    f( 9) f(10) f(11) f(12) f(13) f(14) f(15) f(16)
    f(17) f(18) f(19) f(20) f(21) f(22) f(23) f(24)
    f(25) f(26) f(27) f(28) f(29) f(30) f(31) f(32)
    f(33) f(34) f(35) f(36) f(37) f(38) f(39) f(40)
    f(41) f(42) f(43) f(44) f(45) f(46) f(47) f(48)
    f(49) f(50) f(51) f(52) f(53) f(54) f(55) f(56)
    f(57) f(58) f(59) f(60) f(61) f(62) f(63)
    return 64;
}

//Use this instead if most bits in x are 1 instead of 0
#define f(y) if ((x |= x+1) == hff) return 64-y;