1.2 二進制

整數在計算機中是以二進制的形式表示的。二進制是指數字的每位都是0或1。例如，十進制形式的2轉化為二進制形式之后是10，而十進制形式的10轉換成二進制形式之后是1010。

位運算是把數字用二進制形式表示之后，對每位上0或1的運算。二進制及其位運算是現代計算機學科的基石，很多底層的技術都離不開位運算，因此與位運算相關的題目也經常出現在面試中。由于人們在日常生活中習慣使用十進制形式，因此二進制及位運算讓很多人很難適應。

其實二進制的位運算并不是很難掌握，因為位運算只有6種：非、與、或、異或、左移和右移。非運算對整數的二進制按位取反，0取反得1，1取反得0。下面對8位整數進行非運算：

~00001010=11110101

~10001010=01110101

與、或和異或的運算規律如表1.1所示。

左移運算符m＜＜n表示把m左移n位。如果左移n位，那么最左邊的n位將被丟棄，同時在最右邊補上n個0。具體示例如下：

00001010＜＜2=00101000

10001010＜＜3=01010000

右移運算符m>>n表示把m右移n位。如果右移n位，則最右邊的n位將被丟棄。但右移時處理最左邊位的情形比較復雜。如果數字是一個無符號數值，則用0填補最左邊的n位。如果數字是一個有符號數值，則用數字的符號位填補最左邊的n位。也就是說，如果數字原先是一個正數，則右移之后在最左邊補n個0；如果數字原先是一個負數，則右移之后在最左邊補n個1。下面是對8位有符號數值（Java中的byte型整數）進行右移的例子：

00001010>>2=00000010

10001010>>3=11110001

Java中增加了一種無符號右移位操作符“>>>”。無論是對正數還是負數進行無符號右移操作，都將在最左邊插入0。下面是對Java中byte型整數進行無符號右移操作的例子：

00001010>>>2=00000010

10001010>>>3=00010001

其他編程語言（如C或C++）中沒有無符號右移位操作符。

面試題2：二進制加法

分析：有不少人看到這個題目的第一反應是將二進制字符串轉換成int型整數或long型整數，然后把兩個整數相加得到和之后再將和轉換成二進制字符串。例如，將二進制字符串"11"轉換成3，"10"轉換成2，兩個整數的和為5，將之轉換成二進制字符串就得到"101"。這種解法可能會導致溢出。這個題目沒有限制二進制字符串的長度。當二進制字符串比較長時，它表示的整數可能會超出int型整數或long型整數的范圍，此時不能直接將其轉換成整數。

因此，加法操作只能針對兩個字符串進行?？梢詤⒄帐M制加法來完成二進制加法。在進行十進制加法時，總是將兩個數字的右端對齊，然后從它們的個位開始從右向左相加同一位置的兩個數位，如果前一位有進位還要加上進位。

二進制加法也可以采用類似的方法，從字符串的右端出發向左做加法。與十進制不同的是，二進制是逢二進一，當兩個數位加起來等于2時就會產生進位。可以用如下所示的參考代碼實現二進制加法：

上述代碼中的加法是從字符串的右端開始的，最低位保存在result的最左邊，而通常數字最左邊保存的是最高位，因此，函數addBinary在返回之前要將result進行翻轉。

面試題3：前n個數字二進制形式中1的個數

分析：很多人在面試的時候都能想到直觀的解法，使用一個for循環來計算從0到n的每個整數i的二進制形式中1的個數。于是問題轉換成如何求一個整數i的二進制形式中1的個數。

? 簡單計算每個整數的二進制形式中1的個數

計算整數i的二進制形式中1的個數有多種不同的方法，其中一種比較高效的方法是每次用“i&（i-1）”將整數i的最右邊的1變成0。整數i減去1，那么它最右邊的1變成0。如果它的右邊還有0，則右邊所有的0都變成1，而其左邊所有位都保持不變。下面對i和i-1進行位與運算，相當于將其最右邊的1變成0。以二進制的1100為例，它減去1的結果是1011。1100和1011的位與運算的結果正好是1000。二進制的1100最右邊的1變為0，結果剛好就是1000。

這種思路可以用如下代碼實現：

