一个快速的c#解决方案，使用预先计算的字节位计数表，并根据输入大小进行分支。

public static class BitCount
{
    public static uint GetSetBitsCount(uint n)
    {
        var counts = BYTE_BIT_COUNTS;
        return n <= 0xff ? counts[n]
             : n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
             : n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
             : counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
    }

    public static readonly uint[] BYTE_BIT_COUNTS =
    {
        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
    };
}

这是一个可移植的模块(ANSI-C)，它可以在任何架构上对每个算法进行基准测试。

你的CPU有9位字节?目前它实现了2个算法，K&R算法和一个字节查找表。查找表的平均速度比K&R算法快3倍。如果有人能想出办法使“黑客的喜悦”算法可移植，请随意添加它。

#ifndef _BITCOUNT_H_
#define _BITCOUNT_H_

/* Return the Hamming Wieght of val, i.e. the number of 'on' bits. */
int bitcount( unsigned int );

/* List of available bitcount algorithms.  
 * onTheFly:    Calculate the bitcount on demand.
 *
 * lookupTalbe: Uses a small lookup table to determine the bitcount.  This
 * method is on average 3 times as fast as onTheFly, but incurs a small
 * upfront cost to initialize the lookup table on the first call.
 *
 * strategyCount is just a placeholder. 
 */
enum strategy { onTheFly, lookupTable, strategyCount };

/* String represenations of the algorithm names */
extern const char *strategyNames[];

/* Choose which bitcount algorithm to use. */
void setStrategy( enum strategy );

#endif

.

#include <limits.h>

#include "bitcount.h"

/* The number of entries needed in the table is equal to the number of unique
 * values a char can represent which is always UCHAR_MAX + 1*/
static unsigned char _bitCountTable[UCHAR_MAX + 1];
static unsigned int _lookupTableInitialized = 0;

static int _defaultBitCount( unsigned int val ) {
    int count;

    /* Starting with:
     * 1100 - 1 == 1011,  1100 & 1011 == 1000
     * 1000 - 1 == 0111,  1000 & 0111 == 0000
     */
    for ( count = 0; val; ++count )
        val &= val - 1;

    return count;
}

/* Looks up each byte of the integer in a lookup table.
 *
 * The first time the function is called it initializes the lookup table.
 */
static int _tableBitCount( unsigned int val ) {
    int bCount = 0;

    if ( !_lookupTableInitialized ) {
        unsigned int i;
        for ( i = 0; i != UCHAR_MAX + 1; ++i )
            _bitCountTable[i] =
                ( unsigned char )_defaultBitCount( i );

        _lookupTableInitialized = 1;
    }

    for ( ; val; val >>= CHAR_BIT )
        bCount += _bitCountTable[val & UCHAR_MAX];

    return bCount;
}

static int ( *_bitcount ) ( unsigned int ) = _defaultBitCount;

const char *strategyNames[] = { "onTheFly", "lookupTable" };

void setStrategy( enum strategy s ) {
    switch ( s ) {
    case onTheFly:
        _bitcount = _defaultBitCount;
        break;
    case lookupTable:
        _bitcount = _tableBitCount;
        break;
    case strategyCount:
        break;
    }
}

/* Just a forwarding function which will call whichever version of the
 * algorithm has been selected by the client 
 */
int bitcount( unsigned int val ) {
    return _bitcount( val );
}

#ifdef _BITCOUNT_EXE_

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/* Use the same sequence of pseudo random numbers to benmark each Hamming
 * Weight algorithm.
 */
void benchmark( int reps ) {
    clock_t start, stop;
    int i, j;
    static const int iterations = 1000000;

    for ( j = 0; j != strategyCount; ++j ) {
        setStrategy( j );

        srand( 257 );

        start = clock(  );

        for ( i = 0; i != reps * iterations; ++i )
            bitcount( rand(  ) );

        stop = clock(  );

        printf
            ( "\n\t%d psudoe-random integers using %s: %f seconds\n\n",
              reps * iterations, strategyNames[j],
              ( double )( stop - start ) / CLOCKS_PER_SEC );
    }
}

