algorithm - 计算第 i 位设置的 1 和 N(含)之间的数字

Question

我想计算 1 到 N 之间有多少整数设置了第 i 位。例如，如果 N = 10 且 i = 0，则结​​果应为 5(因为 1 = 0001₂, 3 = 0011< sub>2、5 = 0101₂、7 = 0111₂ 和 9 = 1001₂ 每个位都有一个 1 0).

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

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

是否有恒定时间的解决方案？

Answer 1

让我们先来看一个例子。如果我们设置 n=10，然后查看第二位，那么从右边开始 k=1，我们会看到:

00<b>0</b>0    0
00<b>0</b>1    0
00<b>1</b>0    1
00<b>1</b>1    2
01<b>0</b>0    2
01<b>0</b>1    2
01<b>1</b>0    3
01<b>1</b>1    4
----
10<b>0</b>0    4
10<b>0</b>1    4
10<b>1</b>0    5

我们在这里看到 ⌊N/2^k+1⌋ 个完整的 round trips k 位，每次这样的往返都会产生 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

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

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 是上界的值)。