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

Question

给定一个正整数“l”和“r”。找到最小的数字“n”，这样l

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

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

时间复杂度：O（对数（n））

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

约束条件:

一

以下是我的代码-

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

这是对数方法的想法。

它背后的主要概念如下：要减少一个数字的二进制表示中的集位数，同时可以将其增加到上限，则必须在原始数字中添加一个等于最低有效集位数的值的数字。此操作将设置位推到左侧。当两个设置位相邻时，将等于最低有效位的值相加，可以有效地将两个设置位数减少为一个设置位，同时将其推到左侧。

given 01100
add   00100
gives 10000

another example:
given 00101
add   00001
gives 00110
add   00010
gives 01000

上述概念激励了以下算法：

def num_of_set_bits(num):
  res = 0
  while num:
    res += 1
    num = (num - 1) & num
  return res

def min_set_bits(low, high):
  res = num_of_set_bits(low)

  while low < high:
    low += (low & -low) # two's complement; unsets all except for the LSB
    if low <= high:
      res = min(res, num_of_set_bits(low))
  return res

时间复杂度：O（对数高 * 最大设定位数） 空间复杂度：O（1）

可以对算法进行一些优化。例如，如果低电平的设置位数为 1，则只返回 1。或者，我们可以查看LSB的左侧，如果未设置该位，我们将不会再次计算位，因为该操作不会减少位数。进一步的优化是，当我们看到LSB的左位被设置时，自动将位数减少一。我们不再计算比特数了。这有效地将时间复杂度降低到 O（对数高）。

最后需要注意的是:我对这个算法不是100%确定，因为我还没有在其他地方读到过它。我自己想出来的。我没有充分的工作证明，也没有反例。直觉上，它看起来对我是正确的，但是直觉误导了我很多次。任何反馈或反例，不胜感激。

Answer 2

只是为了好玩，这里有一个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"))

现在，我们可以仔细检查< code >最少设置比特混淆和< code >最少设置比特强力对于一系列输入给出相同的结果:

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()

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

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

例如，如果low=1641和high=1749，则二进制扩展为0b11001101001和0b110110101。公共初始部分由第一个（即最重要的）三位组成：110。在前三位之后，low的下一位是0，high的下一位是1。low和high之间的每个整数也必须以110开头，在同一位置，我们后面的数字是0b11010000000或1664。

上面函数的前三行查找公共部分，0b11000000或1536decimallow^high查找lowandhigh之间不匹配的位，然后 调用告诉我们非匹配部分的长度（我也将其称为尾随部分）。然后<代码>-1

对于其余的位，我们只想将 low 的尾随部分（在函数中match_low）替换为下一个更高的 2 次幂，这就是 1

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