int main( void ) {
    int option;

    while ( 1 ) {
        printf( "Menu Options\n"
            "\t1.\tPrint the Hamming Weight of an Integer\n"
            "\t2.\tBenchmark Hamming Weight implementations\n"
            "\t3.\tExit ( or cntl-d )\n\n\t" );

        if ( scanf( "%d", &option ) == EOF )
            break;

        switch ( option ) {
        case 1:
            printf( "Please enter the integer: " );
            if ( scanf( "%d", &option ) != EOF )
                printf
                    ( "The Hamming Weight of %d ( 0x%X ) is %d\n\n",
                      option, option, bitcount( option ) );
            break;
        case 2:
            printf
                ( "Please select number of reps ( in millions ): " );
            if ( scanf( "%d", &option ) != EOF )
                benchmark( option );
            break;
        case 3:
            goto EXIT;
            break;
        default:
            printf( "Invalid option\n" );
        }

    }

 EXIT:
    printf( "\n" );

    return 0;
}

#endif

这就是所谓的“汉明权重”，“popcount”或“横向相加”。

一些cpu有单独的内置指令来做这件事，而另一些cpu有并行指令来处理位向量。像x86的popcnt(在支持它的cpu上)这样的指令几乎肯定对单个整数来说是最快的。其他一些架构可能有一个缓慢的指令，实现了一个微编码循环，每个周期测试一个比特(需要引用-硬件popcount通常是快速的，如果它存在的话。)

“最佳”算法实际上取决于你所使用的CPU以及你的使用模式。

Your compiler may know how to do something that's good for the specific CPU you're compiling for, e.g. C++20 std::popcount(), or C++ std::bitset<32>::count(), as a portable way to access builtin / intrinsic functions (see another answer on this question). But your compiler's choice of fallback for target CPUs that don't have hardware popcnt might not be optimal for your use-case. Or your language (e.g. C) might not expose any portable function that could use a CPU-specific popcount when there is one.

---

不需要(或受益于)任何硬件支持的可移植算法

如果您的CPU有一个很大的缓存，并且您在一个紧密的循环中执行大量这些操作，那么预先填充的表查找方法可以非常快。然而，它可能会因为“缓存丢失”的代价而受到影响，在这种情况下，CPU必须从主存中获取一些表。(分别查找每个字节以保持表小。)如果你想要popcount的连续范围的数字，只有低字节改变的组256个数字，这是非常好的。

如果你知道你的字节大部分是0或1，那么就有针对这些情况的有效算法，例如在循环中使用bithack清除最低的集合，直到它变成0。

我相信一个非常好的通用算法是以下，称为“并行”或“可变精度SWAR算法”。我已经在一个类似C的伪语言中表达了这一点，你可能需要调整它以适用于特定的语言(例如使用uint32_t for c++和>>> in Java):

