如何在O（1）时间内找到二进制数的1？
我知道之前已经问过，但我正在看这里列出的特定解决方案：
int BitCount(unsigned int u) { unsigned int uCount; uCount = u - ((u >> 1) & 033333333333) - ((u >> 2) & 011111111111); return ((uCount + (uCount >> 3)) & 030707070707) % 63; } 它是如何工作的？
这里有什么警告吗？
理论上可以在恒定的时间内找到答案吗？ 我的意思是，我们不是必须迭代这些位来计算？
计数位
无符号的32位整数u可以这样写：
u = a 31 * 2 31 + a 30 * 2 30 + ... + a 0 * 2 0
我们想要a 31 + a 30 + ... + a 0 。
让我们比较一下u >> k的值：
u >> 0 = a 31 * 2 31 + a 30 * 2 30 + ... + a 1 * 2 1 + a 0 * 2 0 u >> 1 = a 31 * 2 30 + a 30 * 2 29 + ... + a 1 * 2 0 u >> 2 = a 31 * 2 29 + a 30 * 2 28 + ... ... u >> 29 = a 31 * 2 2 + a 29 * 2 1 + ... u >> 30 = a 31 * 2 1 + a 30 * 2 0 你>> 31 = 31 * 2 0
我们将通过以下公式计算比特数：
u >> 0 - u >> 1 - u >> 2 - ... - u >> 31 = p
让我们看看为什么这样有效：
u >> 0 - u >> 1 - u >> 2 - ... - u >> 31 = u >> 0 - (u >> 1 + u >> 2 + ... + u >> 31) = u - q
q的价值是多少？ 让我们一点一点地计算它，看看上面的u >> k的值。 对于a 31 ，它是：
a 31 * 2 30 + a 31 * 2 29 + ...... = a 31 *（2 30 + 2 29 + ...） = a 31 *（2 31 - 1）
或者a 30 ：
一个30 * 2 29 +一个30 * 2 28 + ...... = a 30 *（2 29 + 2 28 + ...） = 30 *（2 30 - 1）
我们发现： q = a 31 * (2 31 - 1) + a 30 * (2 30 - 1) + ...
因此
你 - q = a 31 * 2 31 - a 31 *（2 31 - 1）+ ......
= a 31 + a 30 + ... + a 0
计算3位块中的位
这个算法从做同样的事情开始，但是以3比特的块为单位：
u >> 0 = AaBbbCccDddEeeFffGggHhhIiiJjjKkk (each letter is a bit) u >> 1 & 033333333333 = A Bb Cc Dd Ee Ff Gg Hh Ii Jj Kk (blank = zero) u >> 2 & 011111111111 = BCDEFGHIJK
根据这些差异，通过上述算法， uCount中的每个八位字节包含在u相应八位字节中设置的位数。
uCount = αβγδεζηθικλ (each greek letter is an octet) uCount >> 3 = αβγδεζηθικ
所以uCount + (uCount >> 3)是(λ+κ) * 2 0 + (κ+ι) * 2 3 + (ι+θ) * 2 6 + ...
通过与0o30707070707 ，我们将每隔一个八位字节屏蔽掉，这样我们只计算每对一次：
r =（λ+κ）* 2 0 +（ι+θ）* 2 6 +（η+ζ）* 2 12 + ... =（λ+κ）* 64 0 +（ι+θ）* 64 1 +（η+ζ）* 64 2 + ...
这是一个base-64数，我们想总结基数为64的数字得到α+β+γ+δ+ε+ζ+η+θ+ι+κ+λ ，这是我们的最终结果。 为此，我们计算其base-64 数字根 ：知道结果永远不会大于32，我们只需将数字模数为63。
由于类型中的位数是常数，因此迭代这些位是恒定时间。
因此，检查一个比特的掩码并且针对目标值中的每个比特移位的解决方案实际上是O(1) （例如，其中常数是32）。
最快的方法是使用popcnt指令。 您通常可以通过编译器内部访问它。 您的解决方案在缺少此指令的平台上非常有用。
并行计数位设置显示了如何完成。 该方法可用于8位，16位，32位，64位，128位等位字，但计算中使用的常数会发生变化。
当我们说这个操作是O（1）时，我们的意思是它可以在恒定的时间内完成而不管字大小。 以天真的方式对比特进行计数是比特数的O（n）。
实际上，当处理器本身可以使用字大小时，这只是O（1）。
至于它如何工作，它使用“魔术数字”。 有关说明，请参阅此新闻组post 。