如果一個整數共有k位，那么它的二進制形式中可能有O（k）個1。在上述代碼中，while循環中的代碼對每個整數將執行O（k）次，因此，上述代碼的時間復雜度是O（nk）。

? 根據“i&（i-1）”計算i的二進制形式中1的個數

根據前面的分析可知，“i&（i-1）”將i的二進制形式中最右邊的1變成0，也就是說，整數i的二進制形式中1的個數比“i&（i-1）”的二進制形式中1的個數多1。我們可以利用這個規律寫出如下代碼：

不管整數i的二進制形式中有多少個1，上述代碼只根據O（1）的時間就能得出整數i的二進制形式中1的數目，因此時間復雜度是O（n）。

? 根據“i/2”計算i的二進制形式中1的個數

還可以使用另一種思路來解決這個問題。如果正整數i是一個偶數，那么i相當于將“i/2”左移一位的結果，因此偶數i和“i/2”的二進制形式中1的個數是相同的。如果i是奇數，那么i相當于將“i/2”左移一位之后再將最右邊一位設為1的結果，因此奇數i的二進制形式中1的個數比“i/2”的1的個數多1。例如，整數3的二進制形式是11，有2個1。偶數6的二進制形式是110，有2個1。奇數7的二進制形式是111，有3個1。我們可以根據3的二進制形式中1的個數直接求出6和7的二進制形式中1的個數。這種解法的參考代碼如下所示：

上述代碼用“i>>1”計算“i/2”，用“i&1”計算“i%2”，這是因為位運算比除法運算和求余運算更高效。這個題目是關于位運算的，因此應該盡量運用位運算優化代碼，以展示對位運算相關知識的理解。

這種解法的時間復雜度也是O（n）。

面試題4：只出現一次的數字

分析：這個題目有一個簡化版的類似的題目“輸入數組中除一個數字只出現一次之外其他數字都出現兩次，請找出只出現一次的數字”。任何一個數字異或它自己的結果都是0。如果將數組中所有數字進行異或運算，那么最終的結果就是那個只出現一次的數字。

在這個題目中只有一個數字出現了一次，其他數字出現了3次。相同的3個數字異或的結果是數字本身，但是將數組中所有數字進行異或運算并不能消除出現3次的數字。因此，需要想其他辦法。

一個整數是由32個0或1組成的。我們可以將數組中所有數字的同一位置的數位相加。如果將出現3次的數字單獨拿出來，那么這些出現了3次的數字的任意第i個數位之和都能被3整除。因此，如果數組中所有數字的第i個數位相加之和能被3整除，那么只出現一次的數字的第i個數位一定是0；如果數組中所有數字的第i個數位相加之和被3除余1，那么只出現一次的數字的第i個數位一定是1。這樣只出現一次的任意第i個數位可以由數組中所有數字的第i個數位之和推算出來。當我們知道一個整數任意一位是0還是1之后，就可以知道它的數值。

基于這種思路可以寫出如下代碼：

Java的int型整數有32位，因此上述代碼創建了一個長度為32的數組bitSums，其中“bitSums[i]”用來保存數組nums中所有整數的二進制形式中第i個數位之和。

代碼“（num>>（31-i））&1”用來得到整數num的二進制形式中從左數起第i個數位。整數i先被右移31-i位，原來從左數起第i個數位右移之后位于最右邊。接下來與1做位與運算。整數1除了最右邊一位是1，其余數位都是0，它與任何一個數字做位與運算的結果都是保留數字的最右邊一位，其他數位都被清零。如果整數num從左數起第i個數位是1，那么“（num>>（31-i））&1”的最終結果就是1；否則最終結果為0。

下面求8位二進制整數01101100從左數起的第2個（從0開始計數）數位。我們先將01101100右移5位（7-2=5）得到00000011，再將它和00000001做位與運算，結果為00000001，即1。8位二進制整數01101100從左邊數起的第2個數位的確是1。

舉一反三

題目：輸入一個整數數組，數組中只有一個數字出現m次，其他數字都出現n次。請找出那個唯一出現m次的數字。假設m不能被n整除。

分析：解決面試題4的方法可以用來解決同類型的問題。如果數組中所有數字的第i個數位相加之和能被n整除，那么出現m次的數字的第i個數位一定是0；否則出現m次的數字的第i個數位一定是1。

