今天在看《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

i 和 0x55555555 相与的结果偶数位全部置 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 结果为 x，x 依旧被分为 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

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

参考资料