有许多算法来计数设置位;但是我认为最好的一个是更快的一个! 您可以在本页查看详细信息:

Bit Twiddling Hacks

我建议这样做:

使用64位指令计数在14,24或32位字中设置的位

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// option 2, for at most 24-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) 
     % 0x1f;

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
     0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

这种方法需要64位CPU和快速模除法来提高效率。第一个选项只需要3个操作;第二种选择需要10;第三种选择需要15分钟。

摘自《黑客的喜悦》第66页，图5-2

int pop(unsigned x)
{
    x = x - ((x >> 1) & 0x55555555);
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
    x = (x + (x >> 4)) & 0x0F0F0F0F;
    x = x + (x >> 8);
    x = x + (x >> 16);
    return x & 0x0000003F;
}

执行大约20条指令(依赖于arch)，没有分支。黑客的喜悦是令人愉快的!强烈推荐。

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;
}
}

将整数转换为二进制字符串并计数。

PHP解决方案:

substr_count(decbin($integer), '1');

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

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

另一个汉明权重算法，如果你使用的是BMI2 CPU:

the_weight = __tzcnt_u64(~_pext_u64(data[i], data[i]));