8.5 位操作 + 8.6 智力題

8.5 位操作

位操作可以用於解決各種各樣的問題。有時候，有的問題會明確要求用位操作來解決，而在其他情況下，位操作也是最佳化程式碼的實用技巧。寫程式碼要熟悉位操作，同時也要熟練掌握位操作的手工運算。處理位操作問題時，務必小心翼翼，不經意間就會犯下各種小錯。程式碼寫好後一定要進行充分的測試，也可以邊寫程式碼邊測試。

手工位操作

如果像很多人一樣，你也懼怕位操作問題，以下這些練習對你大有裨益。當你一籌莫展或困惑不解時，不妨換用十進位制來理解相關操作，再將這些操作過程應用到二進位制上。記住，符號^表示XOR（異或）操作，~表示非（取反）操作。

為簡單起見，假定運算元的位寬為4位。我們可以手工或是施以若干技巧（詳情如下）解決下表第三列的問題。

0110 + 0010 0011 * 0101 0110 + 0110 0011 + 0010 0011 * 0011 0100 *0011 0110 - 0011 1101 >> 2 1101 ^ （~1101） 1000 - 0110 1101 ^ 01011011 & （~0 << 2）

答案：第一行（1000， 1111， 1100）；

第二行（0101， 1001， 1100）；

第三行（0011， 0011， 1111）；

第四行（0010， 1000， 1000）。

第三列問題的解決技巧如下。0110 + 0110相當於0110 * 2，也就是將0110左移1位。0100等於4，0100 * 0011也就是將0011乘以4。一個數與2n相乘，相當於將這個數左移n位。於是，將0011左移2位得到1100。逐個位元分解這一操作。一個位元與對它取反的值做異或操作，結果總是1。

因此，a^（~a）的結果是一串1。類似x & （~0 << n）的操作會將x最右邊的n位清零。~0的值就是一串1，將它左移n位後的結果為一串1後面跟n個0。將這個數與x進行“位與”操作，相當於將x最右邊的n位清零。要處理其他問題，不妨開啟Windows上的計算器，選擇“檢視”（View）選單項，再點選該工具的“程式設計師”（Programmer）版本。

有了這個應用程式，就可以執行位與、異或和移位等各種二進位制運算。位操作原理與技巧處理位操作問題時，理解以下原理會大有幫助。不要一味死記硬背，而應思考這些等式何以成立。在下面的示例中，“1s”和“0s”分別表示一串1和一串0。x ^ 0s = x x & 0s = 0 x | 0s = x x ^ 1s = ~x x & 1s = x x | 1s = 1sx ^ x = 0 x & x = x x | x = x要理解這些表示式的含義，你必須記住所有操作是按位進行的，某一位的運算結果不會影響其餘位。也就是說，只要上述語句對某一位成立，則同樣適用於一串位。

常見位操作：獲取、設定、清除及更新位資料

以下這些位操作非常重要，不過切忌死記硬背，否則只會滋生一些難以察覺的錯誤。相反，你要吃透這些操作方法，學會舉一反三，靈活處理其他問題。獲取該方法將1左移i位，得到形如00010000的值。接著，對這個值與num執行“位與”操作，從而將i位之外的所有位清零。最後，檢查該結果是否為零。不為零說明i位為1，否則，i位為0。

boolean getBit（int num， int i） {

return （（num & （1 << i）） ！=0）； }

置位setBit先將1左移i位，得到形如00010000的值。接著，對這個值和num執行“位或”操作，這樣只會改變i位的資料。該掩碼i位除外的位均為零，故而不會影響num的其餘位。

int setBit（int num， int i） {

return num | （1 << i）； }

清零該方法與setBit剛好相反。首先，將1左移i位取得形如00010000的值，對這個值取反進而得到類似11101111的掩碼。接著，對該掩碼和num執行“位與”操作。這樣只會清零num的i位，其餘位則保持不變。

int clearBit（int num， int i） {

int mask = ~（1 << i）；

returnnum & mask；

}

