以下函式確定將整數 A 轉換為整數 B 所需翻轉的位數。我已經通過不同的方法解決了它，但是當我閱讀此解決方案時，我不明白它。它顯然有效，但我的問題是為什么？
def bit_swap_required(a: int, b: int) -> int:
count, c = 0, a ^ b
while c:
count, c = count 1, c & (c - 1)
return count
我明白我們為什么這樣做a^b。它在我們需要翻轉的每個地方都給了我們一個“1”。但是，c & (c-1)反復做如何給你數字中“1”的確切數量？
uj5u.com熱心網友回復：
c - 1取消設定二進制表示中的最低有效位c并將所有未設定的位設定到該位的右側。
當您二進制并有效c - 1地c取消設定最低有效設定位和最低有效設定位右側的所有位時。換句話說，最不重要的設定位c及其右側的所有內容都變為零。
你把它算作一個，這是正確的。因為它只是一組位形式a ^ b。
現在，您繼續此操作直到c變為零，運算元是設定位的數量，其中和c之間的不同位的數量。ab
舉一個例子，說明c - 1對 的二進制表示有什么作用c：
c = 6, in binary 110
c-1 = 5, in binary 101
(c-1) & (c) = 110 & 101 = 100
The above is one iteration of the loop
Next iteration
c = 4, in binary 100
c-1 = 3, in binary 011
(c-1) & (c) = 100 & 101 = 0
以上成功統計了6中設定的位數。
與在每次迭代中右移數字并檢查是否設定了最低有效位相比，此優化可幫助您改進演算法。在前一種情況下，您在最高有效設定位所在的位置數進行操作。假設 2 的冪，2^7，你迭代 8 次，直到數字變為零。使用優化的方法時，您可以根據設定的位數進行迭代。對于 2^7 來說，這只是一次迭代。
uj5u.com熱心網友回復：
從代碼的結構，你可以猜到c & (c-1)有一個1小于c，即使沒有研究運算式
實際上，減法會從右邊1翻轉所有0位（有借位），直到最右邊1包含在內。因此，如果您bitwise and使用c，則只有最右邊的那個會1消失。
例如 c = 1001010 100 -> c-1 = 1001010 011 -> c & (c-1) = 1001010 0 00。
接下來，c = 10010 10000 -> c-1 = 10010 01111 -> c & (c-1) = 10010 0 0000。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/419806.html
標籤：
上一篇：計數排序不排序最后一個元素C
下一篇：鏈表迭代