(转)求整数中比特为1的二进制位数

好几次在CSDN上看到别人讨论如何求出一个整数的二进制表示中状态为1的比特位数。今天写了个程序把从网上看来的加上自己想出来的共有5种方法测试了一下，觉得好玩，就写了这篇博客。

首先简单介绍一下这五种方法。

第一种：最简单的，通过移位操作逐位测试并计数，不妨称为“逐位测试法”；

第二种：注意到对于“单比特二进制”而言，其状态与数值“相同”。即对于单个比特的“数”而言，为0即表示数值0，“全部为1”即表示数值1（注意多比特数值显然没有这个特点，比如一个字节有8个比特，当8个比特全为1时并不代表整数8，而代表255）。利用这一特点，从单个比特开始，以相邻的一位、两位、四位、八位和十六位为分组，一组一组地相加并逐步累计，最终得出结果；不妨称为“分组统计法”；

第三种：注意到一个整数减1的会把最后一位1变成0，而其后的0全变成1，利用这一特点，把一个数不断与它减1后的结果做“按位与”，直到它变成0，那么循环的次数便是其状态为1的比特位数。不妨称之为“循环减一相与法”；

第四种：考虚到多数处理器都提供“找到第一个为1的比特位”这种指令，在我的PC上直接调用X86处理器的BSF或BSR指令，每次直接找到第一个不为0的位并消掉，直到该数变成0，那么循环的次数即为状态为1的比特位数。这种不妨称为“汇编嵌入法”；

第五种，一个字节一共有256种状态，将每一个取值所对应的0比特位数的事先写在程序中（注意这些数值是有规律的），也耗不了太多内存，然后程序运行的时候，把整数的四个字节拆开逐字节查表并相加，这种可称为“查表法”。

 

以下是程序。程序中对应以上五种方法的函数分别命名为f1到f5。另外还有三个函数，correctness_test通过几个简单而又特殊的取值测试各个函数的正确性，相当于一个小单元测试；performance_test则分别将这5个函数作用于一亿个随机整数同进行性能测试；prepare_test_data则是准备1亿个随机整数的程序（这个函数实际并没有为测试数据提供足够的随机性，但这一点对性能测试的结果应该没有太大影响）

#include
#include
#include
using namespace std;

int f1(unsigned int num);
int f2(unsigned int num);
int f3(unsigned int num);
int f4(unsigned int num);
int f5(unsigned int num);

void correctness_test();
void performance_test();
void prepare_test_data(unsigned int data[], int size);

int main() {
    correctness_test();
    performance_test();
    return 0;
}

int f1(unsigned int num) {
    int count = 0;
    while(num) {
        if(num & 1) ++count;
        num >>= 1;
    }
    return count;
}

int f2(unsigned int num) {
    const unsigned int M1 = 0x55555555;
    const unsigned int M2 = 0x33333333;
    const unsigned int M4 = 0x0f0f0f0f;
    const unsigned int M8 = 0x00ff00ff;
    const unsigned int M16 = 0x0000ffff;

    num = (num & M1) + ((num >> 1) & M1);
    num = (num & M2) + ((num >> 2) & M2);
    num = (num & M4) + ((num >> 4) & M4);
    num = (num & M8) + ((num >> 8) & M8);
    num = (num & M16) + ((num >> 16) & M16);
    return num;
}

int f3(unsigned int num) {
    int count = 0;
    while(num) {
        num &= (num - 1);
        ++count;
    }
    return count;
}

int f4(unsigned int num) {
    int count = 0;
    while(num) {
        int n;
        __asm {
            bsr eax, num
            mov n, eax
        }
        ++count;
        num ^= (1 << n);
    }
    return count;
}

int f5(unsigned int num) {
    static const signed 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
    };

    unsigned char* p = reinterpret_castchar*>(&num);
    int count = 0;
    while(p != reinterpret_castchar*>(&num + 1)) {
        count += TABLE[*p++];
    }
    return count;
}