將num最高位至i位（含）清零的做法如下

int clearBitsMSBthroughI（int num， int i） {

int mask = （1 << i）- 1；

return num & mask； }

將i位至0位（含）清零的做法如下：

int clearBitsIthrough0（int num， int i） {

int mask = ~（（1 <<（i+1）） - 1）；

return num & mask； }

更新這個方法將setBit與clearBit合二為一。首先，用諸如11101111的掩碼將num的第i位清零。接著，將待寫入值v左移i位，得到一個i位為v但其餘位都為0的數。最後，對之前取得的兩個結果執行“位或”操作，v為1則將num的i位更新為1，否則該位仍為0。

int updateBit（int num， int i， int v） {

int mask = ~（1 << i）； 。 //

return （num & mask） | （v << i）； }

面試題目

5。1 給定兩個32位的整數N與M，以及表示位元位置的i與j。編寫一個方法，將M插入N，使得M從N的第j位開始，到第i位結束。假定從j位到i位足以容納M，也即若M=10011，那麼j和i之間至少可容納5個位。例如，不可能出現j = 3和i = 2的情況，因為第3位和第2位之間放不下M。

示例 輸入：N = 10000000000， M = 10011， i = 2， j = 6 輸出：N =10001001100

5。2 給定一個介於0和1之間的實數（如0。72），型別為double，列印它的二進位制表示。如果該數字無法精確地用32位以內的二進位制表示，則列印“ERROR”。

5。3 給定一個正整數，找出與其二進位制表示中1的個數相同、且大小最接近的那兩個數（一個略大，一個略小）。

5。4 解釋程式碼（（n & （n-1）） == 0）的具體含義。

5。5 編寫一個函式，確定需要改變幾個位，才能將整數A轉成整數B。

示例 輸入：31， 14 輸出：2

5。6 編寫程式，交換某個整數的奇數位和偶數位，使用指令越少越好（也就是說，位0與位1交換，位2與位3交換，依此類推）。

5。7 陣列A包含0到n的所有整數，但其中缺了一個。在這個問題中，只用一次操作無法取得陣列A裡某個整數的完整內容。此外，陣列A的元素皆以二進位制表示，唯一可用的訪問操作是“從A［i］取出第j位資料”，該操作的時間複雜度為常數。請編寫程式碼找出那個缺失的整數。你有辦法在O（n）時間內完成嗎？

5。8 有個單色螢幕儲存在一個一維位元組陣列中，使得8個連續畫素可以存放在一個位元組裡。螢幕寬度為w，且w可被8整除（即一個位元組不會分佈在兩行上），螢幕高度可由陣列長度及螢幕寬度推算得出。請實現一個函式drawHorizontalLine（byte［］screen， int width， int x1， int x2， int y），繪製從點（x1， y）到點（x2，y）的水平線。

如果像很多人一樣，你也懼怕位操作問題，以下這些練習對你大有裨益。當你一籌莫展或困惑不解時，不妨換用十進位制來理解相關操作，再將這些操作過程應用到二進位制上。記住，符號^表示XOR（異或）操作，~表示非（取反）操作。為簡單起見，假定運算元的位寬為4位。我們可以手工或是施以若干技巧（詳情如下

解決下表第三列的問題。

