java - 如何计算二进制数字中1的数量？

Question

Possible Duplicate:
Best algorithm to count the number of set bits in a 32-bit integer?

我如何计算 1 的二进制数？

假设我有数字 45，它等于二进制中的 101101，其中有 4 个 1。编写算法来执行此操作的最有效方法是什么？

Answer 1

最好使用内置函数，而不是编写算法来做到这一点。 Integer.bitCount()

使这特别有效的原因是 JVM 可以将其视为内在函数。即在支持它的平台上用单个机器代码指令识别和替换整个事物，例如英特尔/AMD

---

为了展示这种优化的有效性

public static void main(String... args) {
    perfTestIntrinsic();

    perfTestACopy();
}

private static void perfTestIntrinsic() {
    long start = System.nanoTime();
    long countBits = 0;
    for (int i = 0; i < Integer.MAX_VALUE; i++)
        countBits += Integer.bitCount(i);
    long time = System.nanoTime() - start;
    System.out.printf("Intrinsic: Each bit count took %.1f ns, countBits=%d%n", (double) time / Integer.MAX_VALUE, countBits);
}

private static void perfTestACopy() {
    long start2 = System.nanoTime();
    long countBits2 = 0;
    for (int i = 0; i < Integer.MAX_VALUE; i++)
        countBits2 += myBitCount(i);
    long time2 = System.nanoTime() - start2;
    System.out.printf("Copy of same code: Each bit count took %.1f ns, countBits=%d%n", (double) time2 / Integer.MAX_VALUE, countBits2);
}

// Copied from Integer.bitCount()
public static int myBitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

打印

Intrinsic: Each bit count took 0.4 ns, countBits=33285996513
Copy of same code: Each bit count took 2.4 ns, countBits=33285996513

使用内部版本和循环的每个位计数平均只需 0.4 纳秒。使用相同代码的副本需要 6 倍的时间(得到相同的结果)