給定一個正整數“l”和“r”。找到最小的數字“n”，使得 l <= n <= r 并且設定位的數量（二進制表示中的“1”的數量）盡可能小。
這篇文章：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回圈。謝謝。
uj5u.com熱心網友回復：
這是對數方法的想法。
它背后的主要概念如下：要減少數字的二進制表示中設定位的數量，同時可以將其增加到上限，您必須將等于最低有效設定位的值的數字添加到原號碼。此操作將設定位推到左側。當 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) 空間復雜度：O(1)
可以對演算法進行一些優化。例如，如果設定的低位數為 1，則只回傳 1。或者，我們可以查看 LSB 的左側，如果該位未設定，我們將不再計算這些位，因為該操作不會減少位的數量。進一步的優化是當我們看到設定了 LSB 的第 th 位時，自動將位數減少 1。我們不再計算位數。這有效地將時間復雜度降低到O(log high).
最后要注意一點：我不是 100% 確定這個演算法，因為我沒有在某處讀過它。我自己想出來的。我沒有完全有效的證據，也沒有反例。直覺上，它看起來對我來說是正確的，但直覺誤導了我很多次。感謝任何反饋或反例。
uj5u.com熱心網友回復：
只是為了好玩，這是 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
在我們試圖解釋上面發生了什么之前，讓我們檢查一下上面的代碼是否確實給出了正確的答案。這是一個明顯正確但效率低下的演算法（盡管仍然是單行演算法），用于計算 range 中設定位數最少的第一個值[l, h]。它利用了int.bit_countPython 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 秒），但它應該在沒有任何asserts 失敗的情況下完成。
現在是時候解開原始的單行解決方案了。首先，讓我們稍微重寫一下該解決方案：
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()
在這里，我們以與單行版本完全相同的順序執行完全相同的操作，但我們重命名了引數，為一些中間值指定了名稱，并解開了:=“海象”的用途操作員。
這里的主要思想是，如果您查看lowand的二進制擴展high，則這些二進制擴展的某些初始部分是匹配的；在該初始部分之后，擴展發散。我們的結果必須以相同的初始部分是low與high有，然后我們就可以在剩下的只需添加一個更簡單地填寫1在正確的位置位。
例如， iflow=1641和high=1749then 的二進制展開是0b11001101001and 0b11011010101。公共初始部分由前三位（即最高有效位）組成：110. 在前三位之后，下一位 forlow是 a 0，下一位 forhigh是 a 1。和之間的每個整數low也high必須在同一位置以 , 開頭110，而我們后面的數字是0b11010000000, 或1664。
上述函式的前三行查找公共部分0b11000000000，或1536以十進制表示。low ^ high找到和之間不匹配的位，然后呼叫告訴我們不匹配部分的長度（我也將其稱為尾隨部分）。然后給我們一個可以用來提取匹配部分的掩碼 ( )。lowhighbit_length()-1 << non_matching_lengthcommon
對于剩余的位，我們只是想用下一個更高的 2 的冪替換low（match_low在函式中）的尾隨部分，這就是1 << match_low.bit_length()給出的結果。
上面的內容并不完全正確，因為我們真正想做的是找到大于或等于尾隨部分的2 的下一個冪low。但事實證明，計算嚴格大于 的尾隨部分的2 的下一個冪稍微容易一些low。正因為如此，我們在函式的開頭通過遞減來補償low，所以我們實際上是在半開區間內尋找解決方案(low, high]。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/420536.html
標籤：