第三列問題的解決技巧如下。0110 + 0110相當於0110 * 2，也就是將0110左移1位。0100等於4，0100 * 0011也就是將0011乘以4。一個數與2n相乘，相當於將這個數左移n位。於是，將0011左移2位得到1100。逐個位元分解這一操作。一個位元與對它取反的值做異或操作，結果總是1。因此，a^（~a）的結果是一串1。類似x & （~0 << n）的操作會將x最右邊的n位清零。~0的值就是一串1，將它左移n位後的結果為一串1後面跟n個0。將這個數與x進行“位與”操作，相當於將x最右邊的n位清零。要處理其他問題，不妨開啟Windows上的計算器，選擇“檢視”（View）選單項，再點選該工具的“程式設計師”（Programmer）版本。有了這個應用程式，就可以執行位與、異或和移位等各種二進位制運算。位操作原理與技巧處理位操作問題時，理解以下原理會大有幫助。不要一味死記硬背，而應思考這些等式何以成立。在下面的示例中，“1s”和“0s”分別表示一串1和一串0。x ^ 0s = x x & 0s = 0 x | 0s = x x ^ 1s = ~x x & 1s = x x | 1s = 1sx ^ x = 0 x & x = x x | x = x要理解這些表示式的含義，你必須記住所有操作是按位進行的，某一位的運算結果不會影響其餘位。也就是說，只要上述語句對某一位成立，則同樣適用於一串位。常見位操作：獲取、設定、清除及更新位資料以下這些位操作非常重要，不過切忌死記硬背，否則只會滋生一些難以察覺的錯誤。相反，你要吃透這些操作方法，學會舉一反三，靈活處理其他問題。獲取該方法將1左移i位，得到形如00010000的值。接著，對這個值與num執行“位與”操作，從而將i位之外的所有位清零。最後，檢查該結果是否為零。不為零說明i位為1，否則，i位為0。

boolean getBit（int num， int i） {

return （（num & （1 << i）） ！=0）； }

置位setBit先將1左移i位，得到形如0001。0000的值。接著，對這個值和num執行“位或”操作，這樣只會改變i位的資料。

該掩碼i位除外的位均為零，故而不會影響num的其餘位。

int setBit（int num， int i） {

return num | （1 << i）； }

清零該方法與setBit剛好相反。

首先，將1左移i位取得形如00010000的值，對這個值取反進而得到類似11101111的掩碼。接著，對該掩碼和num執行“位與”操作。這樣只會清零num的i位，其餘位則保持不變。

int clearBit（int num， int i） {

int mask = ~（1 << i）； //。。。。

returnnum & mask； }

將num最高位至i位（含）清零的做法如下：

int clearBitsMSBthroughI（int num， int i） {

int mask = （1 << i）- 1； //zx

return num & mask； } //dcb

將i位至0位（含） 清零的做法如下：

int clearBitsIthrough0（int num， int i） {

int mask = ~（（1 <<（i+1）） - 1）； //0。0

return num & mask； } //jiesahu

更新這個方法將setBit與clearBit合二為一。

首先，用諸如11101111的掩碼將num的第i位清零。接著，將待寫入值v左移i位，得到一個i位為v但其餘位都為0的數。最後，對之前取得的兩個結果執行“位或”操作，v為1則將num的i位更新為1，否則該位仍為0。

int updateBit（int num， int i， int v） {

int mask = ~（1 << i）； //010

return （num & mask） | （v << i）； }

面試題目 1

5。1。2 給定兩個32位的整數N與M，以及表示位元位置的i與j。編寫一個方法，將M插入N，使得M從N的第j位開始，到第i位結束。假定從j位到i位足以容納M，也即若M=10011，那麼j和i之間至少可容納5個位。例如，不可能出現j = 3和i = 2的情況，因為第3位和第2位之間放不下M。

示例 輸入：N = 10000000000， M = 10011， i = 2， j = 6 輸出：N =100010011005。2 。2給定一個介於0和1之間的實數（如0。72），型別為double，列印它的二進位制表示。如果該數字無法精確地用32位以內的二進位制表示，則列印“ERROR”。

5。3 。2給定一個正整數，找出與其二進位制表示中1的個數相同、且大小最接近的那兩個數（一個略大，一個略小）。

5。4 。2解釋程式碼（（n & （n-1）） == 0）的具體含義。

5。5。2 編寫一個函式，確定需要改變幾個位，才能將整數A轉成整數B。

5。6。2 編寫程式，交換某個整數的奇數位和偶數位，使用指令越少越好（也就是說，位0與位1交換，位2與位3交換，依此類推）。