面試題5：單詞長度的最大乘積

分析：解決這個問題的關鍵在于如何判斷兩個字符串str1和str2中沒有相同的字符。一個直觀的想法是基于字符串str1中的每個字符ch，掃描字符串str2判斷字符ch是否出現在str2中。如果兩個字符串的長度分別為p和q，那么這種蠻力法的時間復雜度是O（pq）。

? 用哈希表記錄字符串中出現的字符

也可以用哈希表來優化時間效率。對于每個字符串，可以用一個哈希表記錄出現在該字符串中的所有字符。在判斷兩個字符串str1和str2中是否有相同的字符時，只需要從'a'到'z'判斷某個字符是否在兩個字符串對應的哈希表中都出現了。在哈希表中查找的時間復雜度是O（1）。這個題目假設所有字符都是英文小寫字母，只有26個可能的字符，因此最多只需要在每個字符串對應的哈希表中查詢26次就能判斷兩個字符串是否包含相同的字符。26是一個常數，因此可以認為應用哈希表后判斷兩個字符串是否包含相同的字符的時間復雜度是O（1）。

由于這個題目只需要考慮26個英文小寫字母，因此可以用一個長度為26的布爾型數組來模擬哈希表。數組下標為0的值表示字符'a'是否出現，下標為1的值表示字符'b'是否出現，其余以此類推。

這種思路的參考代碼如下所示：

上述代碼分為兩步。第1步，初始化每個字符串對應的哈希表。如果數組words的長度為n，平均每個字符串的長度為k，那么初始化哈希表的時間復雜度是O（nk）。第2步，根據哈希表判斷每對字符串是否包含相同的字符?？偣灿?i>O（n²）對字符串，判斷每對字符串是否包含相同的字符需要的時間為O（1），因此這一步的時間復雜度是O（n²）。于是這種解法的總體時間復雜度是O（nk+n²）。

上述代碼為每個字符串創建一個長度為26的數組，用來記錄字符串中出現的字符。如果數組words的長度為n，那么這種解法的空間復雜度就是O（n）。

? 用整數的二進制數位記錄字符串中出現的字符

前面的解法是用一個長度為26的布爾型數組記錄字符串中出現的字符。布爾值只有兩種可能，即true或false。這與二進制有些類似，在二進制中數字的每個數位要么是0要么是1。因此，可以將長度為26的布爾型數組用26個二進制的數位代替，二進制的0對應布爾值false，而1對應true。

Java中int型整數的二進制形式有32位，但只需要26位就能表示一個字符串中出現的字符，因此可以用一個int型整數記錄某個字符串中出現的字符。如果字符串中包含'a'，那么整數最右邊的數位為1；如果字符串中包含'b'，那么整數的倒數第2位為1，其余以此類推。這樣做的好處是能更快地判斷兩個字符串是否包含相同的字符。如果兩個字符串中包含相同的字符，那么它們對應的整數相同的某個數位都為1，兩個整數的與運算將不會等于0。如果兩個字符串沒有相同的字符，那么它們對應的整數的與運算的結果等于0。

基于這種思路可以寫出如下代碼：

上述代碼中的整數“flags[i]”用來記錄字符串“words[i]”中出現的字符。如果“words[i]”中出現了某個字符ch，則對應的整數“flags[i]”中從右邊數起第ch-'a'個數位（即'a'對應最右邊的數位，'b'對應倒數第2個數位，其余以此類推）將被標記為1。

如果兩個整數“flags[i]”和“flags[j]”的與運算的結果為0，那么它們對應的字符串“words[i]”和“words[j]”一定沒有相同的字符。此時可以計算它們長度的乘積，并與其他不含相同字符的字符串對的長度乘積相比較，最終得到長度乘積的最大值。

如果數組words的長度為n，平均每個字符串的長度為k，那么這種解法的時間復雜度是O（nk+n²），空間復雜度是O（n）。雖然兩種解法的時間復雜度和空間復雜度是同一個量級的，但前面的解法在判斷兩個字符串是否包含相同的字符時，可能需要26次布爾運算，而新的解法只需要1次位運算，因此新的解法的時間效率更高。