好手给解释解释这个算法

2012-08-01

高手给解释解释这个算法这是一个求一个32位无符号整型二进制形式的1的个数C/C++ codeint Count(unsigned x

高手给解释解释这个算法
这是一个求一个32位无符号整型二进制形式的1的个数

C/C++ code

int Count(unsigned x) {   x = x - ((x >> 1) & 0x55555555);    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);    x = (x + (x >> 4)) & 0x0F0F0F0F;    x = x + (x >> 8);    x = x + (x >> 16);    return x & 0x0000003F;    } 这里用的是二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/bvbook/archive/2008/04/15/2292823.aspx

[解决办法]
我去富士通面试面试官人很好

就问了我这样的一个算法
[解决办法]
看一个具体的数值比较好说清楚。
只看8位，懂了这个，32位的道理是一样的。
以0xc6为例。写成二进制数就是
11000110b
我们把两位看成一个单元，可以看成4个单元
11 00 01 10
把各个单元的两位数相加，结果放回单元中
1+1 = 10
0+0 = 00
0+1 = 01
1+0 = 01
结果：10 00 01 01
每两位的值正好是原来每两位1的个数。
然后每4位一个单元
1000 0101
两位，两位的相加
10 + 00 = 0010
01 + 01 = 0010
结果：0010 0010
最后整个为一个单元，4位4位的相加
0010 + 0010 = 0100
结果就是1的个数4。

上面的算法就是这样做的，下面就2位为一个单元的情况解释一下，其它情况是一样的。
0x5的二进制形式是0101b，0x55 二进制形式是：01010101b
所以x & 0x55是保留1,3,5,7位，2，4，6，8位置0。
而(x>>1) & 0x55是把2,4,6,8位移到1,3,5,7位。
(x & 0x55) + ((x>>1) & 0x55)就可以把1和2位，3和4位，...7和8位相加了。
但在算法中用的是x - ((x>>1) & 0x55)，这是因为
x - ((x>>1) & 0x55) =
(x & 0x55) + (x & 0x55 << 1) - ((x>>1) & 0x55) =
(x & 0x55) + ((x & 0x55 << 1) >> 1)*2 - ((x>>1) & 0x55) =
(x & 0x55) + ((x & 0x55 << 1) >> 1) + ((x & 0x55 << 1) >> 1) - ((x>>1) & 0x55) =
(x & 0x55) + ((x >> 1) & 0x55) + ((x >> 1) & 0x55) - ((x>>1) & 0x55) =
(x & 0x55) + ((x >> 1) & 0x55)
结果相同，但x - ((x>>1) & 0x55)比(x & 0x55) + ((x>>1) & 0x55)少一次逐位与运算。
[解决办法]
补充一点：

C/C++ code

x = (x + (x >> 4)) & 0x0F0F0F0F;    x = x + (x >> 8);    x = x + (x >> 16);
[解决办法]
小妹不是高手，冒充一次高手，随便推了下：
为了好说明，我把这个32位的数设为：0111 1111 1111 1111 1111 1111 1111 1111
下面是我的推导的过程：
0111 1111 1111 1111 1111 1111 1111 1111->初始状态
0011 1111 1111 1111 1111 1111 1111 1111->x>>1
0101 0101 0101 0101 0101 0101 0101 0101->0x55555555
0001 0101 0101 0101 0101 0101 0101 0101->(x >> 1) & 0x55555555

0111 1111 1111 1111 1111 1111 1111 1111
0001 0101 0101 0101 0101 0101 0101 0101->(x >> 1) & 0x55555555
0110 1010 1010 1010 1010 1010 1010 1010->x - ((x >> 1) & 0x55555555);


0110 1010 1010 1010 1010 1010 1010 1010
0011 0011 0011 0011 0011 0011 0011 0011->0x33333333
0010 0010 0010 0010 0010 0010 0010 0010->(x & 0x33333333)

0110 1010 1010 1010 1010 1010 1010 1010
0001 1010 1010 1010 1010 1010 1010 1010->x>>2
0011 0011 0011 0011 0011 0011 0011 0011->0x33333333
0001 0010 0010 0010 0010 0010 0010 0010->((x >> 2) & 0x33333333);   