5。7。2 陣列A包含0到n的所有整數，但其中缺了一個。在這個問題中，只用一次操作無法取得陣列A裡某個整數的完整內容。此外，陣列A的元素皆以二進位制表示，唯一可用的訪問操作是“從A［i］取出第j位資料”，該操作的時間複雜度為常數。請編寫程式碼找出那個缺失的整數。你有辦法在O（n）時間內完成嗎？

5。8。2 有個單色螢幕儲存在一個一維位元組陣列中，使得8個連續畫素可以存放在一個位元組裡。螢幕寬度為w，且w可被8整除（即一個位元組不會分佈在兩行上），螢幕高度可由陣列長度及螢幕寬度推算得出。請實現一個函式drawHorizontalLine（byte［］screen， int width， int x1， int x2， int y），繪製從點（x1， y）到點（x2，y）的水平線。

8。6。2 智力題智力題當屬最有爭議的面試題之列，很多公司甚至明文規定面試中不得出現智力題。儘管如此，你還是會時不時地碰到它。為什麼呢？因為人們對於智力題尚無明確的定義。不過，好在哪怕你碰到了這類問題，一般來說它們也不會太難。你不需要做腦筋急轉彎，並且幾乎總有辦法透過邏輯推理得出答案。很多智力題甚至還涉及數學或計算機科學的基礎知識。下面，我們會列舉一些應對智力題的常見方法。大聲說出你的思路遇到智力題時，切忌驚慌。

就像演算法題一樣，面試官只不過想看看你會如何處理難題；他們並不期待你立即給出正確答案。只管大聲說出解題思路，讓面試官瞭解你的應對之道。總結規律和模式很多情況下，你會發現，把解題過程中發現的“規律”或“模式”寫下來幫助很大。並且，你確實應該這麼做，這有助於加深記憶。下面會舉例說明這種方法。給定兩條繩子，每條繩子燃燒殆盡正好要用一個小時。怎樣用這兩條繩子準確計量15分鐘？注意這些繩子密度不均勻，因此燒掉半截繩子不一定正好用半個小時。

技巧：先別急著往下看，不妨試著自己解決此問題。一定要看下面的提示資訊的話——也請一段一段慢慢看。後續段落會逐步揭曉答案。從題目可知，計量一小時不成問題。當然也可以計量兩小時，先點燃一根繩子，等它燃燒殆盡，再點燃第二根。由此我們總結出第一條規律。

規律1：給定兩條繩子，燃燒殆盡各需x分鐘和y分鐘，我們可以計時x+y分鐘。那麼，還有其他燒繩子的花樣嗎？當然，我們知道從中間（或繩子兩頭以外的任意位置）點燃繩子沒什麼用。火苗會向繩子兩頭蔓延，我們不知道過多久才會燒完。話說回來，我們可以同時點燃繩子兩頭。30分鐘後火焰便會在繩子某個位置匯合。

規律2：給定一條需要x分鐘燒完的繩子，我們可以計時x/2分鐘。由此可知，用一條繩子可以計時30分鐘。這就意味著我們可以在燃燒第二條繩子時減去這30分鐘，也就是點燃第一條繩子兩頭的同時，只點燃第二條繩子的一頭。規律3：燒完繩子1用時x分鐘，繩子2用時y分鐘，則可以用第二條繩子計時（y-x）分鐘或（y-x/2）分鐘。綜合以上規律，不難得出：既然可以用繩子2計時30分鐘，再適時點燃繩子2的另一頭（見規律2），則15分鐘後繩子2便會燃燒殆盡。將上面的做法從頭至尾整理如下。點燃繩子1兩頭的同時，點燃繩子2的一頭。當繩子1從兩頭燒至中間某個位置時，正好過去30分鐘。而繩子2還可以再燒30分鐘。此時，點燃繩子2的另一頭。15分鐘後，繩子2將全部燒完。從中可以看出，只要一步步歸納規律，並在此基礎上進行總結，智力題便可迎刃而解。

