计算第 i 位设置的 1 和 N（含）之间的数字

Question

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

天真的线性时间解决方案是从 1 迭代到 N 并且对于每个数字，看看它是否有它的 i第位设置。

稍微好一点的方法是，因为对于已知的 2 次方（比如 2^x），2^x−1 数字将设置第 i 位直到数字 2^x − 1，其中 0 ≤ i < x。因此计算所有数字，其第 i 位设置从 (N − 2^x)，其中 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⌋个完整的往返的第 k 位，每次这样的往返都会导致 2^k设置位。我们将这些条目分组在水平条之前。

进而还有N + 1 - 2^k+1×⌊N/2^k+1⌋ 条目在单杠下。我们确定这 less 比 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 上限的值）。

计算第 i 位设置的 1 和 N（含）之间的数字

Counting the numbers between 1 and N (inclusive) where the i-th bit is set

algorithm

bit-manipulation

bitmask