计算二进制表示形式正好需要数字1的数字

你认为有一种更有效的方法是对的。

让我们从一个稍微简单的子问题开始。缺少一些真正聪明的 insights,我们需要能够找到 [n+1, 2n] 那就是 k 二进制表示中设置的位。到 简而言之,我们称这些整数为“权重”- k “整数(有关此术语的动机,请查阅 Hamming weight ). 我们可以 立即简化我们的计数问题:如果我们可以计算所有重量- k 中的整数 [0, 2n] 我们可以计算所有重量- k 中的整数 [0, n] ,我们可以减去一个计数 从另一个得到重量的数量- k 中的整数 [n+1,2n] .

所以一个明显的子问题是计算重量- k 整数有 在时间间隔内 [0,n] ,对于给定的非负整数 k 和 n .

解决这类问题的标准方法是寻找一种方法 将其分解为同类较小的子问题;这是 通常被称为 dynamic programming . 在这种情况下,有一种简单的方法 这样做:考虑中的偶数 [0,n] 和中的奇数 [0,n] 分别地每偶数 m 在里面 [0,n] 重量与 m/2 (因为除以2,我们所做的就是去掉一个零 位)。同样,每个奇数 m级 重量正好比 重量 (m-1)/2 . 考虑到适当的基本情况 导致以下递归算法(在本例中是用Python实现的, 但它应该很容易翻译成任何其他主流语言)。

