algorithm - 范围内整数的补码二进制表示中 1 的个数

Question

此问题来自 2011 Codesprint (http://csfall11.interviewstreet.com/):

计算机科学的基础之一是了解数字如何用 2 的补码表示。想象一下，您使用 32 位以 2 的补码表示形式写下 A 和 B 之间的所有数字。你总共会写下多少个 1？输入:第一行包含测试用例数量 T (<1000)。接下来的 T 行中的每一行都包含两个整数 A 和 B。输出:输出 T 行，一个对应于每个测试用例。约束:-2^31 <= A <= B <= 2^31 - 1

示例输入:3个-2 0-3 4-1 4示例输出:639937

解释:对于第一种情况，-2 包含 31 个 1，后跟一个 0，-1 包含 32 个 1，0 包含 0 个 1。因此总数为63。对于第二种情况，答案是 31 + 31 + 32 + 0 + 1 + 1 + 2 + 1 = 99

我意识到您可以利用 -X 中 1 的数量等于 (-X) = X-1 的补码中 0 的数量这一事实来加快搜索速度。该解决方案声称存在用于生成答案的 O(log X) 递归关系，但我不明白。解决方案代码可以在这里查看:https://gist.github.com/1285119

如果有人能解释一下这种关系是如何推导出来的，我将不胜感激!

Answer 1

好吧，没那么复杂...

单参数 solve(int a) 函数是关键。它很短，所以我将其剪切并粘贴到这里:

long long solve(int a)
{
 if(a == 0) return 0 ;
 if(a % 2 == 0) return solve(a - 1) + __builtin_popcount(a) ;
 return ((long long)a + 1) / 2 + 2 * solve(a / 2) ;
}

它仅适用于非负 a，它计算从 0 到 a 的所有整数中 1 的位数。

函数分为三种情况:

a == 0 -> 返回 0。显然。

a even -> 返回 a 中 1 的位数加上 solve(a-1)。也很明显。

最后一个案例很有趣。那么，我们如何统计1位从0到奇数a的个数呢？

考虑 0 到 a 之间的所有整数，并将它们分成两组:偶数组和偶数组。例如，如果 a 为 5，则您有两组(二进制):

000  (aka. 0)
010  (aka. 2)
100  (aka. 4)

和

001  (aka 1)
011  (aka 3)
101  (aka 5)

注意这两组必须有相同的大小(因为a是奇数并且范围是包含在内的)。要计算每组中有多少个 1 位，首先计算除最后一位以外的所有位，然后计算最后一位。

除最后几位外，所有内容如下所示:

00
01
10

...两个 组看起来都是这样。这里1的位数就是solve(a/2)。 (在这个例子中，它是从 0 到 2 的 1 位数。另外，回想一下 C/C++ 中的整数除法舍入 。)

第一组中的每个数字的最后一位为零，第二组中的每个数字的最后一位为零，因此这些最后的位为总数贡献了 (a+1)/2 一位。

因此递归的第三种情况是 (a+1)/2 + 2*solve(a/2)，适当转换为 long long 来处理a 为 INT_MAX 的情况(因此 a+1 溢出)。

这是一个复杂度为 O(log N) 的解决方案。要将其概括为 solve(a,b)，您只需计算 solve(b) - solve(a)，再加上处理负数的适当逻辑。这就是双参数 solve(int a, int b) 正在做的事情。