在UInt32中计算设置位的最快方法是什么

在不使用查找表的情况下，在UInt32计算设置位数（即计算1的数量）的最快方法是什么？ 有没有办法计算O(1) ？

Answer 1

是重复的： 如何实现-bitcount-using-only-bitwise-operators或best-algorithm-to-count-of-set-bits-in-a-32-bit-integer

这个问题有很多解决方案。 我使用的是：

  int NumberOfSetBits(int i) { i = i - ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24; } 

Answer 2

这个讨厌的黑客页面有很多选项。

当然，您可以争辩说，迭代所有32个可能的位是O（N），因为它每次都是相同的成本:)

为简单起见，我会考虑每字节查找表的方法，或者Brian Kernighan的巧妙构思，它的迭代次数与有些位集相同，我将其写为：

 public static int CountBits(uint value) { int count = 0; while (value != 0) { count++; value &= value - 1; } return count; } 

如果你不喜欢填充256条目查找表的想法，那么每个nybble的查找仍然会非常快。 请注意，8个数组查找可能比32个简单位操作慢。

当然，在采用特别深奥的方法之前，值得测试你的应用程序的真实性能……这真的是你的瓶颈吗？

Answer 3

这是java中用于获取给定数字的设置位的解决方案。

 import java.util.*; public class HelloWorld { static int setBits(int n) { int count = 0; while(n != 0) { count+= ((n & 1) == 1) ? 1 : 0; n >>= 1; } return count; } public static void main(String []args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println("Results: " + HelloWorld.setBits(n)); } }