algorithm - 计算 1 和 N(含)之间的数字,其中设置了第 i 位
问题描述
我想计算 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 迭代到N,并且对于每个数字,查看它是否设置了第i个位。
更好的方法是,因为对于 2 的已知幂(例如 2 x),2 x -1个数字的第i位将设置为数字 2 x - 1,其中 0 ≤ i < x . 因此,从 ( N − 2 x ) 开始计算具有第i位集合的所有数字,其中N是直到我们试图找到所有具有第i位集合的数字的数字,并且 2 x是 2 的最接近的幂对于数字N。这种方法减少了迭代次数,但仍然是一种线性时间解决方案,并且在某些情况下对于更大的数字可能非常无用。
有恒定时间的解决方案吗?
解决方案
我们先来看一个例子。如果我们设置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个条目具有选定位,而其余位(最多2 k-1个条目)具有选定位。0
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是上限的值)。
推荐阅读
- php - 如何显示来自 sqlite db 和动画的最新数据以查看更多信息?
- reactjs - React Select 选择后保留输入值
- swift - Swift 5 中的自定义 TEST 预处理器宏
- phabricator - 是否有 API 可以获取差异修订的审核状态?
- reactjs - 在 React 组件中使用 document.getElementById() 是否可以接受?
- javascript - 如何按值比较两个表
- kql - 如何在操作员日期时间变量之间调用
- verilog - “分配”操作中的操作优先级?
- bash - 在 RedHat 上的 bash 脚本中设置新用户的密码
- xslt - XSLT 将每第 n 个项目分组到新组中