如何计算1的数字将在二进制数字？
可能重复：
计算32位整数中设置位数的最佳algorithm是什么？
我如何计算一个数字将在二进制数字？
所以我们假设我的数字是45 ，等于101101 ，二进制数字是4 1 。 什么是写一个algorithm来做到这一点的最有效的方法？
而不是写一个algorithm来做到这一点，最好使用内置函数。 Integer.bitCount（）
是什么让这个特别有效的是，JVM可以把它当作一个内在的东西。 即在支持它的平台（例如Intel / AMD）上用单个机器代码指令来识别和replace整个事物
为了演示这种优化是多么有效
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位variables的数目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 （ “计算机程序devise艺术”第四卷，第11页），该代码首次出现在第一本关于编程的教科书“Wilkes，Wheeler和Gill 编写的电子数字计算机程序” （第二版，1957年，转载1984 ）。 本书第二版的191-193页由DB Gillies和JCP Miller提出了漂亮的平行计数 。
查看Bit Twidling Hacks并研究所有“计数位集”algorithm。 特别是，如果你期待一个小的答案，Brian Kernighan的方法很简单，速度也相当快。 如果你期望一个均匀分布的答案，查找表可能会更好。
这就是所谓的海明重量 。 这也被称为population count ， population count或sideways sum 。
以下是来自“Bit Twiddling Hacks”页面或Knuth的书籍 （我不记得）。 它适应于无符号的64位整数，并在C＃上工作。 我不知道在Java中缺less无符号值是否会造成问题。
顺便说一句，我写的代码仅供参考; 最好的答案是使用Integer.bitCount()说的; 因为在一些（但不是全部）CPU中对于这个操作有特定的机器码操作。
const UInt64 m1 = 0x5555555555555555; const UInt64 m2 = 0x3333333333333333; const UInt64 m4 = 0x0f0f0f0f0f0f0f0f; const UInt64 h01 = 0x0101010101010101; public int Count(UInt64 x) { x -= (x >> 1) & m1; x = (x & m2) + ((x >> 2) & m2); x = (x + (x >> 4)) & m4; return (int) ((x * h01) >> 56); }
public int f(int n) { int result = 0; for(;n > 0; n = n >> 1) result += ((n & 1) == 1 ? 1 : 0); return result; }
以下Ruby代码适用于正数。
count = 0 while num > 1 count = (num % 2 == 1) ? count + 1 : count num = num >> 1 end count += 1 return count
我用过最快的一个实际实现（在开源的Sphinxsearch引擎中 ）是MIT HAKMEMalgorithm 。 它在1和0的非常大的stream上运行超快。
