获得第 n 个大于 0 且最多设置了 k 位的整数的快速方法是什么？

Question

我有一个系列，值大于 0，其中设置的位数不超过 k。

for instance, for `k = 2`

n    binary    value    bits_set
0    0000      0        0
1    0001      1        1
2    0010      2        1
3    0011      3        2
4    0100      4        1
5    0101      5        2
6    0110      6        2
7    1000      8        1
8    1001      9        2
9    1010      10       2
10   1100      14       2
... etc ...

对于给定的 k 值，是否有计算效率高的方法来查找系列中的第 n 项？

我所有的尝试都表现得很慢，我不知道如何有效地解决这个问题。

Answer 1

我知道这个问题被标记为 C#，很抱歉在 Python 中给出答案：

首先，我们将找到一种方法来计算可用 space 中特定位数的不同数字的数量。然后我们将找到一种对这些结果进行排序的方法。

将 f(b, s) 表示为从 b 集中构造一个正好有 s 位的数的方法数。

这里有递推关系。满足f(b, s) 的数要么是满足f(b-1, s) 且前面有0 的数，要么是满足f(b-1, s-1) 且前面有1 的数。因此 f(b, s) = f(b-1, s) + f(b-1, s-1).

一些基本案例填写table： f(b,0) 为 1 f(b,s) 为 1，其中 b = s

    10 9 8 7 6 5 4 3 2 1 0
24   . . . . . . . . . . 1
23   . . . . . . . . . . 1
22   . . . . . . . . . . 1
21   . . . . . . . . . . 1
20   . . . . . . . . . . 1
19   . . . . . . . . . . 1
18   . . . . . . . . . . 1
17   . . . . . . . . . . 1
16   . . . . . . . . . . 1
15   . . . . . . . . . . 1
14   . . . . . . . . . . 1
13   . . . . . . . . . . 1
12   . . . . . . . . . . 1
11   . . . . . . . . . . 1
10   1 . . . . . . . . . 1
 9   0 1 . . . . . . . . 1
 8   0 0 1 . . . . . . . 1
 7   0 0 0 1 . . . . . . 1
 6   0 0 0 0 1 . . . . . 1
 5   0 0 0 0 0 1 . . . . 1
 4   0 0 0 0 0 0 1 . . . 1
 3   0 0 0 0 0 0 0 1 . . 1
 2   0 0 0 0 0 0 0 0 1 . 1
 1   0 0 0 0 0 0 0 0 0 1 1

构建 table g(b, s) 也很有用，它表示有多少 b 位数字设置了 s 或更少的位。 g(b, s) = sum(i = 0 到 s) f(b, i)

所以我们现在可以回答有多少个数字正好是 24 中的 10 位，即 f(24, 10) = 1961256，我们可以回答有多少个数字最多为 10位设置为 24，即 f(24, 10) + f(24, 9) + f(24, 8) ... + f(24, 1) + f(24, 0) = g(24, 10 ) = 4540386

但是，如果问题是找到第 n 个数字，使得 24 位中最多有 10 个被设置，我们需要能够以有序的方式搜索这个 space。

首先要注意的是，任何第n位首为1的数都大于任何位首为1的数晚于n的数

这意味着我们可以找到每个数字的位置，只需设置一个位后跟 z 个零。这必然大于 g(z, max(z,10))。我们可以在这里进行优化并声明由于 10 位 space 中的所有数字都是合格的（它们不可能设置超过 10 位）然后第 n 个这样的数字 = n 对于所有 n <= 2^10.

如果 n > 2^10 (=> z > 10)，我们可以通过找到最大的 z_10 来搜索第一个设置位的位置，使得 g(z_10, 10 ) <= n。如果它实际上等于 n，我们就找到了答案，所以可以停止了。如果我们想要超高效，这甚至可以通过二进制搜索来完成！

否则，我们必须找到最大的z_9使得g(z_9, 9) <= n - g(z_10, 10)，然后是最大的z_8 这样 g(z_8, 8) <= n - g(z_10, 10) - g(z_9, 9) 等等，直到我们达到相等并回答问题。

在Python中：

class Memoize:
    def __init__(self, f):
        self.f = f
        self.memo = {}
    def __call__(self, *args):
        if not args in self.memo:
            self.memo[args] = self.f(*args)
        return self.memo[args]

def g(b, s):
    r = 0
    for i in range(0, s+1):
        r = r + f(b, i)
    return r

def f(b,s):
    if b == s:
        return 1
    if s == 0:
        return 1
    if b < s:
        return 0
    return f(b-1, s) + f(b-1, s-1)

def build(s, n, i):
    d = (24 - len(s))
    if n <= 2 ** i:
        return s + format(n, '0%db' % (d))
    for z in range(i, d+1):
        x = g(z, i)
        if x < n:
            continue
        if x == n:
            return s + format(2 ** z, '0%db' % (d))
        y = g(z-1, i)
        return build(s + format(1, '0%db' % (d-(z-1))),
                     n - y,
                     i - 1)

def solve(n):
    return build("", n-1, 10)

f = Memoize(f)
g = Memoize(g)

for n in range(1, 4540387):
    print("%07d: %s" % (n, solve(n)))

获得第 n 个大于 0 且最多设置了 k 位的整数的快速方法是什么？

What is a quick way to get the n'th integer > 0, that has at most k bits set?

c#

math

bits