在给定范围内设置位为 MINIMUM 的最小数
Smallest number whose set bits are MINIMUM in a given range
给定一个正整数“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))
辅助space：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循环。
谢谢。
这是对数方法的想法。
其背后的主要概念如下：要减少数字的二进制表示中的设置位数，同时可以将其增加到上限，您必须添加一个等于最小值的数字significant set bit 为原来的数字。此操作将设置位推向左侧。当2个设置位相邻时，将等于最低有效位的值相加有效地将2个设置位减少为一个设置位，同时将其向左推。
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(log high * num of max set bits)
Space 复杂度：O(1)
可以对算法进行一些优化。比如low的设置位数是1，就return一个。或者，我们可以查看 LSB 的左侧，如果该位未设置，我们将不会再次计算这些位，因为该操作不会减少位数。进一步的优化是当我们看到 LSB 的第 th 左边位被设置时自动将位数减少一位。我们不再计算位数。这有效地将时间复杂度降低到 O(log high).
最后要注意一点：我对这个算法不是 100% 肯定，因为我还没有在某个地方读过它。我自己想出来的。我没有完整的工作证明，也没有反例。直觉上，它对我来说看起来是正确的，但直觉误导了我很多次。欢迎任何反馈或反例。
只是为了好玩，Python 中有一个快速的 one-line 解决方案（嗯，两行，包括 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
在我们尝试解释上面发生的事情之前，让我们检查一下上面的代码是否确实给出了正确的答案。这是一个 obviously-correct 但效率低下的算法（尽管仍然是 one-liner）来计算 [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 失败的情况下完成。
现在是解压原始 one-line 解决方案的时候了。首先，让我们稍微重写一下该解决方案：
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()
这里我们执行与 one-line 版本完全相同的操作，顺序完全相同，但我们重命名了参数，为一些中间值命名，并解包:=“海象”运算符的使用。
这里的主要思想是，如果您查看 low 和 high 的二进制展开式，就会发现这些二进制展开式的某些初始部分是匹配的；在最初的部分之后，扩展出现分歧。我们的结果必须从 low 和 high 具有的相同初始部分开始，然后我们可以通过在正确位置再添加一个 1 位来简单地填充其余部分。
例如，如果 low=1641 和 high=1749，则二进制扩展为 0b11001101001 和 0b11011010101。公共初始部分由前三位（即最高有效位）组成：110。在前三位之后，low 的下一位是 0，high 的下一位是 1。
low 和 high 之间的每个整数也必须在相同的位置以 110 开头，我们之后的数字是 0b11010000000 或 1664。
上面函数的前三行找到公共部分，0b11000000000，或十进制的 1536。 low ^ high 在 low 和 high 之间找到 不 匹配的位，然后 bit_length() 调用告诉我们non-matching 部分（我也将其称为尾随部分）。然后 -1 << non_matching_length 给了我们一个掩码，可以用来提取匹配部分 (common).
对于剩余的位，我们只是想用下一个更高的2的幂替换low（函数中的match_low）的尾部，这就是1 << match_low.bit_length() 给出。
上面的完全不对，因为我们真正想做的是求下一个大于或等于[=的2的次方89=] low 的结尾部分。但事实证明，计算下一个 严格 大于 low 的尾随部分的 2 的次方要稍微容易一些。因此，我们在函数的开头通过递减 low 进行补偿，因此我们实际上是在 half-open 区间 (low, high].
中寻找解决方案
给定一个正整数“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))
辅助space：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循环。 谢谢。
这是对数方法的想法。
其背后的主要概念如下：要减少数字的二进制表示中的设置位数，同时可以将其增加到上限，您必须添加一个等于最小值的数字significant set bit 为原来的数字。此操作将设置位推向左侧。当2个设置位相邻时，将等于最低有效位的值相加有效地将2个设置位减少为一个设置位，同时将其向左推。
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(log high * num of max set bits) Space 复杂度：O(1)
可以对算法进行一些优化。比如low的设置位数是1，就return一个。或者，我们可以查看 LSB 的左侧，如果该位未设置，我们将不会再次计算这些位，因为该操作不会减少位数。进一步的优化是当我们看到 LSB 的第 th 左边位被设置时自动将位数减少一位。我们不再计算位数。这有效地将时间复杂度降低到 O(log high).
最后要注意一点：我对这个算法不是 100% 肯定，因为我还没有在某个地方读过它。我自己想出来的。我没有完整的工作证明，也没有反例。直觉上，它对我来说看起来是正确的，但直觉误导了我很多次。欢迎任何反馈或反例。
只是为了好玩，Python 中有一个快速的 one-line 解决方案（嗯，两行，包括 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
在我们尝试解释上面发生的事情之前，让我们检查一下上面的代码是否确实给出了正确的答案。这是一个 obviously-correct 但效率低下的算法（尽管仍然是 one-liner）来计算 [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 失败的情况下完成。
现在是解压原始 one-line 解决方案的时候了。首先，让我们稍微重写一下该解决方案：
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()
这里我们执行与 one-line 版本完全相同的操作，顺序完全相同，但我们重命名了参数，为一些中间值命名，并解包:=“海象”运算符的使用。
这里的主要思想是，如果您查看 low 和 high 的二进制展开式，就会发现这些二进制展开式的某些初始部分是匹配的；在最初的部分之后，扩展出现分歧。我们的结果必须从 low 和 high 具有的相同初始部分开始，然后我们可以通过在正确位置再添加一个 1 位来简单地填充其余部分。
例如，如果 low=1641 和 high=1749，则二进制扩展为 0b11001101001 和 0b11011010101。公共初始部分由前三位（即最高有效位）组成：110。在前三位之后，low 的下一位是 0，high 的下一位是 1。
low 和 high 之间的每个整数也必须在相同的位置以 110 开头，我们之后的数字是 0b11010000000 或 1664。
上面函数的前三行找到公共部分，0b11000000000，或十进制的 1536。 low ^ high 在 low 和 high 之间找到 不 匹配的位，然后 bit_length() 调用告诉我们non-matching 部分（我也将其称为尾随部分）。然后 -1 << non_matching_length 给了我们一个掩码，可以用来提取匹配部分 (common).
对于剩余的位，我们只是想用下一个更高的2的幂替换low（函数中的match_low）的尾部，这就是1 << match_low.bit_length() 给出。
上面的完全不对，因为我们真正想做的是求下一个大于或等于[=的2的次方89=] low 的结尾部分。但事实证明，计算下一个 严格 大于 low 的尾随部分的 2 的次方要稍微容易一些。因此，我们在函数的开头通过递减 low 进行补偿，因此我们实际上是在 half-open 区间 (low, high].