我知道以前有人问过这个问题，但我正在查看此处列出的这个特定解决方案：
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 = a31 * 231 + a30 * 230 + ... + a0 * 20
我们想要 的值。a31 + a30 + ... + a0
让我们比较 的值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 u >> 31 = a 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上面的值。对于，它是：a31
31 * 2 30 + 31 * 2 29 + ... = 31 * (2 30 + 2 29 + ...) = 一个31 * (2 31 - 1)
或为：a30
一个30 * 2 29 + 一个30 * 2 28 + ... = 30 * (2 29 + 2 28 + ...) = 30 * (2 30 - 1)
我们发现：q = a31 * (231 - 1) + a30 * (230 - 1) + ...
因此
u - q = a 31 * 2 31 - a 31 * (2 31 - 1) + ...
= 一个31 + 一个30 + ... + 一个0
这个算法从做同样的事情开始，但在 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 = B C D E F G H I J K
取这些差异，通过上述算法，每个八位字节uCount包含在相应八位字节中设置的位数u。
uCount = αβγδεζηθικλ (each greek letter is an octet)
uCount >> 3 = αβγδεζηθικ
uCount + (uCount >> 3)也是_(λ+κ) * 20 + (κ+ι) * 23 + (ι+θ) * 26 + ...
通过与 进行 AND 运算0o30707070707，我们屏蔽了所有其他八位位组，因此我们只对每一对计数一次：
r = (λ+κ) * 2 0 + (ι+θ) * 2 6 + (η+ζ) * 2 12 + ... = (λ+κ) * 64 0 + (ι+θ) * 64 1 + (η+ζ) * 64 2 + ...
这是一个 base-64 数字，我们想将 base-64 数字相加得到α+β+γ+δ+ε+ζ+η+θ+ι+κ+λ，我们的最终结果。为此，我们计算它的 base-64数字根：知道结果永远不会大于 32，我们只需将数字取模 63。
因此，检查一位掩码并针对目标值中的每一位进行移位的解决方案确实是O(1)（例如，常数为 32）。
最快的方法是 popcnt 指令。您通常可以通过编译器内在函数访问它。您的解决方案在缺少此说明的平台上可能很有用。