algorithm - 在给定范围内设置位为 MINIMUM 的最小数

Question

给定一个正整数“l”和“r”。找到最小的数字“n”，使得 l <= n <= r 并且设置位的数量(二进制表示中“1”的数量)尽可能MINIMUM。

本文:https://www.geeksforgeeks.org/smallest-number-whose-set-bits-maximum-given-range/给出具有最大设置位的最小数字.但我需要 [l, r] 中具有最小设置位的最小数字。

我们可以在线性时间内简单地做到这一点。但是，我正在寻找一种优化方法，它接受——

时间复杂度:O(log(n))

辅助空间:O(1) 或 O(n)

约束:

1 <= l <= r <= 10^18

下面是我的代码--

import math

l, r = map(int, input().split())
if l <= 2: print(l)
else:
    x1 = math.log(l, 2)
    x2 = math.log(r, 2)
    x3 = int(math.pow(2, math.ceil(x1)))
    
    if x1 == x2 or x3 > r:
       cnt = 32
       for i in range(l, r+1):
            s = bin(i).replace("0b", "")
            cnt1 = s.count('1')
            if cnt1 < cnt:
               cnt = cnt1
               ans = i
           
    else:
        ans = x3
        
    print(and)

我需要优化上面python代码中的for循环。谢谢。

Answer 1

只是为了好玩，这是一个用 Python 编写的快速单行解决方案(嗯，两行，包括 def ，但所有有趣的东西都在一行中)。我将进一步解压它。

def fewest_set_bits_obfuscated(l, h):
    return (h:=(l:=l-1)&-1<<(l^h).bit_length())|1<<(l^h).bit_length()

示例用法:

>>> fewest_set_bits_obfuscated(617, 725)
640

在我们尝试解释上面发生的事情之前，让我们检查一下上面的代码是否确实给出了正确的答案。这是一个显然正确但效率低下的算法(尽管仍然是单行算法)来计算 [l, h] 范围内设置位数最少的第一个值。它使用 int.bit_count 方法，这是 Python 3.10 中的新方法:

def fewest_set_bits_brute_force(l, h):
    return min(range(l, h+1), key=int.bit_count)

如果您没有可用的 Python 3.10，这里有一个更慢的版本，它手动计算 1 位:

def fewest_set_bits_brute_force(l, h):
    return min(range(l, h+1), key=lambda n: bin(n).count("1"))

现在我们可以仔细检查 fewest_set_bits_obfuscated 和 fewest_set_bits_brute_force 对于一系列输入给出相同的结果:

MAX = 1000
for high in range(1, MAX+1):
    for low in range(1, high+1):
        ans_obfuscated = fewest_set_bits_obfuscated(low, high)
        ans_brute_force = fewest_set_bits_brute_force(low, high)
        assert ans_obfuscated == ans_brute_force, f"failed for {low}, {high}"

上面的代码将花费一些时间来运行(在我的笔记本电脑上大约需要 41 秒)，但它应该会在没有任何 assert 失败的情况下完成。

现在是解压原始单线解决方案的时候了。首先，让我们稍微重写一下该解决方案:

def fewest_set_bits_deobfuscated(low, high):
    low -= 1
    non_matching_length = (low ^ high).bit_length()
    common = low & (-1 << non_matching_length)
    match_low = low ^ common
    return common | 1 << match_low.bit_length()

在这里，我们执行与单行版本完全相同的操作，顺序完全相同，但我们重命名了参数，为一些中间值命名，并解压缩了:= “海象”运算符。

这里的主要思想是，如果您查看 low 和 high 的二进制扩展，这些二进制扩展的某些初始部分是匹配的；在最初的部分之后，扩展出现分歧。我们的结果必须从 low 和 high 具有的相同初始部分开始，然后我们可以通过在正确位置再添加一个 1 位来简单地填充其余部分。

例如，如果 low=1641 和 high=1749 则二进制扩展为 0b11001101001 和 0b11011010101 。公共(public)初始部分由前三位(即最高有效位)组成:110。在前三位之后，low 的下一位是 0 ，high 的下一位是 1 。low 和 high 之间的每个整数也必须以 110 开头，在相同的位置，我们之后的数字是 0b11010000000 或 1664。

上述函数的前三行找到公共(public)部分，即 0b11000000000 或十进制形式的 1536。 low ^ high 找到 low 和 high 之间不匹配的位，然后 bit_length() 调用告诉我们不匹配部分的长度(我也将其称为尾随部分)。然后 -1 << non_matching_length 为我们提供了一个掩码，可用于提取匹配部分 (common)。

对于剩余的位，我们只想将 low 的尾部部分(在函数中为 match_low)替换为下一个更高的 2 的幂，这就是 1 << match_low.bit_length() 给出的结果。

上面的不完全是正确的，因为我们真正想要做的是找到大于或等于 low 的尾部部分的下一个 2 的幂.但事实证明，计算下一个 严格 大于 low 尾部的 2 的幂要稍微容易一些。因此，我们在函数的开头通过递减 low 进行补偿，因此我们实际上是在半开区间 (low, high] 中寻找解决方案。