计算32位无符号数字的二进制内包含1的个数

计算32位无符号数字的二进制内包含1的个数

在老刘的知识星球上看到一道有意思的题目,如下:

int HW(unsigned int n){
    n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);
    n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2);
    n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);
    n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);
    n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);
    return n;
}

提问者提问这个算法是干什么的,评论里面有人给出了答案——判断无符号数二进制写法中有几个1。题目这个算法写得有点悬,拿来分析下,得出下面笔记。

某32位无符号整数n,用二进制写法为:n = xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx ,每个x 表示0 或者 1。
把这个xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx 每位拆开来写,假定为这样:X0,X1,X2……,X30,X31。
计算其1 的个数,也就是把每个Xk 加起来即可。
count_of_one(n) = X0+X1+X2……+X30+X31
=(X0+X1)+(X2+X3)……+(X30+X31)

由于X0,X1 要么是0 要么是1,所以X0+X1之和 结果小于2(使用二进制写法是10),也就是使用两个bit 就可以保存了。
假设一个数r 是两位bit大小的数字,那么它的二进制1的个数和则是:
(r&0x01) + ((r&0x02)>>1)
如果0x01 和0x02 使用二进制的写法,那么这个数字也就是:
(r&01) + ((r&10)>>1) 写法(1)

这里我们把n的每两个bit 看出一个数字,计算每两个bit 的1个数,存放在原来位置
也就是把X0+X1 的结果,存储在原来数据n 的内存上的bit0,bit1(作为一个内存整体,下称bit[0,1])上;
把 X2+X3 的结果,存储在原来数据n 的内存的bit[2,3]上;
把 X4+X5 的结果,存储在原来数据n 的内存的bit[4,5]上;
……
把 X30+X31 的结果,存储在原来数据n 的内存上的bit[30,31]上;

按照写法(1)的方式,就是这样了:
n = (n & 01010101 01010101 01010101 01010101) + ((n & 10101010 10101010 10101010 10101010) >> 1)

二进制数字 01010101 01010101 01010101 01010101 的十六进制写法 0x55555555,
二进制数字 10101010 10101010 10101010 10101010 的十六进制写法 0xaaaaaaaa,
采用十六进制的写法,则是:
n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);

到这里可以看到,(X0+X1),(X2+X3)……,(X30+X31)的数值分别存储在n的 bit[0,1],bit[1,2]……bit[30,31]了。
我们只需要把bit[0,1] + bit[2,3]+ …… + bit[30,31] 即可,
也就是(bit[0,1] + bit[2,3])+ (bit[4,5] + bit[6,7])+…… + (bit[28,329] + bit[30,31])

到此,我们将bit[0,1,2,3]看成一个数字r,把bit[0,1] + bit[2,3] 结果存储在bit[0,1,2,3] 上,采用二进制的写法就是
r = (r & 0011) + ((r & 1100)>> 2)
同样,n的每4位内的每2位做相同的操作,那么就是:
n = (n & 00110011 00110011 00110011 00110011) + ((n & 11001100 11001100 11001100 11001100) >> 2)
也就是十六进制的写法:
n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2 );

到这,每4个bit 的1 相加,结果存储在了n 的每4个bit 里面了。
同理按照上面的方法处理每8个bit内的每4bit,也就是:
n = (n & 00001111 00001111 00001111 00001111) + ((n & 11110000 11110000 11110000 11110000) >> 4)
也就是:
n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);

再重复上面的类似步骤处理每16bit 内的8bit
n = (n & 00000000 11111111 00000000 11111111) + ((n & 11111111 00000000 11111111 00000000) >> 8)
也就是:
n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);

继续处理32bit (也就是整体)内的16bit
n = (n & 00000000 00000000 11111111 11111111) + ((n & 11111111 11111111 00000000 00000000 >> 16)
也就是:

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

整合上面的结果,算法就是这样了:
n = (n & 0x55555555) + ((n & 0xaaaaaaaa) >> 1);
n = (n & 0x33333333) + ((n & 0xcccccccc) >> 2);
n = (n & 0x0f0f0f0f) + ((n & 0xf0f0f0f0) >> 4);
n = (n & 0x00ff00ff) + ((n & 0xff00ff00) >> 8);
n = (n & 0x0000ffff) + ((n & 0xffff0000) >> 16);

综上,思路就是,每相邻两个数值,归并起来,不断重复一直到合成一个。

图解来看就比较清楚了:

计算二进制中的1个数

到最后,x[0,1,……31]存储的就是结果了。

(全文完)

(欢迎转载本站文章,但请注明作者和出处 云域 – Yuccn

发表评论

电子邮件地址不会被公开。 必填项已用*标注