这是在golang中的实现

func CountBitSet(n int) int {


    count := 0
    for n > 0 {
      count += n & 1
      n >>= 1

    }
    return count
}

int countBits(int x)
{
    int n = 0;
    if (x) do n++;
           while(x=x&(x-1));
    return n;
}   

或者:

int countBits(int x) { return (x)? 1+countBits(x&(x-1)): 0; }

在我最初的回答7年半之后，@PeterMortensen质疑这是否是有效的C语法。我发布了一个在线编译器的链接，显示它实际上是完全有效的语法(代码如下)。

#include <stdio.h>
int countBits(int x)
{
    int n = 0;
    if (x) do n++;           /* Totally Normal Valid code. */
           while(x=x&(x-1)); /* Nothing to see here.       */
    return n;
}   
 
int main(void) {
    printf("%d\n", countBits(25));
    return 0;
}
 

输出:

3

如果你想重新写清楚，它看起来是这样的:

if (x)
{
    do
    {
        n++;
    } while(x=x&(x-1));
}

但在我看来，这太过分了。

然而，我也意识到函数可以变得更短，但可能更神秘，写为:

int countBits(int x)
{
    int n = 0;
    while (x) x=(n++,x&(x-1));
    return n;
}   

unsigned int count_bit(unsigned int x)
{
  x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
  x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
  x = (x & 0x0000FFFF) + ((x >> 16)& 0x0000FFFF);
  return x;
}

我来解释一下这个算法。

该算法基于分治算法。假设有一个8位整数213(二进制的11010101)，算法是这样工作的(每次合并两个邻居块):

+-------------------------------+
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |  <- x
|  1 0  |  0 1  |  0 1  |  0 1  |  <- first time merge
|    0 0 1 1    |    0 0 1 0    |  <- second time merge
|        0 0 0 0 0 1 0 1        |  <- third time ( answer = 00000101 = 5)
+-------------------------------+

下面是PHP中的一些东西(所有PHP整数都是32位符号，因此是31位):

function bits_population($nInteger)
{

    $nPop=0;
    while($nInteger)
    {
        $nInteger^=(1<<(floor(1+log($nInteger)/log(2))-1));
        $nPop++;
    }
    return $nPop;
}

你可以这样做:

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

工作原理如下:

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

这是一个有助于了解您的微架构的问题。我只是在gcc 4.3.3下用-O3编译的两个变量使用c++内联来计时，以消除函数调用开销，十亿次迭代，保持所有计数的运行总和，以确保编译器不删除任何重要的东西，使用rdtsc计时(精确的时钟周期)。

inline int pop2(unsigned x, unsigned y)
{
    x = x - ((x >> 1) & 0x55555555);
    y = y - ((y >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    y = (y & 0x33333333) + ((y >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    y = y + (y >> 8);
    x = x + (x >> 16);
    y = y + (y >> 16);
    return (x+y) & 0x000000FF;
}

未经修改的黑客喜悦需要122亿周期。我的并行版本(计算的比特数是它的两倍)的运行周期为13.0千兆周期。在2.4GHz的酷睿双核上，两者总共消耗了10.5秒。在这个时钟频率下，25千兆周期= 10秒多一点，所以我相信我的计时是正确的。

这与指令依赖链有关，这对算法非常不利。通过使用一对64位寄存器，我几乎可以再次将速度提高一倍。事实上，如果我聪明一点，早点加上x+y，我就可以减少一些移位。64位版本做了一些小的调整，结果是相同的，但又增加了一倍的比特数。

对于128位SIMD寄存器，这是另一个因素，SSE指令集通常也有聪明的快捷方式。

没有理由让代码特别透明。该算法界面简单，可在多处在线引用，并能通过全面的单元测试。偶然发现它的程序员甚至可能学到一些东西。这些位操作在机器级别上是非常自然的。

好吧，我决定搁置调整后的64位版本。对于这个sizeof(unsigned long) == 8

inline int pop2(unsigned long x, unsigned long y)
{
    x = x - ((x >> 1) & 0x5555555555555555);
    y = y - ((y >> 1) & 0x5555555555555555);
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
    y = (y & 0x3333333333333333) + ((y >> 2) & 0x3333333333333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0F;
    y = (y + (y >> 4)) & 0x0F0F0F0F0F0F0F0F;
    x = x + y; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x + (x >> 32); 
    return x & 0xFF;
}

这看起来是对的(不过我没有仔细测试)。现在计时结果是10.70亿周期/ 14.1亿周期。后面的数字加起来是1280亿比特，相当于这台机器运行了5.9秒。非并行版本稍微加快了一点，因为我在64位模式下运行，它更喜欢64位寄存器，而不是32位寄存器。

让我们看看这里是否有更多的OOO管道。这有点复杂，所以我实际上测试了一些。每一项单独加起来是64，所有项加起来是256。

inline int pop4(unsigned long x, unsigned long y, 
                unsigned long u, unsigned long v)
{
  enum { m1 = 0x5555555555555555, 
         m2 = 0x3333333333333333, 
         m3 = 0x0F0F0F0F0F0F0F0F, 
         m4 = 0x000000FF000000FF };

    x = x - ((x >> 1) & m1);
    y = y - ((y >> 1) & m1);
    u = u - ((u >> 1) & m1);
    v = v - ((v >> 1) & m1);
    x = (x & m2) + ((x >> 2) & m2);
    y = (y & m2) + ((y >> 2) & m2);
    u = (u & m2) + ((u >> 2) & m2);
    v = (v & m2) + ((v >> 2) & m2);
    x = x + y; 
    u = u + v; 
    x = (x & m3) + ((x >> 4) & m3);
    u = (u & m3) + ((u >> 4) & m3);
    x = x + u; 
    x = x + (x >> 8);
    x = x + (x >> 16);
    x = x & m4; 
    x = x + (x >> 32);
    return x & 0x000001FF;
}

我兴奋了一会儿，但结果是gcc在-O3上玩内联的把戏，尽管我在一些测试中没有使用内联关键字。当我让gcc玩把戏时，对pop4()的十亿次调用需要12.56 gigacycles，但我确定它是将参数折叠为常量表达式。更实际的数字似乎是19.6gc，以实现30%的加速。我的测试循环现在看起来像这样，确保每个参数足够不同，以阻止gcc耍花招。

   hitime b4 = rdtsc(); 
   for (unsigned long i = 10L * 1000*1000*1000; i < 11L * 1000*1000*1000; ++i) 
      sum += pop4 (i,  i^1, ~i, i|1); 
   hitime e4 = rdtsc(); 

2560亿比特加起来在8.17秒内过去了。根据16位表查找的基准测试，3200万比特的计算结果为1.02秒。不能直接比较，因为另一个工作台没有给出时钟速度，但看起来我已经把64KB表版本的鼻涕打出来了，这首先是L1缓存的悲惨使用。

更新:决定做明显的和创建pop6()通过增加四个重复的行。结果是22.8gc, 3840亿比特在9.5秒内加起来。所以还有20%现在是800毫秒，320亿比特。