Redis 中的 variable-precision SWAR 算法
今天在看《Redis 设计与实现》中「二进制位数组」一章,书中讲述 BITCOUNT
命令时提及了「计算汉明重量(Hamming Weight)」,「汉明重量」是一串符号中非零符号的个数。
二进制位统计的常见算法有遍历算法、查表算法,在 LeetCode 191. 位1的个数 一题中我也写过 相关题解。Redis 在实现 BITCOUNT
命令时则使用了查表和 variable-precision SWAR 两种算法,本文将主要介绍 variable-precision SWAR 算法的实现原理。
算法实现原理
以计算 32 位二进制的汉明重量为例。
// 计算 32 位二进制的汉明重量 |
下面拆分步骤进行分析。
步骤一:(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 * (0x01010101)
表示:将 i
的汉明重量聚集在二进制的最高八位。
i * (0x01010101) >> 24
将最高八位右移成为最低八位,从而求出最终结果。
参考资料
- 本文链接:http://jalan.space/2020/05/05/2020/variable-percision-swar/
- 版权声明:本博客所有文章除特别声明外,均采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。
分享