如何计算一个数字在二进制中的数量？
可能重复：
计算32位整数中设定位数的最佳算法？
我怎么算的数1 “SA数量将在二进制？
所以我们假设我的数字是45 ，等于二进制101101 ，并且有4 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倍的时间（获得相同的结果）
计算32位变量中1的个数的最有效方法v我知道的是：
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年）。 本书第二版191-193页由DB Gillies和JCP Miller介绍了Nifty Parallel Count。
查看Bit Twidling Hacks并研究所有'计数位集'算法。 特别是，如果你期望得到一个小答案，Brian Kernighan的方法很简单，而且速度相当快。 如果您希望得到均匀分布的答案，查找表可能会更好。
链接地址: http://www.djcxy.com/p/72577.html上一篇: How to count the number of 1's a number will have in binary?