Redis二进制位数组-Hamming Weight算法

BITCOUNT命令计算二进制位数组的一个步骤,是利用variable-precision SWAR算法来实现的,即计算Hamming Weight(简写为HW)的值。

https://www.cnblogs.com/NaLanZiYi-LinEr/p/11876246.html

{{{code

unit32_t swar(unit32_t i) {

//步骤1 每两个二进制位为一组进行分组,各组的十进制表示就是该组的HW

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

//步骤2 每四个二进制位为一组进行分组,各组的十进制表示就是该组的HW

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

//步骤3 每八个二进制位为一组进行分组,各组的十进制表示就是该组的HW

i = (i & 0x0F0F0F0F) + ((i >> 4) & 0x0F0F0F0F);

//步骤4 i*0x01010101语句计算出HW并记录在二进制位的高八位,>> 24通过右移运算,将HW移动到最低八位,就是最终的HW

i = (i*0x01010101) >> 24;

return i;

}

/}}}

 

Leave a Reply

Your email address will not be published. Required fields are marked *