void correctness_test() {
    unsigned int test_data[] = {0, 1, 2, 3, 0x01234567, 0x89abcdef, 0xffffffff};
    unsigned int corect_result[] = {0, 1, 1, 2, 12, 20, 32};

    int (*fn[])(unsigned int) = {f1, f2, f3, f4, f5};
    for(int i = 0; i < sizeof(fn) / sizeof(*fn); ++i) {
        for(int j = 0; j < sizeof(test_data) / sizeof(*test_data); ++j) {
            if(fn[i](test_data[j]) != corect_result[j]) {
                cout << "f" << (i + 1) << " failed!" << endl;
                exit(-1);
            }
        }
    }
    cout << "All methods passed correctness test." << endl;
}

void performance_test() {
    const int TEST_DATA_SIZE = 100000000;
    unsigned int* test_data = new unsigned int[TEST_DATA_SIZE];
    prepare_test_data(test_data, TEST_DATA_SIZE);

    int (*fn[])(unsigned int) = {f1, f2, f3, f4, f5};
    for(int i = 0; i < sizeof(fn) / sizeof(*fn); ++i) {
        clock_t start = clock();
        for(int j = 0; j < TEST_DATA_SIZE; ++j) {
            fn[i](test_data[j]);
        }
        int ticks = clock() - start;
        double seconds = ticks * 1.0 / CLOCKS_PER_SEC;

        cout << "f" << (i + 1) << " consumed " << seconds << " seconds." << endl;
    }
    delete[] test_data;
}

void prepare_test_data(unsigned int* data, int len) {
    srand(0);
    for(int i = 0; i < len; ++i) {
        data[i] = static_castint>(rand() * 1.0 / RAND_MAX * 0xffffffff);
    }
}

在我的机器上（AMD Phenom 8560处理器，Windows XP SP2），使用Visual C++ 2008 Express Edition编译并运行（Release版），某一次得到的输出如下：

All methods passed correctness test.

f1 consumed 14.156 seconds.

f2 consumed 1.032 seconds.

f3 consumed 4.656 seconds.

f4 consumed 13.687 seconds.

f5 consumed 1.422 seconds.

从结果来看，最慢的是第一种“逐位测试法”，最快的是第二种“分组统计法”。两者相差近14倍！

第三种“循环减一相与法”表现也很不错，虽然跟最快的相比逊色很多，但比最慢的强多了；

第四种“汇编嵌入法”，表面上看，其复杂度是跟数值中1的位数相关，这一点与方法三一样。而不像方法一那样复杂度跟整个数的位数有关。但其表现并不令人满意，结果几乎跟方法一一样差，而无法跟方法三相比。查了一下指令手册，发现BSR指令并不是一条固定周期的指令，作用于32位整数时，快的时候它只需几个CPU时钟周期，慢的时候需要40几个时钟周期，我想它极有可能是在CPU内部通过类似于“逐位查找”的微命令实现的。

第五种“查表法”的表现倒让人相当满意，性能逼近方法二。注意我只用了基于字节编码的表，如果实际使用中需要这种运算，我们完全可以构造一个基于unsigned short编码的表，这样一个表将占用64K内存，在现代PC上仍属小菜一碟，而每个32位数只需要把前后两半查表的结果一加即可。那样一来，其性能会不会比方法二还要强呢？有兴趣的朋友可以试试。：P

最后，或许有朋友会问：第四种方法中既然采用嵌入汇编，为何不把整个函数都用汇编来写呢？那样或许效率还会好一些。但那对其它几种方法来说是不公平的，因为所有的方法都可以改用汇编来写。所以，在这个函数中我只是把依赖于特定处理器（X86）、且无法使用C++语言及其标准库直接实现的部分用汇编实现，其它的计算仍然用C++语言写出。剩下的事情，跟其它几种方法的实现一样——让编译器看着办吧，它爱怎么优化就怎么优化。