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

00000111

设置了三个比特。

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


当前回答

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

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

其他回答

public class BinaryCounter {

private int N;

public BinaryCounter(int N) {
    this.N = N;
}

public static void main(String[] args) {

    BinaryCounter counter=new BinaryCounter(7);     
    System.out.println("Number of ones is "+ counter.count());

}

public int count(){
    if(N<=0) return 0;
    int counter=0;
    int K = 0;
    do{
        K = biggestPowerOfTwoSmallerThan(N);
        N = N-K;
        counter++;
    }while (N != 0);
    return counter;

}

private int biggestPowerOfTwoSmallerThan(int N) {
    if(N==1) return 1;
    for(int i=0;i<N;i++){
        if(Math.pow(2, i) > N){
            int power = i-1;
            return (int) Math.pow(2, power);
        }
    }
    return 0;
}
}

这可以在O(k)中完成,其中k是设置的比特数。

int NumberOfSetBits(int n)
{
    int count = 0;

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

    return count;
}

我认为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)编辑的一本书中出版。)

我总是在竞争性编程中使用它,它很容易写,而且效率很高:

#include <bits/stdc++.h>

using namespace std;

int countOnes(int n) {
    bitset<32> b(n);
    return b.count();
}

以二进制表示计数集位(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)。

您可以在这里运行代码。