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

00000111

设置了三个比特。

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


当前回答

这也可以正常工作:

int ans = 0;
while(num) {
  ans += (num & 1);
  num = num >> 1;
}    
return ans;

其他回答

int bitcount(unsigned int n)
{ 
      int count=0;
      while(n)
      {
           count += n & 0x1u;
           n >>= 1;
      }
      return  count;
 }

迭代的“计数”运行的时间与总比特数成比例。它只是循环遍历所有位,因为while条件而稍微提前终止。如果1'S或集合位是稀疏的且在最低有效位之间,则很有用。

对于232查找表和逐个遍历每个位之间的折中方法:

int bitcount(unsigned int num){
    int count = 0;
    static int nibblebits[] =
        {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
    for(; num != 0; num >>= 4)
        count += nibblebits[num & 0x0f];
    return count;
}

从http://ctips.pbwiki.com/CountBits

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

大约在1990年,我为RISC机器编写了一个快速比特计数宏。它不使用高级算术(乘法,除法,%),内存提取(太慢),分支(太慢),但它确实假设CPU有一个32位的桶移位器(换句话说,>> 1和>> 32占用相同的周期)。它假定小常数(如6、12、24)加载到寄存器中不需要花费任何代价,或者存储在临时变量中并反复重用。

在这些假设下,在大多数RISC机器上,它在大约16个周期/指令中计算32位。注意,15条指令/周期接近于周期或指令数量的下界,因为似乎至少需要3条指令(掩码、移位、运算符)才能将加数的数量减半,因此log_2(32) = 5,5 x 3 = 15条指令是准下界。

#define BitCount(X,Y)           \
                Y = X - ((X >> 1) & 033333333333) - ((X >> 2) & 011111111111); \
                Y = ((Y + (Y >> 3)) & 030707070707); \
                Y =  (Y + (Y >> 6)); \
                Y = (Y + (Y >> 12) + (Y >> 24)) & 077;

这是第一步也是最复杂的一步:

input output
AB    CD             Note
00    00             = AB
01    01             = AB
10    01             = AB - (A >> 1) & 0x1
11    10             = AB - (A >> 1) & 0x1

所以如果我取上面的第一列(A),右移1位,然后从AB减去它,我就得到了输出(CD)。扩展到3位类似;如果你愿意,你可以用一个8行布尔表来检查它。

不吉利

一个快速的c#解决方案,使用预先计算的字节位计数表,并根据输入大小进行分支。

public static class BitCount
{
    public static uint GetSetBitsCount(uint n)
    {
        var counts = BYTE_BIT_COUNTS;
        return n <= 0xff ? counts[n]
             : n <= 0xffff ? counts[n & 0xff] + counts[n >> 8]
             : n <= 0xffffff ? counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff]
             : counts[n & 0xff] + counts[(n >> 8) & 0xff] + counts[(n >> 16) & 0xff] + counts[(n >> 24) & 0xff];
    }

    public static readonly uint[] BYTE_BIT_COUNTS =
    {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    };
}