位运算:1-bits的计数

看Matrix67的博客的时候知道了一本叫Hacker‘s Delight的书,大概是讲位运算的。有些操作用位运算真的很高效。以32位整数为例总结下学到的方法。

 

1)pop(x)种群计数(population count):记录整数x的二进制表示中1的个数

int pop(int a)

{

a=(a&0x55555555)+((a>>1)&0x55555555);//0101

a=(a&0x33333333)+((a>>2)&0x33333333);//0011

a=(a&0x0f0f0f0f)+((a>>4)&0x0f0f0f0f);//0000 1111

a=(a&0x00ff00ff)+((a>>8)&0xff00ff00);//0000 0000 1111 1111

a=(a&0x0000ffff)+((a>>16)&0xffff0000);

return a;

}

 

这个算法采用的是分治的思想,0x55555555其实就是8个0101位串,第一个语句后,a中的每两个bit位一组记录着原数中这两个相应位置上1的个数。例如四位串1110经过第一步后变为1001。后面的几个语句所作的就是把这些数都加起来。

当然你也可以用一个循环,求得a&(1<<i)的和不过这样确实不如以上的方法高效。

 

2)奇数还是偶数个1-bits(Parity)

那么如何确定a中的1是奇数个还是偶数个呢?当然pop(a)&1会给出答案,但还有更好的方法。

 

int Parity(int a)

{

a^=(a>>1);

a^=(a>>2);

a^=(a>>4);

a^=(a>>8);

a^=(a>>16);

return a&1;

}

语句a^=(a>>1)把a的每个bit都变成该位和它前面一位中1的奇偶数:有一个1就是1,两个或零个就是0。

同理a^=(a>>2)把a的每个bit都变成该位和它前面四位中1的奇偶数。

由于右移高位补0,这个结果对于中间的a也是成立的。例如a^=(a>>4)之后我们可以从此时a的值了解到原数a从各个位开始向左的8个位中1的个数。

这也是利用了异或运算和奇偶判断的一些关系:

奇+奇=偶          1^1=0

奇+偶=奇          1^0=1

偶+偶 =偶        0^0=0

偶+奇=奇          0^1=1

 

还有一个用到了乘法的算法,可能更简便一些,不过没有这个显得那么对称:

int Parity(int a)

{

a^=(a>>1);

a=(a^(a>>2))&0x11111111;

a*=0x11111111;

return (a>>28)&1;

}

这个需要在纸上演算一下就容易理解了。第二条语句后,a中只有第4*i+1(i=0,1,2,..,7)可能是1.如果4*i+1位是1说明4*i+1,4*i+2,4*i+3,4*i+4中有奇数个1.

关键是第三句,乘法是干什么用的呢?其实列下算式就明白了,以a=[00000001]_2为例:

a:      0000 0001

*       0001 0001

——————

0000 0001

+  0000 0001

——————

0001

它所做的正是把各个4*i+1位加起来。而且只有第29位(i=7)加了所有的1.所以最后要右移28位。

可以想到这样的类似方法也是对的:

int Parity(int a)

{

a=(a^(a>>1))&0x55555555;

a*=0x55555555;

return (a>>30)&1;

}

 

3)一个公式:

 

pop(a)=a-[a/2]-[a/4]-[a/8]-…[a/2^32].

[x]表示向下取整。

证明是把a展开成a1*2^32+a2*2^31+…a32的形式。

 

Advertisements