我个人使用这个:

  public static int myBitCount(long L){
      int count = 0;
      while (L != 0) {
         count++;
         L ^= L & -L; 
      }
      return count;
  }

下面是功能优等递归解决方案，它是迄今为止最纯粹的一个(并且可以用于任何位长度!):

template<typename T>
int popcnt(T n)
{
  if (n>0)
    return n&1 + popcnt(n>>1);
  return 0; 
}

摘自《黑客的喜悦》第66页，图5-2

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

执行大约20条指令(依赖于arch)，没有分支。黑客的喜悦是令人愉快的!强烈推荐。

我使用下面更直观的代码。

int countSetBits(int n) {
    return !n ? 0 : 1 + countSetBits(n & (n-1));
}

逻辑:n & (n-1)重置n的最后一个集合位。

附注:我知道这不是O(1)解，尽管这是一个有趣的解。

这不是最快或最好的解决方案，但我以自己的方式发现了同样的问题，我开始反复思考。最后我意识到它可以这样做，如果你从数学方面得到这个问题，画一个图，然后你发现它是一个有周期部分的函数，然后你意识到周期之间的差异……所以你看:

unsigned int f(unsigned int x)
{
    switch (x) {
        case 0:
            return 0;
        case 1:
            return 1;
        case 2:
            return 1;
        case 3:
            return 2;
        default:
            return f(x/4) + f(x%4);
    }
}

我特别喜欢这个来自《财富》的例子:

#define BITCOUNT(x)    (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
#define BX_(x)         ((x) - (((x)>>1)&0x77777777)
                             - (((x)>>2)&0x33333333)
                             - (((x)>>3)&0x11111111))

我最喜欢它，因为它太漂亮了!