提取一個整數的最右邊N位

在昨天的Code Jam資格回合http://code.google.com/codejam/contest/dashboard?c=433101#s=a&a=0中，有一個叫Snapper Chain的問題。從比賽分析中，我發現問題需要翻閱一些東西，比如提取整數的最右邊的N位，並檢查它們是否都是1.我看到一個參賽者（Eireksten）代碼，它執行如下操作：提取一個整數的最右邊N位

(((K&(1<<N)-1))==(1<<N)-1)

我無法理解這是如何工作的。在比較中有什麼用處？如果有人能解釋這一點，那對我們新秀來說會非常有用。此外，任何提示識別這類問題將不勝感激。我使用了一種天真的算法來解決這個問題，最終只解決了較小的數據集（花了不少時間來編譯需要在8分鐘內提交的較大數據集）。提前致謝。

來源

2010-05-09 srandpersonia

幫你聯繫，召回'10000 - 1 = 9999'，大致同樣的事情發生在二進制 – Anycorn 2010-05-09 15:56:37

@aaa的確！現在它更有意義。 – srandpersonia 2010-05-09 16:13:24

我更喜歡（k ^（k + 1））>> n – 2012-06-28 23:34:07

我們以N = 3爲例。在二進制中，1<<3 == 0b1000。所以1<<3 - 1 == 0b111。

一般來說，1<<N - 1創建一個二進制形式的N個數字。

讓R = 1<<N-1。然後表達式變成(K&R) == R。該K&R將提取的最後N個比特，例如：

 101001010 
    &  111 
    ———————————— 
    000000010

（回想一下，按位與將在數字返回1，當且僅當兩個操作數具有1中的數字。）

當且僅當最後N位全爲1時，等式成立。因此，表達式檢查K是否以N個結尾。

來源

2010-05-09 15:54:49 kennytm

非常感謝您的解釋和您的時間。 :-) – srandpersonia 2010-05-09 16:11:28

例如：N = 3，K = 101010

1. (1<<N) = 001000 (shift function) 
2. (1<<N)-1 = 000111 (http://en.wikipedia.org/wiki/Two's_complement) 
3. K&(1<<N)-1 = 0000010 (Bitmask) 
4. K&(1<<N)-1 == (1<<N)-1) = (0000010 == 000111) = FALSE

來源

2010-05-09 16:04:49 Nikel

感謝您的鏈接和解釋:-) – srandpersonia 2010-05-09 16:12:46

我認爲我們可以通過首先計算由手的答案，對於一些系列的N（例如1,2-承認這樣的問題， 3，..）。之後，我們會識別狀態變化，然後編寫一個函數來自動化過程（第一個函數）。運行一些輸入程序，並注意模式。

當我們得到模式時，寫出表示模式的函數（第二個函數），並比較第一個函數和第二個函數的輸出。

對於Code Jam案例，我們可以針對小數據集運行這兩個函數，並驗證輸出。如果相同，則第二個函數可以及時解決大數據集的概率很高。

來源

2010-05-11 07:46:35 monn

我正在研究Snapper Chain問題，並在這裏尋找關於如何在解決方案中遇到的位旋轉算法的解釋。我發現了一些很好的信息，但是我仍然花了很長時間才弄明白自己是一個點點滴滴。

這裏是我嘗試解釋算法以及如何提出它。如果我們列舉鏈中每個笛卡爾所有可能的電源和ON/OFF狀態，我們會看到一個模式。給出的測試情況下，N = 3，K = 7（3種笛鯛，7扣）中，我們顯示每個鯛的功率和ON/OFF狀態，每第k個單元：

  1 2 3 
    0b:1 1 1.1 1.0 0.0 -> ON for n=1 
0b:10 2 1.0 0.1 0.0 
0b:11 3 1.1 1.1 1.0 -> ON for n=1, n=2 
0b:100 4 1.0 0.0 1.0 
0b:101 5 1.1 1.0 1.0 -> ON for n=1 
0b:110 6 1.0 0.1 0.1 
0b:111 7 1.1 1.1 1.1 -> ON for n=2, n=3

的燈泡是在當所有笛鯛打開並接收電源，或者當我們有第k個快照導致n 1s時。更簡單地說，當所有笛卡爾接通時燈泡都點亮，因爲它們都必須接通電源才能接通（因此燈泡）。這意味着每k次拍攝，我們需要n 1s。另外，你可以注意到k不僅滿足n = 3的k = 7，而且滿足n = 2且滿足n = 2的k = 1的k = 3。此外，對於n = 1或2，我們可以看到每打開一個燈泡的數量，k的最後n個數字總是1.我們可以試圖概括出所有滿足n個笛卡爾的k將是一個以1.

n個數字，我們可以使用較早的海報提到的表達比1 < < N - 1總是給我們n個1的二進制數字，或在這種情況下，1 < < 3 - 1 = 0b111。如果我們把我們的n個笛卡爾鏈看作一個二進制數，其中每個數字表示開/關，並且我們需要n個數字中的一個，這就給了我們表示。

現在，我們希望找到那些情況下，1 < < N - 1等於某個k，在1個二進制數字，這是我們通過執行按位並做結尾：克&（1 < < N - 1）得到k的最後n位數，然後將其與1 < < n - 1相比較。

我想這種類型的思維在處理這些類型的問題之後會變得更加自然，但它仍然很嚇人對我而言，我懷疑自己會想出一個這樣的解決方案！

這裏是我的解決方案在Perl：

$tests = <>; 
for (1..$tests) { 
    ($n, $k) = split//, <>; 
    $m = 1 << $n - 1; 
    printf "Case #%d: %s\n", $_, (($k & $m) == $m) ? 'ON' : 'OFF'; 
}

來源

2011-05-12 02:57:27 Anonymous

提取一個整數的最右邊N位

回答

相關問題