BK算法（Brian Kernighan’s算法）

1
2
3
4
5
6
7
8
9
10
11
12
unsigned char countBit1InByte(unsigned char byte)
{
    unsigned char count = 0;

    while (byte) 
    {
        byte &= (byte - 1);
        count++;
    }
    return count;
}

此算法的思想是利用 n & (n-1) 可以将 n 的最右边的 1 置零的特性，通过迭代直到 n 变为 0，统计迭代次数即可。

它的运行时间与字节中bit1的位数成正比，而不是与字节的总位数成正比。因此计算效率不稳定，适用于bit1较少的场景。

位移法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>  

typedef unsigned char   BYTE;
typedef unsigned short  WORD;
typedef unsigned int    DWORD;

// 计算一个字节中bit1的个数
BYTE countBit1InByte(BYTE byte)
{
    // 第一步：将相邻的两位中的 1 位相加，结果保存在原来的位置
    byte = byte - ((byte >> 1) & 0x55);

    // 第二步：将相邻的 4 位中的 1 位相加，结果保存在原来的位置
    byte = (byte & 0x33) + ((byte >> 2) & 0x33);

    // 第三步：将相邻的 8 位中的 1 位相加，结果保存在原来的位置
    return (byte + (byte >> 4)) & 0x0F;
}

// 计算4个字节中bit1的个数
BYTE countBit1InInt(DWORD num)
{
    // 第一步：将相邻的两位中的 1 位相加，结果保存在原来的位置
    num = num - ((num >> 1) & 0x55555555);
    // 第二步：将相邻的 4 位中的 1 位相加，结果保存在原来的位置
    num = (num & 0x33333333) + ((num >> 2) & 0x33333333);
    // 第三步：将相邻的 8 位中的 1 位相加，结果保存在原来的位置
    num = (num + (num >> 4)) & 0x0F0F0F0F;
    // 第四步：将相邻的 16 位中的 1 位相加，结果保存在原来的位置
    num = num + (num >> 8);
    // 第五步：将相邻的 32 位中的 1 位相加，结果保存在原来的位置
    return (num + (num >> 16)) & 0x0000003F;
}

这是一个非常高效的方法，使用了位运算技巧来快速计算结果，而不需要使用循环或条件语句。

不过这个算法理解起来较为困难，下面开始解释每一步是如何工作的。

以 0x93 为例

  1. 第一步：byte = byte - ((byte >> 1) & 0x55);

    这一步的结果是将相邻的两位中的1位相加，并将结果保存在原来的位置。

    1
    2
    3
    4
    5
    10010011 (0x93) : original
    01000001 (0x41) : (byte >> 1) & 0x55
    01010010 (0x52) : byte - ((byte >> 1) & 0x55)
    ------
    01010010 (0x52) : result

  2. 第二步：byte = (byte & 0x33) + ((byte >> 2) & 0x33);

    这一步是计算前后4位的bit1个数，并将计算的结果保存到各自的位置。

    1
    2
    3
    4
    5
    6
    01010010 (0x52) : original
    00010000 (0x10) : (byte >> 2) & 0x33
    00010010 (0x12) : byte & 0x33
    00100010 (0x22) : (byte & 0x33) + ((byte >> 2) & 0x33)
    ------
    00100010 (0x22) : result

  3. 第三步：return (byte + (byte >> 4)) & 0x0F;

    将前后4位中bit1的个数相加，然后通过 & 0x0F 确保结果在4位以内。

    1
    2
    3
    4
    00100010 (0x22) : original
    00000100 (0x04) : (byte + (byte >> 4)) & 0x0F
    ------
    00000100 (0x04) : result

查表法

最高效的算法，只需要多占用 256 Bytes 的内存空间，就可换来效率的极大提升。

先用经典位计数算法或BK算法计算 0 - 255 这 256 个数字对应的 bit1 个数，并将计算的结构保存到 bit1Table 数组中。之后使用的时候就可以直接通过bit1Table 来获取各个数值对应的 bit1 个数了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>  

typedef unsigned char   BYTE;
typedef unsigned short  WORD;
typedef unsigned int    DWORD;

BYTE bit1Table[256];

// 计算一个字节中bit1的个数
BYTE countBit1InByte(BYTE byte)
{
    // 第一步：将相邻的两位中的 1 位相加，结果保存在原来的位置
    byte = byte - ((byte >> 1) & 0x55);

    // 第二步：将相邻的 4 位中的 1 位相加，结果保存在原来的位置
    byte = (byte & 0x33) + ((byte >> 2) & 0x33);

    // 第三步：将相邻的 8 位中的 1 位相加，结果保存在原来的位置
    return (byte + (byte >> 4)) & 0x0F;
}

// 初始化bit1个数表
void countBit1_InitTable(void)
{
    DWORD i;
    for (i = 0; i < 256; i++)
    {
        bit1Table[i] = countBit1InByte(i);
    }
}

// 查表法计算一个Byte中bit1的个数，需先调用 countBit1_InitTable 函数
BYTE countBit1InByte_LookupTable(BYTE byte)
{
    return bit1Table[byte];
}

void main(void)
{
    BYTE dat0 = 0x12;
    BYTE dat1 = 0x31;

    countBit1_InitTable();

    printf("dat0 bit1 = %d\n", countBit1InByte_LookupTable(dat0));
    printf("dat0 bit1 = %d\n", countBit1InByte_LookupTable(dat1));

}