0010 0010 0010 0010 0010 0010 0010 0010->(x & 0x33333333)
0001 0010 0010 0010 0010 0010 0010 0010->((x >> 2) & 0x33333333);   
0011 0100 0100 0100 0100 0100 0100 0100->(x & 0x33333333) + ((x >> 2) & 0x33333333);

0011 0100 0100 0100 0100 0100 0100 0100  
0000 0011 0100 0100 0100 0100 0100 0100->x>>4

0011 0100 0100 0100 0100 0100 0100 0100
0000 0011 0100 0100 0100 0100 0100 0100->x>>4
0011 0111 1000 1000 1000 1000 1000 1000->(x + (x >> 4)) 
 

0011 0111 1000 1000 1000 1000 1000 1000->(x + (x >> 4))
0000 1111 0000 1111 0000 1111 0000 1111->0x0F0F0F0F
0000 0111 0000 1000 0000 1000 0000 1000->(x + (x >> 4)) & 0x0F0F0F0F;

0000 0111 0000 1000 0000 1000 0000 1000->(x + (x >> 4)) & 0x0F0F0F0F;
0000 0000 0000 0111 0000 1000 0000 1000->(x >> 8);

0000 0111 0000 1000 0000 1000 0000 1000  
0000 0000 0000 0111 0000 1000 0000 1000->(x >> 8);
0000 0111 0000 1111 0001 0000 0001 0000-> x + (x >> 8);

0000 0111 0000 1111 0001 0000 0001 0000
0000 0000 0000 0000 0000 0111 0000 1111->(x >> 16);   

0000 0000 0000 0000 0000 0111 0000 1111->(x >> 16);
0000 0111 0000 1111 0001 0000 0001 0000
0000 0111 0000 1111 0001 0111 0001 1111->x + (x >> 16);  

0000 0111 0000 1111 0001 0111 0001 1111
0000 0000 0000 0000 0000 0000 0011 1111->0x0000003F
0000 0000 0000 0000 0000 0000 0001 1111-> x & 0x0000003F最后的结果，十进制为31，正确
[解决办法]
探讨
看一个具体的数值比较好说清楚。
只看8位，懂了这个，32位的道理是一样的。
以0xc6为例。写成二进制数就是
11000110b
我们把两位看成一个单元，可以看成4个单元
11 00 01 10
把各个单元的两位数相加，结果放回单元中
1+1 = 10
0+0 = 00
0+1 = 01
1+0 = 01
结果：10 00 01 01
每两位的值正好是原来每两位1的个数。
……

[解决办法]
不是很明白
[解决办法]
探讨
看一个具体的数值比较好说清楚。
只看8位，懂了这个，32位的道理是一样的。
以0xc6为例。写成二进制数就是
11000110b
我们把两位看成一个单元，可以看成4个单元
11 00 01 10
把各个单元的两位数相加，结果放回单元中
1+1 = 10
0+0 = 00
0+1 = 01
1+0 = 01
结果：10 00 01 01
每两位的值正好是原来每两位1的个数。
……

[解决办法]
C/C++ codeint count = 0;while(x){    ++count;    x = x & (x - 1);}
[解决办法]
探讨
看一个具体的数值比较好说清楚。
只看8位，懂了这个，32位的道理是一样的。
以0xc6为例。写成二进制数就是
11000110b
我们把两位看成一个单元，可以看成4个单元
11 00 01 10
把各个单元的两位数相加，结果放回单元中
1+1 = 10
0+0 = 00
0+1 = 01
1+0 = 01
结果：10 00 01 01
每两位的值正好是原来每两位1的个数。
……

[解决办法]
C/C++ codeint Count(unsigned x) {   x = x - ((x >> 1) & 0x55555555);    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);    x = (x + (x >> 4)) & 0x0F0F0F0F;    x = x + (x >> 8);    x = x + (x >> 16);    return x & 0x0000003F;    }

热点排行