如何计算1的数字将具有二进制数？

Question

可能重复:
计算32位整数中设置位数的最佳算法？

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

所以,假设我有一个数字45,它等于101101二进制数,并且有4个1.编写算法来实现此目的的最有效方法是什么？

Answer 1

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

使这个特别有效的原因是JVM可以将其视为内在的.即在支持它的平台上使用单个机器代码指令识别和替换整个事物,例如Intel/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倍的时间(得到相同的结果)

Answer 2

在v我知道的32位变量中计算1的数量的最有效方法是:

v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // c is the result

更新:我想说明这不是我的代码,实际上它比我年长.根据Donald Knuth(计算机程序设计艺术第四卷,第11页),该代码首次出现在第一本关于编程的教科书中,威尔克斯,惠勒和吉尔的电子数字计算机程序的准备(第二版,1957年,转载1984年) ).本书第2版的第191-193页介绍了DB Gillies和JCP Miller的Nifty Parallel Count.

Answer 3

参见Bit Twidling Hacks并研究所有'计数位集'算法.特别是,如果你期望一个小答案,Brian Kernighan的方式很简单,也很快.如果您期望均匀分布的答案,查找表可能会更好.

Answer 4

这称为汉明重量.它也被称为population count,popcount或sideways sum.