天真的解决方案

时间复杂度为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;
}

我觉得很无聊，于是对三种方法进行了十亿次迭代。编译器是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，那么可以使用第二种方法。否则，请使用可读的(但速度较慢)一次一位的方法。

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

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

Kotlin 1.4 之前

        fun NumberOfSetBits(i: Int): Int {
            var i = i
            i -= (i ushr 1 and 0x55555555)
            i = (i and 0x33333333) + (i ushr 2 and 0x33333333)
            return (i + (i ushr 4) and 0x0F0F0F0F) * 0x01010101 ushr 24
        }

这或多或少是上面那个答案的翻版。

它带有Java补丁，然后使用IntelliJ IDEA Community Edition中的转换器进行转换

1.4及以上(截至2021-05-05 -未来可能会改变)。

        fun NumberOfSetBits(i: Int): Int {
            return i.countOneBits()
        }

在底层，它使用Integer。bitCount如下所示:

@SinceKotlin("1.4")
@WasExperimental(ExperimentalStdlibApi::class)
@kotlin.internal.InlineOnly
public actual inline fun Int.countOneBits(): Int = Integer.bitCount(this)

这里有一个到目前为止还没有提到的解决方案，使用位字段。下面的程序使用4种不同的方法对100000000个16位整数数组中的设置位进行计数。计时结果在括号中给出(在MacOSX上，使用gcc -O3):

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

#define LENGTH 100000000

typedef struct {
    unsigned char bit0 : 1;
    unsigned char bit1 : 1;
    unsigned char bit2 : 1;
    unsigned char bit3 : 1;
    unsigned char bit4 : 1;
    unsigned char bit5 : 1;
    unsigned char bit6 : 1;
    unsigned char bit7 : 1;
} bits;

unsigned char sum_bits(const unsigned char x) {
    const bits *b = (const bits*) &x;
    return b->bit0 + b->bit1 + b->bit2 + b->bit3 \
         + b->bit4 + b->bit5 + b->bit6 + b->bit7;
}

int NumberOfSetBits(int i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}

#define out(s) \
    printf("bits set: %lu\nbits counted: %lu\n", 8*LENGTH*sizeof(short)*3/4, s);

int main(int argc, char **argv) {
    unsigned long i, s;
    unsigned short *x = malloc(LENGTH*sizeof(short));
    unsigned char lut[65536], *p;
    unsigned short *ps;
    int *pi;

    /* set 3/4 of the bits */
    for (i=0; i<LENGTH; ++i)
        x[i] = 0xFFF0;

    /* sum_bits (1.772s) */
    for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=sum_bits(*p++));
    out(s);

    /* NumberOfSetBits (0.404s) */
    for (i=LENGTH*sizeof(short)/sizeof(int), pi=(int*)x, s=0; i--; s+=NumberOfSetBits(*pi++));
    out(s);

    /* populate lookup table */
    for (i=0, p=(unsigned char*) &i; i<sizeof(lut); ++i)
        lut[i] = sum_bits(p[0]) + sum_bits(p[1]);

    /* 256-bytes lookup table (0.317s) */
    for (i=LENGTH*sizeof(short), p=(unsigned char*) x, s=0; i--; s+=lut[*p++]);
    out(s);

    /* 65536-bytes lookup table (0.250s) */
    for (i=LENGTH, ps=x, s=0; i--; s+=lut[*ps++]);
    out(s);

    free(x);
    return 0;
}

虽然位域版本非常可读，但计时结果显示它比NumberOfSetBits()慢了4倍以上。基于查找表的实现仍然要快得多，特别是对于一个65 kB的表。

Python的解决方案:

def hammingWeight(n: int) -> int:
    sums = 0
    while (n!=0):
        sums+=1
        n = n &(n-1)

    return sums

在二进制表示中，n中最不有效的1位总是对应n - 1中的0位。因此，对n和n - 1这两个数进行and运算总是将n中最不有效的1位翻转为0，并保持所有其他位相同。

#!/user/local/bin/perl


    $c=0x11BBBBAB;
     $count=0;
     $m=0x00000001;
    for($i=0;$i<32;$i++)
    {
        $f=$c & $m;
        if($f == 1)
        {
            $count++;
        }
        $c=$c >> 1;
    }
    printf("%d",$count);

ive done it through a perl script. the number taken is $c=0x11BBBBAB   
B=3 1s   
A=2 1s   
so in total  
1+1+3+3+3+2+3+3=19