1

我需要找到解决这个问题的算法：
在 [x,y] 范围内的数字中找到所有正位的总和。
警告：x 和 y 可能非常大（从 1 到 10^20）。
感谢帮助。

4

1 回答 1

3

看一个具体的例子来识别模式可能是有益的。例如，20 到 25。这是它们的二进制表示：

20: 10100
21: 10101
22: 10110
23: 10111
24: 11000
25: 11001

按列查看，很明显最右边的列总是在 0 和 1 之间交替。由此我们可以得出结论，如果您的范围中有 N 个数字并且 N 是偶数，那么最右边的列中有 N/2 位。现在忽略最右边的列并尝试识别剩余位中的模式。

1010
1010
1011
1011
1100
1100

列表中的每个数字都只重复一次。转换为十进制，我们看到这些数字是1010 = 10, 1011 = 11, 1100 = 12。使用这两个观察结果，我们可以得出结论bitsInRange(20, 25) = (27 - 20 - 1) + 2*bitsInRange(10,12)。我们确定的两种模式对于任何偶数开始数和奇数结束数都是正确的，因此该公式可以推广为：

bitsInRange(X,Y) =
if X is even and Y is odd:
    (Y - X - 1) + 2*bitsInRange(X/2, (Y-1)/2)

但是，如果我们有一个奇数的起始编号或一个偶数的结束编号怎么办？上面的公式不适用于那些，因为我们确定的两种模式对于这些类型的数字并不完全相同。您可以尝试为偶数和奇数的每种可能组合编写单独的公式，但这种方式是危险的并且充满了Fencepost Errors。如果您利用这些关键属性，您将拥有更轻松的时间：

bitsInRange(X, Y) = bitsInRange(X, Y-1) + numBits(Y)
bitsInRange(X, Y) = bitsInRange(X+1, Y) + numBits(X)

... wherenumBits给出1单个数字中的位数。

现在我们可以为偶数和奇数范围的每个可能组合编写一个递归公式。（顺便说一下，我们还需要一个基本案例）

function bitsInRange(X,Y):
    if X == Y:
        return numBits(X)
    if X is odd:
        return bitsInRange(X+1, Y) + numBits(X)
    if Y is even:
        return bitsInRange(X, Y-1) + numBits(Y)
    return (Y - X - 1) + 2*bitsInRange(X/2, (Y-1)/2)

因为最终案例将问题空间切成两半，而所有其他案例都迅速将问题转化为最终案例，所以整个公式具有对数复杂度。如果您想获得像 [1, 10^20] 这样的大范围内的位，这很好。即使是这样的巨大数字，bitsInRange也只会运行大约 200 次左右。

于 2012-06-21T19:56:32.673 回答