计算设置 i 位的 1 到 N(含)之间的数字

Question

我想计算 1 到N之间设置了第i位的整数数量。例如，如果N = 10 且i = 0，则结果应为 5(因为 1 = 0001 2、3 = 0011 2、5 = 0101 2、7 = 0111 2 和 9 =       1001_{2 在}位 0处各有一个 1)。 

朴素线性时间解决方案是从 1 迭代到N，对于每个数字，查看它是否设置了第i位。

一个稍微好一点的方法是，因为对于 2 的已知幂(例如 2 x)，2^x−1数字将设置其第 i 位，直到数字 2^x − 1，其中 0 ≤ i <&nbsp;^x。因此，计算所有数字的第 i 位集从 (N − 2 x) 开始，其中N 是数字，直到我们寻求找到所有设置了第i位的数字，2^x是数字N最接近的 2 的幂。这种方法减少了迭代次数，但仍然是一种线性时间解决方案，在某些情况下对于更高的数字可能非常无用。

有恒定时间的解决方案吗？

Answer 1

我们先来看一个例子。如果我们设置n=10，我们看第二位，所以从右边k=1，我们看到：

0000    0
0001    0
0010    1
0011    2
0100    2
0101    2
0110    3
0111    4
----
1000    4
1001    4
1010    5

我们在这里看到，第k 位有⌊N/2^k+1⌋次完整的往返，每次这样的往返都会产生2^k个设置位。我们将这些条目分组在水平条之前。

此外，在水平条下仍然有 N + 1 - 2 k+1×⌊N/2^k+1⌋条目。我们确信这小于2^k，否则⌊N/2^k⌋会更高。前2 个^k-1条目0为选定位，而其余位(最多2^{个 k-1}条目)1为选定位。

因此，我们可以在 Haskell 中构造以下算法：

countBit k n = c1 +  max 0 (n + 1 - c0 - sk)
where sk = shiftL 1 k
c1 = shiftL (shiftR n (k+1)) k
c0 = shiftL c1 1

例如，对于k=1，我们得到以下计数：

Prelude Data.Bits> map (countBit 0) [0..32]
[0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13,14,14,15,15,16,16]
Prelude Data.Bits> map (countBit 1) [0..32]
[0,0,1,2,2,2,3,4,4,4,5,6,6,6,7,8,8,8,9,10,10,10,11,12,12,12,13,14,14,14,15,16,16]
Prelude Data.Bits> map (countBit 2) [0..32]
[0,0,0,0,1,2,3,4,4,4,4,4,5,6,7,8,8,8,8,8,9,10,11,12,12,12,12,12,13,14,15,16,16]
Prelude Data.Bits> map (countBit 3) [0..32]
[0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,8,8,8,8,8,8,8,8,9,10,11,12,13,14,15,16,16]
Prelude Data.Bits> map (countBit 4) [0..32]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,16]

所以对于n=10和k=1，我们得到了预期：

Prelude Data.Bits> countBit 0 10
5
Prelude Data.Bits> countBit 1 10
5

或者，我们可以用列k=3计算从0到12345(含)的数字的设置位数：

Prelude Data.Bits> countBit 3 12345
6170

或用于k=15和n=12'345'678'901'234'567'890

Prelude Data.Bits> countBit 15 12345678901234567890
6172839450617282560

对于n=123'456'789'012'345'678'901'234'567'890：

Prelude Data.Bits> countBit 15 123456789012345678901234567890
61728394506172839450617282560

我们在这里执行一些位移和减法，对于大数字，这些可以在O(log N)时间内完成(N是上限值)。