今天在看《Redis 设计与实现》中「二进制位数组」一章,书中讲述 BITCOUNT 命令时提及了「计算汉明重量(Hamming Weight)」,「汉明重量」是一串符号中非零符号的个数。

二进制位统计的常见算法有遍历算法、查表算法,在 LeetCode 191. 位1的个数 一题中我也写过 相关题解。Redis 在实现 BITCOUNT 命令时则使用了查表和 variable-precision SWAR 两种算法,本文将主要介绍 variable-precision SWAR 算法的实现原理。

算法实现原理

以计算 32 位二进制的汉明重量为例。

// 计算 32 位二进制的汉明重量
uint32_t swar(uint32_t i)
{
// 步骤1
i = (i & 0x55555555) + ((i >> 1) & 0x55555555);

// 步骤2
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);

// 步骤3
i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);

// 步骤4
i = (i * (0x01010101) >> 24);

return i;
}

下面拆分步骤进行分析。

步骤一:(i & 0x55555555) + ((i >> 1) & 0x55555555)

0x55555555 的二进制表示为 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01

i & 0x55555555

i0x55555555 相与的结果偶数位全部置 0,奇数位与 i 保持一致。

i >> 1

i 右移 1 位,丢弃最右边的奇数位,因此 i 中原奇数位变为偶数位,原偶数位变为奇数位。

(i >> 1) & 0x55555555

i >> 1 的结果为 x,则 x & 0x55555555 的结果偶数位全部置 0,奇数位与 x 中奇数位保持一致。而 x 中的奇数位是 i 中的偶数位。

(i & 0x55555555) + ((i >> 1) & 0x55555555)

(i & 0x55555555) + ((i >> 1) & 0x55555555) 中,按每个二进制位为一组进行分组,各组的十进制表示就是该组的汉明重量。


步骤二:(i & 0x33333333) + ((i >> 2) & 0x33333333)

0x33333333 的二进制表示为 0011 0011 0011 0011 0011 0011 0011 0011

i & 0x33333333

i 中每 4 个二进制数为一组,每组中 2 个低位数字保持不变,高位数字置 0。

i >> 2

i 右移动 2 位,丢弃 2 个低位,因此原先一组中的 2 个高位变成低位,2 个低位被右移到右侧分组的高位中。

(i >> 2) & 0x33333333

i >> 2 结果为 xx 依旧被分为 4 个一组,每组中 2 个高位置 0,2 个低位保持不变。

(i & 0x33333333) + ((i >> 2) & 0x33333333)

(i & 0x33333333) + ((i >> 2) & 0x33333333) 中每 4 个二进制数被分为一组,各组的十进制表示就是该组的汉明重量。


步骤三:(i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);

0x0F0F0F0F 的二进制表示为 00001111 00001111 00001111 00001111。同上述步骤可知,步骤三 (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F) 将步骤二的结果按每八个二进制位为一组进行分组,各组的十进制表示就是该组的明汉重量。


步骤四:(i * (0x01010101) >> 24)

0x01010101 的二进制表示为 00000001 00000001 00000001 00000001

i * (0x01010101)

i 已经被分为八个二进制位为一组的分组,假设分组分别为 A、B、C、D(长度为 32 位,所以有 4 个分组),现在我们要求总结果,就要把这 4 个分组的值(即汉明重量)进行相加。

// 分组 A
i +
// 分组 B 左移 8 位
(i << 8) +
// 分组 C 左移 16 位
(i << 16) +
// 分组 D 左移 24 位
(i << 24)
= i * (1 + 1 << 8 + 1 << 16 + 1 << 24)
= i * 0x01010101

因此,i * (0x01010101) 表示:将 i 的汉明重量聚集在二进制的最高八位。

i * (0x01010101) >> 24

将最高八位右移成为最低八位,从而求出最终结果。

参考资料