GCC10和clang 10.0可以识别这种模式/习惯用法，并在可用时将其编译为硬件popcnt或等效指令，为您提供两全其美的服务。(https://godbolt.org/z/qGdh1dvKK)

int numberOfSetBits(uint32_t i)
{
     // Java: use int, and use >>> instead of >>. Or use Integer.bitCount()
     // C or C++: use uint32_t
     i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
     i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
     i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
     return (i * 0x01010101) >> 24;          // horizontal sum of bytes
}

对于JavaScript:强制为整数|0的性能:更改第一行为i = (i|0) - ((i >> 1) & 0x55555555);

这是所有讨论过的算法中最糟糕的行为，因此可以有效地处理您抛出的任何使用模式或值。(它的性能不依赖于普通cpu的数据，在普通cpu中，包括乘法在内的所有整数操作都是常量时间。“简单”输入不会让它变得更快，但它仍然相当不错。)

引用:

https://graphics.stanford.edu/~seander/bithacks.html https://catonmat.net/low-level-bit-hacks用于bithack基础知识，例如如何减去1翻转连续的零。 https://en.wikipedia.org/wiki/Hamming_weight http://gurmeet.net/puzzles/fast-bit-counting-routines/ http://aggregate.ee.engr.uky.edu/MAGIC/人口% 20计数% 20(% 20计数)

---

这个SWAR bithack如何工作:

i = i - ((i >> 1) & 0x55555555);

第一步是屏蔽的优化版本，以隔离奇数/偶数位，移动以对齐它们，并添加。这有效地在2位累加器(SWAR = SIMD Within A Register)中进行16个独立的加法。比如(i & 0x55555555) + ((i>>1) & 0x55555555)。

下一步是取这16个2位累加器中的奇/偶8个，然后再次相加，得到8个4位累加器。我…这次不可能进行优化，所以它只是在移动之前/之后进行遮罩。使用相同的0x33…两次都是常量，而不是0xccc…在为需要单独在寄存器中构造32位常量的isa编译时，在移位之前进行转换是一件好事。

(i + (i >> 4)) & 0x0F0F0F0F的最后一个移位和添加步骤将扩大为4个8位累加器。它在加后而不是加前进行掩码，因为如果设置了所有对应的4位输入位，则任何4位累加器中的最大值为4。4+4 = 8仍然适合4位，所以在I + (I >> 4)中，啃食元素之间的进位是不可能的。

到目前为止，这只是使用SWAR技术和一些聪明的优化的相当普通的SIMD。继续相同的模式2步可以扩大到2x 16位，然后1x 32位计数。但在硬件快速相乘的机器上，有一种更有效的方法:

一旦我们有足够少的“元素”，一个神奇常数的乘法可以把所有的元素加起来变成最上面的元素。在本例中是字节元素。乘法是通过左移和加法完成的，因此x * 0x01010101的乘法得到x + (x<<8) + (x<<16) + (x<<24)。我们的8位元素足够宽(并且包含足够小的计数)，因此不会产生进位到前8位。

它的64位版本可以使用0x0101010101010101乘数在64位整数中处理8x 8位元素，并使用>>56提取高字节。所以它不需要任何额外的步骤，只是更大的常数。这是当硬件popcnt指令未启用时，GCC在x86系统上对__builtin_popcountll使用的方法。如果您可以为此使用内置或内在函数，那么这样做可以让编译器有机会进行特定于目标的优化。

---

对于更宽的向量具有完整的SIMD(例如计算整个数组)

这种逐位swar算法可以在多个向量元素中同时进行并行运算，而不是在单个整数寄存器中进行并行运算，从而在具有SIMD但没有可用popcount指令的cpu上实现加速。(例如x86-64代码必须在任何CPU上运行，而不仅仅是Nehalem或更高版本。)

然而，对popcount使用矢量指令的最佳方法通常是使用变量-shuffle并行地对每个字节每次4位进行表查找。(4位索引保存在向量寄存器中的16项表)。

在Intel cpu上，硬件64位popcnt指令的性能比SSSE3 PSHUFB位并行实现的性能好2倍，但前提是编译器的性能恰到好处。否则，上交所可能会大幅领先。较新的编译器版本意识到popcnt对Intel的错误依赖问题。

https://github.com/WojciechMula/sse-popcount state-of-the-art x86 SIMD popcount for SSSE3, AVX2, AVX512BW, AVX512VBMI, or AVX512 VPOPCNT. Using Harley-Seal across vectors to defer popcount within an element. (Also ARM NEON) Counting 1 bits (population count) on large data using AVX-512 or AVX-2 related: https://github.com/mklarqvist/positional-popcount - separate counts for each bit-position of multiple 8, 16, 32, or 64-bit integers. (Again, x86 SIMD including AVX-512 which is really good at this, with vpternlogd making Harley-Seal very good.)

我认为最快的方法——不使用查找表和popcount——是以下方法。它仅通过12次操作来计数设置位。

int popcount(int v) {
    v = v - ((v >> 1) & 0x55555555);                // put count of each 2 bits into those 2 bits
    v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // put count of each 4 bits into those 4 bits  
    return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}

它之所以有效，是因为你可以通过将设置位分为两半来计算总设置位的数量，计算两半设置位的数量，然后将它们相加。也被称为分而治之范式。让我们来详细谈谈。

v = v - ((v >> 1) & 0x55555555); 

两位位数可以是0b00、0b01或0b10。让我们试着在2位上解决这个问题。

 ---------------------------------------------
 |   v    |   (v >> 1) & 0b0101   |  v - x   |
 ---------------------------------------------
   0b00           0b00               0b00   
   0b01           0b00               0b01     
   0b10           0b01               0b01
   0b11           0b01               0b10

这就是所需要的:最后一列显示每两个位对中设置位的计数。如果两个比特数>= 2 (0b10)，则产生0b01，否则产生0b00。

v = (v & 0x33333333) + ((v >> 2) & 0x33333333); 

这句话应该很容易理解。在第一个操作之后，我们每两个比特中就有一个set位的计数，现在我们每4个比特中就有一个set位的计数。

v & 0b00110011         //masks out even two bits
(v >> 2) & 0b00110011  // masks out odd two bits

然后我们把上面的结果加起来，得到4位的集合位总数。最后一个陈述是最棘手的。

c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;

让我们进一步分析一下……

v + (v >> 4)

这和第二种说法很相似;我们以4为一组来计数集合位。因为我们之前的运算，我们知道每一个咬痕都有一个集合位的计数。让我们看一个例子。假设我们有字节0b01000010。这意味着第一个啃食有它的4位设置，第二个有它的2位设置。现在我们把这些小块加在一起。

v = 0b01000010
(v >> 4) = 0b00000100
v + (v >> 4) = 0b01000010 + 0b00000100

它为我们提供了一个字节中set位的计数，在第二个nibble 0b01000110中，因此我们掩码了该数字中所有字节的前四个字节(丢弃它们)。

0b01000110 & 0x0F = 0b00000110

现在每个字节都有一个集合位的计数。我们需要把它们全部加起来。诀窍是将结果乘以0b10101010，它有一个有趣的属性。如果我们的数字有四个字节，A B C D，它将产生一个新的数字，包含这些字节A+B+C+D B+C+D C+D。一个4字节的数字最多可以设置32位，可以表示为0b00100000。

我们现在需要的是第一个字节，它是所有字节中所有set位的和，我们通过>> 24得到它。该算法是为32位字设计的，但可以很容易地修改为64位字。

我在任何地方都没见过这种方法:

int nbits(unsigned char v) {
    return ((((v - ((v >> 1) & 0x55)) * 0x1010101) & 0x30c00c03) * 0x10040041) >> 0x1c;
}

它每字节工作一次，所以对于一个32位整数，它必须被调用四次。它源于横向加法，但它使用两个32位乘法将指令数量减少到只有7条。

大多数当前的C编译器将使用SIMD (SSE2)指令优化这个函数，当请求的数量是4的倍数时，它变得非常有竞争力。它是可移植的，可以定义为宏或内联函数，并且不需要数据表。

这种方法可以扩展为一次处理16位，使用64位乘法。但是，当所有16位都被设置时，它会失败，返回0，所以它只能在0xFFFF输入值不存在时使用。由于64位操作，它也比较慢，并且没有很好地优化。

如果你使用c++，另一个选择是使用模板元编程:

// recursive template to sum bits in an int
template <int BITS>
int countBits(int val) {
        // return the least significant bit plus the result of calling ourselves with
        // .. the shifted value
        return (val & 0x1) + countBits<BITS-1>(val >> 1);
}

// template specialisation to terminate the recursion when there's only one bit left
template<>
int countBits<1>(int val) {
        return val & 0x1;
}

用法如下:

// to count bits in a byte/char (this returns 8)
countBits<8>( 255 )

// another byte (this returns 7)
countBits<8>( 254 )

// counting bits in a word/short (this returns 1)
countBits<16>( 256 )

当然，你可以进一步扩展这个模板来使用不同的类型(甚至是自动检测位大小)，但为了清晰起见，我让它保持简单。

edit:忘了说这很好，因为它应该在任何c++编译器中工作，它基本上只是为你展开循环，如果一个常量值用于比特计数(换句话说，我很确定这是你能找到的最快的通用方法)