你可以这样做:

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

工作原理如下:

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

从Python 3.10开始，你将能够使用int.bit_count()函数，但目前，你可以自己定义这个函数。

def bit_count(integer):
    return bin(integer).count("1")

天真的解决方案

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

我使用下面的函数。我还没有检查基准测试，但它是有效的。

int msb(int num)
{
    int m = 0;
    for (int i = 16; i > 0; i = i>>1)
    {
        // debug(i, num, m);
        if(num>>i)
        {
            m += i;
            num>>=i;
        }
    }
    return m;
}

以二进制表示计数集位(N):

伪代码,

设置counter = 0。 重复计数，直到N不为零。 检查最后一点。 如果最后一位= 1，则递增计数器 丢弃N的最后一位。

现在让我们用c++编写代码

int countSetBits(unsigned int n){

int count = 0;

while(n!=0){

    count += n&1;

    n = n >>1;
}

  return count;

}

我们用这个函数。

int main(){

 int x = 5;
 cout<<countSetBits(x);

 return 0;
}

输出:2

因为5有2位二进制表示(101)。

您可以在这里运行代码。

你可以:

while(n){
    n = n & (n-1);
    count++;
}

这背后的逻辑是n-1位从n的最右边的集合位倒出来。

如果n=6，即110，那么5是101，位从n的最右边的集合位倒出来。

因此，如果我们&这两个，我们将在每次迭代中使最右边的位为0，并且总是到下一个最右边的集位。因此，计数设置位。当每一位都被设置时，最糟糕的时间复杂度将是O(log n)。