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

我想计算1到N之间有多少个整数的第I位集例如，如果N=10和i=0，则结果应为5（因为1=00012、3=00112、5=01012、7=01112和9=10012在位0处各有1）。
简单的线性时间解是从1到n迭代，对于每个数字，看看它是否有第i位集。
一个稍微好一点的方法是，因为对于已知的2次方（比如2x），2x-1数字的第i位将被设置为数字2x-1，其中0≤i有恒定时间解吗？

最佳答案

让我们先看一个例子如果我们设置了n=10，然后再看第二位，那么从右边的k=1，我们会看到：

这里我们看到第k位有n/2k+1全往返，每一个这样的往返都产生2k个设置位。我们把这些条目放在横条的前面。
此外，水平条下还有N+1-2K+1×N/2K+1条目。我们肯定这是小于2K的，因为否则N/2K会高出一个。前2k-1项具有0作为选定位，而其余位（最多2k-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是上界的值）。

关于algorithm - 计算设置第i位的1到N(含)之间的数字，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/56417337/