Hacker's Delight笔记(3)-位计数

发布网友 发布时间：2024-11-05 00:06

我来回答

共1个回答

热心网友 时间：2024-11-05 00:10

: 非 (ASCII 00AC) ⨁: 异或 (ASCII 2A01) ≡：异或非，即异或再取非 (ASCII 2261) ≫: 有符号右移 (ASCII 226B) ≫U：无符号右移

1. 统计为1的位元数

考虑长度为32bit的整数，现在要统计bit为”1”的个数。这里我们可以利用”分而治之”的策略，将32bit分成两个16bit的部分分别统计。然后再将16bit分成两个8bit，直到粒度为2个bit的情况。

假设x为2bit数，那么x中的1的个数可以表示为(x & 1) + (x >> 1)。对于32bit的整数，第一步先同时对16组2bit数进行操作: x = (x & 0x5555 5555) + ((x >> 1) & 0x5555 5555)。然后，我们想办法再将16组2bit数加成一个数即可: x = (x & 0x3333 3333) + ((x >> 2) & 0x3333 3333)。相邻的2bit数加成4bit数 x = (x & 0x0F0F 0F0F) + ((x >> 4) & 0x0F0F 0F0F)。相邻的4bit数加成8bit数 x = (x & 0x00FF 00FF) + ((x >> 8) & 0x00FF 00FF)。相邻的8bit数加成16bit数 x = (x & 0x0000 FFFF) + ((x >> 16) & 0x0000 FFFF)。相邻的16bit数加成最后的32bit数

简化:

由于最后的结果最大值为32(0x0000 0020)，顶多也就使用了6个bit。所以上面的式子应该还可以继续精简。现在我们还是考虑2bit数0bAB = 2*A+B(A,B为1或0)。所以1的个数A+B = 2A＋B–A = 0bAB–(0bAB>>1)，所以上面第一个式子可以简化成:

x = x – ((x >> 1) & 0x5555 5555)

这里我们把4bit看成一组。假设经过上面的一步，我们从0bABCD得到了0bEFGH。从2bit为单位看，有0bEF = A+B, 0bGH = C+D，从4bit角度看，有0bEFGH = 4*(A+B)+C+D。所以, A+B+C+D=4*(A+B)+C+D-3*(A+B) = 0bEFGH – 3*(0bEFGH >> 2) , 所以第二个式子可以继续优化成:

x = x – 3*((x >> 2) & 0x3333 3333)

接下来的8bit的结果最大为8，最大占用4个字节。所以可以先加，再把多余的bit置零。

x = (x + (x >> 4)) & 0x0F0F 0F0F

由于最终结果顶多占用6bit，所以下面的式子也不用考虑bit相加的进位问题。

x = x + (x >> 8) x = x + (x >> 16)

只需要最后把不需要的bit置零，就得到最后的结果了。

x = x & 0x0000 003F

建表方法优化:

使用建立表格的方式虽然比较暴力，但是在很多地方往往有很好的优化效果。我们先把0~255的结果算出来建表:

table[256] = {0, 1, 1, …, 7, 8}

最后的结果为:table[x & 0xFF] + table[(x >> 8) & 0xFF] + table[(x >> 16) & 0xFF] + table[x >> 24]

2. 奇偶性

如果一个位串中的1的个数为奇数，称之为”奇位串”，否则称为”偶位串”。

我们这里依然主要用”分而治之”的方法，考虑2bit数0bAB，然后取异或A⨁B。0⨁0=0, 1⨁1=0, 1⨁0=1, 0⨁1=1。如果把0看作偶数，1看作奇数，那异或正好满足了奇偶的统计规律。0bAB ⨁ (0bAB >> 1)，这样我们就把奇偶的结果存放在了最低位。然后我们把2bit推广到4bit，直到32bit。下面是公式:

y = x ^ (x >> 1); y = y ^ (y >> 2); y = y ^ (y >> 4); y = y ^ (y >> 8); y = y ^ (y >> 16);

奇偶性的结果就在最低位。0代表偶数，1代表奇数。

3. 前导0计数

用二分法搜索计算前导0个数的算法:

如果使用建表的方法，可以用下面的语句替换上面的6~9行. table[256] = {0, 1, 2, 2, …, 8} return n + 7 – table[x >> 24]

4. 后缀0计数

用二分法搜索计算后缀0个数的算法:

如果后缀0的数目比较少，则这种循环的方式更快一些:

此外，还有一种并发执行度较高的代码: