这个位操作在Java中如何工作？
我正在研究Java如何计算int的位集。
在我的脑海里，我有一些像这样的简单（我认为是正确的）：
public static int bitCount(int number){ final int MASK = 0x1; int count = 0; for(int i = 0; i >> i) & MASK) == MASK){ count++; } } return count; } 相反，我发现了一种方法，我完全不知道在做什么（对我来说似乎很神奇）：
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;
有人可以帮助理解这是什么以及为什么一个简单的function，如我最初想到的那个/可能是坏的？
当然
i = i - ((i >>> 1) & 0x55555555);
5的位模式是0101 （4位），因此掩码是位模式01的重复16次。 该行计算该数字的每两位对中的位数。 如果考虑两位对， (i >>> 1) & 0x1得到低位的高位。 现在，有四种可能的两位模式
00 ~> 00 - 00 = 00 01 ~> 01 - 00 = 01 10 ~> 10 - 01 = 01 11 ~> 11 - 01 = 10
现在每个两位对包含原始位置的位数。
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
接下来，我们计算每个四位组（也称为半字节）中的位数。 通过屏蔽具有0x3 = 0011(b)的半字节，我们得到半字节的低位两位的位数，并且(i >>> 2) & 0x3从高位的两位得到计数。蚕食。 现在添加了这些计数。 由于每个计数最多为2，因此总和最多为4，因此不会留下半字节。
i = (i + (i >>> 4)) & 0x0f0f0f0f;
现在计算每个八位字节中的位数。 每个半字节包含该位置原始位置的位数。 向右移动四位将计数从每个位置的高阶半字节移动到低阶半字节，这些都被添加。 然后我们还将计数从低阶半字节移动到相邻八位字节的高阶nets，由& 0x0f0f0f0f屏蔽掉。 由于每个八位字节最多可以设置8位，因此计数不会离开八位字节的低位半字节。
i = i + (i >>> 8);
现在我们添加相邻八位字节对的计数。
i = i + (i >>> 16);
现在我们在高阶两个八位字节和低阶二中添加计数的总数。
return i & 0x3f;
最后，除了最低阶八位字节之外的所有八位字节都被屏蔽掉，因为高阶八位字节仍然包含中间计数。
您的简单实现可能被认为是错误的原因是性能。 复杂的bit-hack使用较少的操作而没有分支，因此速度更快。 然而，这更容易出错。
计算int （或long ）中的设置位的另一种巧妙方法是
public static int bitCount(int n) { int count = 0; while(n != 0) { ++count; n = n & (n-1); } return count; }
这是有效的，因为n = n & (n-1)清除n = n & (n-1)的最后一个设置位并保持其他所有内容不变。 如果n的位模式结束
...100...0
n-1的位模式是
...011...1
并且n中最后1位之前的位是相同的。 在Java中，保证也可以用于负数，因为整数溢出具有环绕语义，因此如果n = Integer.MIN_VALUE ，则位模式为100...0并且n - 1变为具有位模式的Integer.MAX_VALUE 011...1
cool方法只有在计算机具有int的有限值范围时才有效。 因为你需要在计算之前知道所有需要的掩码，所以它无法在无限范围（如BigInteger）中轻松工作（以及其他很酷的位算法）。
无论如何，你可以通过以下方式阅读它的工作原理： http ： //graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
它在本章的底部。