如何计算32位整数中的设置位数？

Question

如何计算32位整数中的设置位数？代表数字7的8位看起来像这样：00000111设置三位。什么算法来确定32位整数中的设置位数？

Answer 1

在我看来，“最佳”解决方案是另一个程序员（或两年后的原始程序员）可以阅读而没有大量评论的解决方案。你可能想要一些已经提供的最快或最聪明的解决方案，但我更喜欢可读性而不是聪明。

unsigned int bitCount (unsigned int value) {

    unsigned int count = 0;

    while (value > 0) {           // until all bits are zero

        if ((value & 1) == 1)     // check lower bit

            count++;

        value >>= 1;              // shift bits, removing lower bit

    }

    return count;

}

如果你想要更快的速度（假设你记录好以帮助你的继任者），你可以使用表查找：

// Lookup table for fast calculation of bits set in 8-bit unsigned char.

static unsigned char oneBitsInUChar[] = {

//  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F (<- n)

//  =====================================================

    0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, // 0n

    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, // 1n

    : : :

    4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8, // Fn

};

// Function for fast calculation of bits set in 16-bit unsigned short.

unsigned char oneBitsInUShort (unsigned short x) {

    return oneBitsInUChar [x >>    8]

         + oneBitsInUChar [x &  0xff];

}

// Function for fast calculation of bits set in 32-bit unsigned int.

unsigned char oneBitsInUInt (unsigned int x) {

    return oneBitsInUShort (x >>     16)

         + oneBitsInUShort (x &  0xffff);

}

虽然这些依赖于特定的数据类型大小，因此它们不具备可移植性。但是，由于许多性能优化无论如何都不可移植，这可能不是问题。如果你想要便携性，我会坚持使用可读的解决方案。