algorithm - 范围内的快速位计数

Question

我需要找到解决这个问题的算法:
求 [x,y] 范围内数字中所有正数位的总和。
警告:x 和 y 可以很大(从 1 到 10^20)。
感谢您的帮助。

Answer 1

查看具体示例以识别模式可能具有指导意义。例如，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)

... 其中 numBits 给出了单个数字中 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 次左右。