天真的解决方案

时间复杂度为O(no。n的比特数)

int countSet(unsigned int n)
{
    int res=0;
    while(n!=0){
      res += (n&1);
      n >>= 1;      // logical right shift, like C unsigned or Java >>>
    }
   return res;
}

Brian Kerningam的算法

时间复杂度为O(n中设置位的个数)

int countSet(unsigned int n)
{
  int res=0;
  while(n != 0)
  {
    n = (n & (n-1));
    res++;
  }
  return res;
} 

32位数字的查找表方法-在这种方法中，我们将32位数字分解为4个8位数字的块

时间复杂度为O(1)

static unsigned char table[256]; /* the table size is 256,
                        the number of values i&0xFF (8 bits) can have */

void initialize() //holds the number of set bits from 0 to 255
{
  table[0]=0;
  for(unsigned int i=1;i<256;i++)
     table[i]=(i&1)+table[i>>1];
}

int countSet(unsigned int n)
{
  // 0xff is hexadecimal representation of 8 set bits.
  int res=table[n & 0xff];
  n=n>>8;
  res=res+ table[n & 0xff];
  n=n>>8;
  res=res+ table[n & 0xff];
  n=n>>8;
  res=res+ table[n & 0xff];
  return res;
}

def hammingWeight(n):
    count = 0
    while n:
        if n&1:
            count += 1
        n >>= 1
    return count

我觉得很无聊，于是对三种方法进行了十亿次迭代。编译器是gcc -O3。CPU就是第一代Macbook Pro里装的东西。

最快的是3.7秒:

static unsigned char wordbits[65536] = { bitcounts of ints between 0 and 65535 };
static int popcount( unsigned int i )
{
    return( wordbits[i&0xFFFF] + wordbits[i>>16] );
}

第二名是相同的代码，但查找的是4个字节而不是2个半字。这花了大约5.5秒。

第三名是“横向加法”法，用时8.6秒。

第四名是GCC的__builtin_popcount()，仅为11秒。

一次一个比特的计数方法要慢得多，我厌倦了等待它完成。

因此，如果您最关心的是性能，那么请使用第一种方法。如果您关心它，但又不想在上面花费64Kb的RAM，那么可以使用第二种方法。否则，请使用可读的(但速度较慢)一次一位的方法。

很难想象在什么情况下你会想要使用比特旋转方法。

编辑:这里也有类似的结果。

你要找的函数通常被称为二进制数的“横向和”或“总体数”。Knuth在前分册1A，第11-12页中讨论了它(尽管在第2卷，4.6.3-(7)中有简要的参考)。

经典文献是Peter Wegner的文章“二进制计算机中的一种计数技术”，摘自ACM通讯，卷3(1960)第5号，第322页。他给出了两种不同的算法，一种针对“稀疏”(即1的数量很少)的数字进行了优化，另一种针对相反的情况。

你可以这样做:

int countSetBits(int n)
{
    n=((n&0xAAAAAAAA)>>1) + (n&0x55555555);
    n=((n&0xCCCCCCCC)>>2) + (n&0x33333333);
    n=((n&0xF0F0F0F0)>>4) + (n&0x0F0F0F0F);
    n=((n&0xFF00FF00)>>8) + (n&0x00FF00FF);
    return n;
}

int main()
{
    int n=10;
    printf("Number of set bits: %d",countSetBits(n));
     return 0;
}

海王： http://ideone.com/JhwcX

工作原理如下:

首先，所有的偶数位都向右移动，并与奇数位相加，以计算两组位的数量。 然后我们两人一组，然后四个人，以此类推。

在我看来，“最好”的解决方案是另一个程序员(或者两年后的原始程序员)可以阅读而不需要大量注释的解决方案。你可能想要最快或最聪明的解决方案，有些人已经提供了，但我更喜欢可读性而不是聪明。

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);
}

这些依赖于特定的数据类型大小，所以它们不是那么可移植的。但是，由于许多性能优化是不可移植的，这可能不是一个问题。如果您想要可移植性，我会坚持使用可读的解决方案。