如何找到一个32位数中'1'的个数

如何找到一个32位数中‘1’的个数呢？举个例子，给定一个输入，比如0x1013，那其中‘1’的个数便是4；再给定一个输入，比如是0xff00ff00，那其中‘1’的个数便是16。这个题目的解法有多种，第一反应是做一个循环，每次判断一下这个数的最低位(LSB)是否是1，然后向右移位，直到这个数为0为止。

unsigned long findOnes(unsigned long number)
{
    unsigned long count = 0;
    for (; number; number = (number >> 1))
        if (number & 0x1)
            count++;
    return count;
}

测试程序如下，

int _tmain(int argc, _TCHAR* argv[])
{
    unsigned long testArray[] = {0, 0xffffffff, 0x12345678, 0x11111111, 0x22222222, 0x33333333};
    for (size_t i = 0; i < sizeof(testArray)/sizeof(unsigned long); i++)
    {
        cout << "Input number is 0x" << hex << testArray[i] << ", totally " << dec << findOnes(testArray[i]) << " '1'(s) " << endl;
    }

    system("pause");
    return 0;
}

输出为
Input number is 0x0, totally 0 '1'(s)
Input number is 0xffffffff, totally 32 '1'(s)
Input number is 0x12345678, totally 13 '1'(s)
Input number is 0x11111111, totally 8 '1'(s)
Input number is 0x22222222, totally 8 '1'(s)
Input number is 0x33333333, totally 16 '1'(s)
程序看上去一切正常。可是是否还有更好的算法呢？是否能让计算变得更快呢？
我的一个改进的想法是用空间换时间，代码如下，

unsigned long fixedMap[] =
    {
        0, 1, 1, 2, 1, 2, 2, 3,
        1, 2, 2, 3, 2, 3, 3, 4
    };

#define LOW_BIT4(NUM) ((NUM) & 0xF)

unsigned long findOnes(unsigned long number)
{
    return fixedMap[LOW_BIT4(number)]        + fixedMap[LOW_BIT4(number>>4)]
         + fixedMap[LOW_BIT4(number>>8)]     + fixedMap[LOW_BIT4(number>>12)]
         + fixedMap[LOW_BIT4(number>>16)]    + fixedMap[LOW_BIT4(number>>20)]
         + fixedMap[LOW_BIT4(number>>24)]    + fixedMap[LOW_BIT4(number>>28)];
}

定义一个fixedMap，共16个元素，index代表数的大小，value代表这个数含有多少个‘1’，然后把32位长整形分割成8份，把每一份含有‘1’的个数做加法。


还有一个更现成一点的办法，那就是用STL提供的bitset来实现，

unsigned long findOnes(unsigned long number)
{
    bitset<32> tempBitSet((long)number);
    return tempBitSet.count();
}

此处使用long来强制转换number，因为bitset模板的构造函数并未提供输入参数是unsigned long类型的重载函数，所以要让编译器明确一下，否则会编译不过。这里稍微深入一下bitset，看一下内部的实现，我惊奇的发现，事实上bitset提供的count函数和我自己之前实现的空间换时间的版本的思路是基本一致的，如下

size_t count() const
        {    // count number of set bits
        static char _Bitsperhex[] = "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4";
        size_t _Val = 0;
        for (int _Wpos = _Words; 0 <= _Wpos; --_Wpos)
            for (_Ty _Wordval = _Array[_Wpos]; _Wordval != 0; _Wordval >>= 4)
                _Val += _Bitsperhex[_Wordval & 0xF];
        return (_Val);
        }

不过事实上使用bitset要更慢一些，原因是bitset的构造函数也要花费一定的时间，进行构造，代码清单如下

bitset(int _Ival)
        {    // construct from bits in int
        unsigned int _Val = (unsigned int)_Ival;
        _Tidy();
        for (size_t _Pos = 0; _Val != 0 && _Pos < _Bits; _Val >>= 1, ++_Pos)
            if (_Val & 1)
                set(_Pos);
        }

最后再列出一种网上某大哥写的方法，这个方法比较难理解，不过因为没有循环操作，效率亦很高，

unsigned long findOnes(unsigned long number)
{
#define C55 0x5555555555555555ULL
#define C33 0x3333333333333333ULL
#define C0F 0x0f0f0f0f0f0f0f0fULL
#define C01 0x0101010101010101ULL

    number -= (number >> 1) & C55;                      // put count of each 2 bits into those 2 bits
    number = (number & C33) + ((number >> 2) & C33);    // put count of each 4 bits into those 4 bits
    number = (number + (number >> 4)) & C0F; // put count of each 8 bits into those 8 bits
    return (number * C01) >> 56;      // returns left 8 bits of x + (x<<8) + (x<<16) + (x<<24) + ...
}