[C++知识库]求一个整数的二进制表示中bit1的总数（C语言实现）

方法一：逐位判断法，这种方法最容易想到，效率也最差。时间复杂度与数据位宽（n = sizeof(unsigned int) * 8）有关O(n)。代码实现如下：

int fun1(unsigned int data)
{
    int cnt = 0;
    
    while(data) {
        if (data & 1) ++cnt;
        data >>= 1; 
    }

    return cnt;
}

方法二：循环消一法

????????以一个unsigned char型十进制整数232为例，它的二进制表示为：11101000，十进制232减去1等于231，十进制整数231的二进制表示为11100111。十进制232减去1转换成二进制减法，计算过程如下：

?? ?????????????????????????11101000
????????????????????????—? ? ? ? ? ? ? 1
????????????????????????——————
?? ?????????????????????????11100111

? ? ? ? 我们注意到，一个十进制整数减1的结果，如果用二进制表示的话，就是把该整数最后一位1后面的0全变成1，而最后一位1则变成0。利用上述特点，进一步将整数 N 与整数 （N -1）做“按位与”运算，即，N & (N-1)，则能够将整数N的二进制表示中的最后一个1消除掉。因此，把一个整数不断与它减1后的结果做“按位与”，则可以逐一消除该整数最后面的1，最终得到0，统计消除次数就可得到该整数中bit1的个数。时间复杂度与bit1的个数n 有关O(n)。代码实现如下：

int fun2(unsigned int data)
{
    int cnt = 0;

    while (data) {
        data &= (data - 1);
        ++cnt;
    }

    return cnt;
}

方法三：查表法

????????一个字节一共有256种状态，将每一个取值所对应的bit1的个数事先写在程序中（注意这些数值是有规律的），然后程序运行的时候，把整数的四个字节拆开逐字节查表并相加，这种可称为“查表法”。时间复杂度与入参数据类型含有的Byte数（n = sizeof(unsigned int)）有关O(n)。代码实现如下：

int fun3(unsigned int num) 
{
    int cnt = 0;
    unsigned char* p = (unsigned char*)(&num);
    static const unsigned char table[256] = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };

    while(p != (unsigned char*)(&num + 1)) {
        cnt += table[*p++];
    }

    return cnt;
}

方法四：分组统计法

????????我们注意到对于单个比特的二进制“数”而言，为0即表示bit1的个数是0，为1即表示bit1的个数是1（注意多比特二进制数值显然没有这个特点，比如一个字节有8个比特，当8个比特全为1时并不代表整数8，而代表255），所以：

（其中??表示x的第i个bit）

我们可以将所有bit两两一组分别相加计算，即：

并注意到每组最大值为2，而2个bit最大能表示的数为3。所以，我们可以将每组的和存入其原来的位置而不发生溢出。具体做法为：

1. 将x的值右移一位后与二进制数0101...01（即0x55555555）按位取&。（x本身值不变）
2. 将x的值与二进制数0101...01（即0x55555555）按位取&。（x本身值不变）
3. 将第一步和第二步的结果相加，并赋值回给x。

即：

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

这样我们就得到了一个整数，其第0~1位的值为0~1位含有1的数量，第2~3位的值为2~3位含有1的数量，……。

以此类推，我们可以在此基础上，将上一步的结果按4 bits一组分组，每组的左边一半和右边一遍相加，并将和写入原来的4bit的位置。再按8bits，16bits，32bits一组重复以上过程，即得到最后的结果。时间复杂度最低O(1)。

代码实现如下：

int fun4(unsigned int data)
{
    data = (data & 0x55555555) + ((data >> 1) & 0x55555555);
    data = (data & 0x33333333) + ((data >> 2) & 0x33333333);
    data = (data & 0x0F0F0F0F) + ((data >> 4) & 0x0F0F0F0F);
    data = (data & 0x00FF00FF) + ((data >> 8) & 0x00FF00FF);
    data = (data & 0x0000FFFF) + ((data >>16) & 0x0000FFFF);

    return data;
}

上述方法效率对比：

????????前置条件：将32K Byte内存区域全部初始化成0x5a，即，bit0的个数和bit1的个数相等，且都是0x20000个。

分组统计法最快，逐位判断法最慢，速度相差6.75了倍。

参考：二进制中1的个数（分治法） - 知乎

如有侵权请联系本人！