發現的2大於n

更大的最小功率我碰到一段代碼來尋找的2最小功率比32位的整數n ...發現的2大於n

n+=(n==0); 
n--; 
n|=n>>1; 
n|=n>>2; 
n|=n>>4; 
n|=n>>8; 
n|=n>>16; 
n++;

現在它是如何工作的更大？我試圖在印刷基地-2數N = 100的每一步之後，但它並沒有多大意義。它背後的邏輯是什麼？

來源

2013-01-12 sudeepdino008

我認爲這是一個32位整數？ – WhozCraig

它只適用於32位uint。順便說一句有[同樣的問題]（http://stackoverflow.com/questions/671815/what-is-the-fastest-most-efficient-way-to-find-the-highest-set-bit-msb-in-一個-I）：nextpow2是相同數量的，如果它是兩者的功率（'X＆（X - 1）== 0'）及其'MSB << 1'否則。 –

@WhozCraig是的。對不起，我編輯了這個問題。 – sudeepdino008

這段代碼用二進制1 s填充給定數字n的所有最低有效位，然後將結果增加1，實現要求的結果。例如，用於輸入101的位操作將產生111和增加通過1後它將成爲1000（8），這是確實的2最少的功率大於101（5）。

更新：實際上，這是對手動設置每個lsb位的簡單方法的優化。爲什麼這種優化達到相同的結果是在更廣泛的範圍內的另一個問題，超出了這個問題。

來源

2013-01-12 07:18:52 SomeWittyUsername

附加冰層的回答是：作爲解釋here，算法計算1 << (floor(log_2(n - 1)) + 1)。

來源

2013-01-12 07:21:27 filmor

實際上它發現的2大於或小於等於n最小功率和它的工作原理爲32位的無符號數。

第一行只是把0的方式相同，1（寫在有些混亂的方式）
第二行佔「等於」，如果一個數正好是二的冪，我們使它短一點。
接下來的幾行確保，所有下位設置爲1。首先，我們右移1移位和做邏輯或。其效果是，現在的最高位和位正下方被設置爲1。現在做同樣的具有2的移位使得前4位之一，等等。
最後我們有一個數字，比二的冪少一個，我們只需添加1

來源

2013-01-12 07:22:13 Henry

回答

相關問題