c++ - 如何找到给定范围内的整数个数甚至设置位

Question

我想知道在给定范围内有多少个数字表示 x，假设 l 和 r，l < r，表示 x 的二进制表示中 1 的个数为偶数。有什么有效的方法可以找到它吗？

Answer 1

这是一个关键事实:

• 如果 n 是一个非负偶数数，则正好有一半小于 n 的非负整数具有偶校验和另一半有奇校验。 (“偶校验”表示二进制表示中的位数为偶数。)

假设我们需要计算 [l, r) 范围内具有某些属性 P 的整数的数量，并且我们知道如何为 l 为 0 的任何范围解决此问题。(“[l, r)”是“半开范围”:所有整数n，其中l≤n<r。这使得算术更容易。)然后我们只需要减去以解决 l≠0 的一般问题:COUNT[l,r) = COUNT[0,r) − COUNT[0,l).

第一个事实并没有完全告诉我们我们需要知道的一切，因为它甚至只适用于 n。但是如果 n 是奇数，n-1 是偶数，我们需要做的就是检查 n-1 本身的奇偶性，这是不在 [0,n-1] 范围内的额外数字。

将所有这些放在一起，如果我们有范围 [l, r)，我们计算计数如下:

• COUNT(0,l) 是 l/2 如果 l 是偶数，并且 (l- 1)/2+PARITY(l) 如果l是奇数
• COUNT(0,r) 是 r/2 如果 r 是偶数，并且 (r- 1)/2+PARITY(r) 如果r是奇数
• COUNT(l,r) 是 COUNT(0,r) − COUNT(0,l )

最后的计算最多需要两次奇偶校验计算，无论范围有多大，以及几次除法和一次减法。

如果这是一个数学网站，我可能会觉得有必要在一开始就证明关键事实中的断言，但由于这是 CS，我会满足于证明大纲。我们首先注意到，如果 i 是偶数，那么 PARITY(i) 和 PARITY(i+1) 是不同的(因为二进制表示仅最后一点不同)。相反，如果 i 是奇数，则 PARITY(i) 和 PARITY(i-1) 不同。现在，将 [0,n) 中的所有整数分成奇校验整数集和偶校验整数集，并考虑同态

f(i)⇒i+1 如果i是偶数；
f(i)⇒i−1 如果i是奇数；

f 在 [0,n) 的两个子集之一上的图像是另一个子集，因为 f 的奇偶性(i) 不同于 i 的奇偶校验。所以这两个子集的大小相同。