略作變通許多智力題往往涉及將最壞情況減至最低限度的問題，措辭上要麼要求儘可能減少步驟，要麼限定具體的試驗次數。一種實用的技巧是嘗試“平衡”最壞情況。也就是說，如果早先的解決方案效果不太理想，我們可以針對最壞情況略作變通。用一個例子來解釋會更為清晰。“

九球稱重”是一個經典面試題。給定9個球，其中8個球的重量相同，只有一個比較重。然後給定一個天平，可以稱出左右兩邊哪邊更重。最多用兩次天平，找出這個重球。第一種做法是將球分成2組，4個一組，第9個球暫時擱在一邊。如果有一組球較重，則重球必在其中；但如果兩組球重量相同，則第9個球為重球。按此思路將包含重球的這一組球再分成兩組，在最壞情況下我們需要稱量3次——多了一次！因此，這是一個“失衡”的解法：如果第9個球是重球，我們只需稱量一次；但如果不是，則需稱量3次。如果我們略作調整，將更多的球與第9個球配在一起，就不會出現“失衡”的狀況。這就是所謂“最壞情況下的平衡”。現在，將這些球均分成3個一組共3組，稱量一次就能知道哪一組球更重。我們甚至可以總結出一條規律：給定N個球，其中N能被3整除，稱量一次便能找到包含重球的那一組球。找到這一組3個球之後，我們只是簡單地重複此前的模式：先把一個球放到一邊，稱量剩下的兩個球。從中挑出那個重球；或者，如果這兩個球重量相同，那第3個球便是重球。觸類旁通要是卡殼了，不妨考慮運用前面提到的演算法題的五種解法。剔除技術層面的因素，智力題不外乎就是些演算法題。其中，舉例法、簡化推廣法、模式匹配法，以及簡單構造法可能會特別有用。面試題目

6。1 有20瓶藥丸，其中19瓶裝有1克/粒的藥丸，餘下一瓶裝有1。1克/粒的藥丸。給你一臺稱重精準的天平，怎麼找出比較重的那瓶藥丸？天平只能用一次。

6。2 有個8×8棋盤，其中對角的角落上，兩個方格被切掉了。給定31塊多米諾骨牌，一塊骨牌恰好可以覆蓋兩個方格。用這31塊骨牌能否蓋住整個棋盤？請證明你的答案（提供範例，或證明為什麼不可能）。

6。3 有兩個水壺，容量分別為5夸脫（美製：1夸脫=0。946升，英制：1夸脫=1。136升）和3夸脫，若水的供應不限量（但沒有量杯），怎麼用這兩個水壺得到剛好4夸脫的水？注意，這兩個水壺呈不規則形狀，無法精準地裝滿“半壺”水。

6。4 有個島上住著一群人，有一天來了個遊客，定了一條奇怪的規矩：所有藍眼睛的人都必須儘快離開這個島。每晚8點會有一個航班離島。每個人都看得見別人眼睛的顏色，但不知道自己的（別人也不可以告知）。此外，他們不知道島上到底有多少人是藍眼睛的，只知道至少有一個人的眼睛是藍色的。所有藍眼睛的人要花幾天才能離開這個島？

6。5 有棟建築物高100層。若從第N層或更高的樓層扔下來，雞蛋就會破掉。若從第N層以下的樓層扔下來則不會破掉。給你2個雞蛋，請找出N，並要求最差情況下扔雞蛋的次數為最少。

6。6 走廊上有100個關上的儲物櫃。有個人先是將100個櫃子全都開啟。接著，每數兩個櫃子關上一個。然後，在第三輪時，再每隔兩個就切換第三個櫃子的開關狀態（也就是將關上的櫃子開啟，將開啟的關上）。照此規律反覆操作100次，在第i輪，這個人會每數i個就切換第i個櫃子的狀態。當第100輪經過走廊時，只切換第100個櫃子的開關狀態，此時有幾個櫃子是開著的？