在一个长整数中计算集合位的数量

Question

我需要计算一个长数字中有多少个二进制位是1。同时，我需要对此进行优化。

我正在使用以下代码：

public static int countSetBits(long number) {
    int count = 0;
    while (number > 0) {
        ++count;
        number &= number - 1;
    }
    return count;
}

欢迎您提出任何修改意见。

- Amit

---

你只想计算 long 中的 '1'，是吗？ - Flown

是的。所以如果输入为2，则输出应为1。对于3，它应该是2。 - Amit

Long.bitCount有什么问题？ - Dirk

Long.bitCount 很可能会被优化得比你写的任何东西都要好，甚至可能使用内部函数将其转换为一条 CPU 指令。 - Louis Wasserman

Answer 1

您可以将其写成以下形式，而不需要减法操作。

public static int countSetBits(long number) {
    int count = 0;
    while (number > 0) {
        count += number&1L;
        number>>=1L;
    }
    return count;
}

如果您想使用Java内置库，可以使用bitCount函数。

Long.bitCount(number)

如果您想查看源代码，那么

public static int  bitCount(long i) {
   i = i - ((i >>> 1) & 0x5555555555555555L);
   i = (i & 0x3333333333333333L) + ((i >>> 2) & 0x3333333333333333L);
   i = (i + (i >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
   i = i + (i >>> 8);
   i = i + (i >>> 16);
   i = i + (i >>> 32);
   return (int)i & 0x7f;
}

- ashiquzzaman33

Answer 2

你可以尝试类似的东西，

public static int countSetBits(long n){
        int count = 0;
        int temp = 0;
        for(int i = 0 ; i < 64 ; i++){ // 64-bit for long data-type
            temp = 1;
            temp = temp << i;
            temp = n & temp;
            if((temp > 0))
                count++;
        }
        return count;
    }

- Vishal Gajera

---

这种方法失败了。请参见此问题。 - trincot