variable-precision SWAR algorithm

简介：这是一个计算一个数中有多少个二进制1的方法

int swar(uint32_t i)
{
    // (A)
    i = ( i & 0x55555555) + ((i >> 1) & 0x55555555);

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

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

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

    return i;
}

算法分析

0x55555555 二进制 01010101 01010101 01010101 01010101

i & 0x55555555 表示 偶数二进制位 是否位1，并记录到 对应二进制位上，二进制位1则 对应的结果位1，否则为0

(i>>1) & 0x55555555 表示奇数二进制为是否为1，并记录到偶数位位上

两者相加，则用两个二进制位来表示 i 的每两个二进制数1的个数

同理 i & 0x33333333 + ((i >> 2) & 0x33333333) ( 00110011 00110011 00110011 00110011 ) 用4个二进制位表示 i上4位二进制 1的个数

i & 0x0F0F0F0F + ((i >> 4) & 0x0F0F0F0F) ( 00001111 00001111 00001111 00001111 ) 用8个二进制位表示 i上8位二进制 1的个数

i * 0x01010101 表示

y3  y2  y1  y0
                     x     1    1    1   1
---------------------------------------------------
                         y3  y2  y1  y0
                   y3  y2  y1  y0
             y3  y2  y1  y0
       y3  y2  y1  y0

由上图可知 第4个 8位表示 y0 + y1 + y2 + y3 再右移24位，则是i的1的个数