def count_weights(n, k):
    """
    Return number of weight-k integers in [0, n] (for n >= 0, k >= 0)
    """
    if k == 0:
        return 1  # 0 is the only weight-0 value
    elif n == 0:
        return 0  # only considering 0, which doesn't have positive weight
    else:
        from_even = count_weights(n//2, k)
        from_odd = count_weights((n-1)//2, k-1)
        return from_even + from_odd

这里有很大的错误空间,所以让我们测试一下我们的递归 针对效率较低但更直接(我希望更多)的算法 明显正确):

def weight(n):
    """
    Number of 1 bits in the binary representation of n (for n >= 0).
    """
    return bin(n).count('1')

def count_weights_slow(n, k):
    """
    Return number of weight-k integers in [0, n] (for n >= 0, k >= 0)
    """
    return sum(weight(m) == k for m in range(n+1))

比较这两种算法的结果看起来很有说服力:

>>> count_weights(100, 5)
11
>>> count_weights_slow(100, 5)
11
>>> all(count_weights(n, k) == count_weights_slow(n, k)
...     for n in range(1000) for k in range(10))
True

然而,我们的速度应该很快 count_weights 函数不能很好地扩展到 您需要的尺码:

>>> count_weights(2**64, 5)  # takes a few seconds on my machine
7624512
>>> count_weights(2**64, 6)  # minutes ...
74974368
>>> count_weights(2**64, 10)  # gave up waiting ...

但这里有动态编程的第二个关键思想:记忆! 也就是说,记录以前通话的结果,以防我们需要使用 他们又来了。结果是递归调用链 将 倾向于 重复打很多电话,所以记忆很有价值。在Python中,这是 通过 functools.lru_cache 室内装修设计师这是我们的新 版本 count\u权重 . 所有更改都是顶部的额外行:

@lru_cache(maxsize=None)
def count_weights(n, k):
    """
    Return number of weight-k integers in [0, n] (for n >= 0, k >= 0)
    """
    if k == 0:
        return 1  # 0 is the only weight-0 value
    elif n == 0:
        return 0  # only considering 0, which doesn't have positive weight
    else:
        from_even = count_weights(n//2, k)
        from_odd = count_weights((n-1)//2, k-1)
        return from_even + from_odd

现在再次对这些较大的示例进行测试,我们得到了结果 很 更快, 没有任何明显的延迟。

>>> count_weights(2**64, 10)
151473214816
>>> count_weights(2**64, 32)
1832624140942590534
>>> count_weights(5853459801720308837, 27)
356506415596813420

现在我们有了一种有效的计数方法,我们得到了一个反问题 求解:给定 k 和 m级 ,查找 n 因此 count_weights(2*n, k) - count_weights(n, k) == m . 这一步特别容易,因为 量 count_weights(2*n, k) - count_weights(n, k) 是单调的 随着增加 n (对于固定 k ),更具体地说 0 或 1 每一次 n 增加 1. . 我会留下这些证据的 事实告诉你,但这里有一个演示:

>>> for n in range(10, 30): print(n, count_weights(n, 3))
... 
10 1
11 2
12 2
13 3
14 4
15 4
16 4
17 4
18 4
19 5
20 5
21 6
22 7
23 7
24 7
25 8
26 9
27 9
28 10
29 10

这意味着我们保证能够找到解决方案。可能有多种解决方案,因此我们将力求找到最小的解决方案(尽管找到最大的解决方案也同样容易)。对分搜索为我们提供了一种粗糙但有效的方法。代码如下:

def solve(m, k):
    """
    Find the smallest n >= 0 such that [n+1, 2n] contains exactly
    m weight-k integers.

    Assumes that m >= 1 (for m = 0, the answer is trivially n = 0).
    """
    def big_enough(n):
        """
        Target function for our bisection search solver.
        """
        diff = count_weights(2*n, k) - count_weights(n, k)
        return diff >= m

    low = 0
    assert not big_enough(low)

    # Initial phase: expand interval to identify an upper bound.
    high = 1
    while not big_enough(high):
        high *= 2

    # Bisection phase.
    # Loop invariant: big_enough(high) is True and big_enough(low) is False
    while high - low > 1:
        mid = (high + low) // 2
        if big_enough(mid):
            high = mid
        else:
            low = mid
    return high

测试解决方案:

>>> n = solve(5853459801720308837, 27)
>>> n
407324170440003813446

让我们再检查一下 n :

>>> count_weights(2*n, 27) - count_weights(n, 27)
5853459801720308837

看起来不错。如果我们搜索正确,这应该是最小的 n 这很有效:

>>> count_weights(2*(n-1), 27) - count_weights(n-1, 27)
5853459801720308836

在 上面的代码和其他解决问题的方法,但我希望这能为您提供 起点。

OP评论说,他们需要在C语言中实现这一点,在C语言中,如果不使用外部库,就无法立即获得备忘录。这是 count\u权重 这不需要记忆。它是通过(a)在 count\u权重 所以同样 n 对于给定的 n ,的值 count_weights(n, k) 对于 全部的 k 其答案为非零。实际上,我们只是将备忘录移动到一个明确的列表中。

注意:如前所述,下面的代码需要Python 3。

def count_all_weights(n):
    """
    Return frequencies of weights of all integers in [0, n],
    as a list. The kth entry in the list gives the count
    of weight-k integers in [0, n].

    Example
    -------
    >>> count_all_weights(16)
    [1, 5, 6, 4, 1]

    """
    if n == 0:
        return [1]
    else:
        wm = count_all_weights((n-1)//2)
        weights = [wm[0], *(wm[i]+wm[i+1] for i in range(len(wm)-1)), wm[-1]]
        if n % 2 == 0:
            weights[bin(n).count('1')] += 1
        return weights

调用示例:

>>> count_all_weights(7590)
[1, 13, 78, 286, 714, 1278, 1679, 1624, 1139, 559, 182, 35, 3]

即使对于较大的 n : count_all_weights(10**18) 在我的机器上不到半毫秒。

现在,对分搜索将像以前一样工作,取代对 count\u权重(n,k) 具有 count_all_weights(n)[k] (对于 count_weights(2*n, k) ).

最后,另一种可能性是打破间隔 [0,n] 变成一系列越来越小的子区间,其中每个子区间的长度都是二的幂。例如,我们会打破间隔 [0, 101] 进入 [0, 63] , [64, 95] , [96, 99] 和 [100, 101] . 这样做的好处是我们可以很容易地计算出重量- k 通过计算组合,这些子区间中的任何一个子区间中都有整数。例如,在 [0, 63] 我们有所有可能的6位组合,所以如果我们在寻找权重为3的整数,我们知道其中肯定有6-choose-3(即20个)。并且在 [64, 95] ,我们知道每个整数都以 1. -位,然后排除 1. -位我们有所有可能的5位组合,所以我们再次知道在这个区间中有多少个整数具有任何给定的权重。

应用这个想法,这里有一个完整、快速、一体式的函数,可以解决您原来的问题。它没有递归和记忆。

def solve(m, k):
    """
    Given nonnegative integers m and k, find the smallest
    nonnegative integer n such that the closed interval
    [n+1, 2*n] contains exactly m weight-k integers.

    Note that for k small there may be no solution:
    if k == 0 then we have no solution unless m == 0,
    and if k == 1 we have no solution unless m is 0 or 1.
    """
    # Deal with edge cases.
    if k < 2 and k < m:
        raise ValueError("No solution")
    elif k == 0 or m == 0:
        return 0
    k -= 1

    # Find upper bound on n, and generate a subset of
    # Pascal's triangle as we go.
    rows = []
    high, row = 1, [1] + [0] * k
    while row[k] < m:
        rows.append((high, row))
        high, row = high * 2, [1, *(row[i]+row[i+1] for i in range(k))]

    # Bisect to find first n that works.
    low = mlow = weight = 0
    while rows:
        high, row = rows.pop()
        mmid = mlow + row[k - weight]
        if mmid < m:
            low, mlow, weight = low + high, mmid, weight + 1
    return low + 1