代表数字7的8位像这样:

00000111

设置了三个比特。

确定32位整数中设置位数的算法是什么?


当前回答

你可以使用内置函数__builtin_popcount()。c++中没有__builtin_popcount,但它是GCC编译器的内置函数。这个函数返回一个整数中的设置位数。

int __builtin_popcount (unsigned int x);

参考:Bit Twiddling Hacks

其他回答

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

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位操作,它也比较慢,并且没有很好地优化。

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,并保持所有其他位相同。

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

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

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

我认为Brian Kernighan的方法也很有用… 它的迭代次数和设置位个数一样多。因此,如果我们有一个32位的单词,只设置了高位,那么它将只经过一次循环。

int countSetBits(unsigned int n) { 
    unsigned int n; // count the number of bits set in n
    unsigned int c; // c accumulates the total bits set in n
    for (c=0;n>0;n=n&(n-1)) c++; 
    return c; 
}

出版于1988年的C编程语言第二版(由Brian W. Kernighan和Dennis M. Ritchie编写)在练习2-9中提到了这一点。2006年4月19日,Don Knuth向我指出,这种方法“是由Peter Wegner在CACM 3(1960), 322中首次发表的。(同样由德里克·莱默(Derrick Lehmer)独立发现,并于1964年在贝肯巴赫(Beckenbach)编辑的一本书中出版。)

在Java 8或9中只调用Integer。bitCount。