從LeetCode學演算法 - 66 Bitwise Operation (3)

0190. Reverse Bits (Easy)

Question

Reverse bits of a given 32 bits unsigned integer.

Example 1

1
2
3
Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2

1
2
3
Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

分析/解題

題目要求將一個32bit長度的integer進行反轉。
(也就是將二進位制的各個bit 0變成1，1變成0)

先前我們談過二進位的問題，以及一些位元運算 。
如果這題有要求處理正負號的問題的話，就會稍微複雜一點，
因為如題目提示的說明，Java中的有號的integer會使用**二補數
(2’s complement)**來表示，這件事情隱含了如果將bit位移時，
需要考慮是»或»>的問題。
負數使用»時最高位會補1，而»>時最高位會補0 ，
由於最高位用來記錄正負號，這會影響到實際得到的結果。

但我們這邊單純只是要將整個32 bit順序反過來的話就沒有太大問題XD

我們先從簡單一點的開始，
比如有一個數字n是1001100(也就是十進制的76)，
假設我們要將這7個bit反轉，應該要得到0011001，這個過程怎麼來的呢？

先將我們的答案叫做r(result)，一開始為0，我們先這樣表示：

1
2
r:
n: 1001100

接下來我們要找下一個對應的bit的話，
n必須要取最右邊的bit才行，記錄完以後，
為了讓下一次的n的最右邊依然是我們要的bit，
可以將n進行一次向右位移，即可對到最右邊。
另外，r為了要記錄下一個位元，每次要向左位移一格，空出最右邊來。

1
2
r: 0
n: 100110

重複相同的操作，直到n等於0或全部位元操作完畢即可。

1
2
r:        -> 0      -> 00    -> 001  -> 0011 -> 00110 -> 0011001
n:1001100 -> 100110 -> 10011 -> 1001 -> 100  -> 10    -> 1      -> 0

觀察上面的規律，我們可以歸納出對32位元的操作：
1. 令res為0
2. 執行32次以下的迴圈：
2–1. res向左位移1位
2–2. 將n的最右邊的bit加到res上
2–3. 將n向右位移1位
3. 最終res即為答案

依此，可以寫成如下的程式碼：
Java的部分，我們使用«=和»=進行各自位移後再回存。
而對應到2-2的部分，除了如第8行的寫法，
將n和1進行AND運算 來確認最右邊的位元 以外，
也可以用AND完以後跟res進行OR 的方法。
此外，由於最開始res是0，
所以先將其往左位移一次是不會對答案造成影響的。

Java

Python的部分提供一個看到比較特別的寫法：
使用format將n進行轉換，
當中0:032b的第一個0可以不用寫 (因為format中也只有一個數字)，
第二個0代表多出來的部份必須進行補0 (補完反轉才不會有問題)，
轉成32位的bit後，將其從尾往頭擺順序，
再用int轉換回integer(指定前面那段是二進制)即可。

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(N)，因為必然經過每個位元)

「如果檢查n是否為0做為結束條件，執行速度是否會較快？」
(不一定，要看n反轉後的最接近高位的0有多接近，
否則每次多檢查一次未必比較快)

相似及延伸

Special Thanks suggestions/corrections from viewers:
From ** 程式人雜誌 — 公益出版** ** - Novus Chou**:
「現實中比較講究的位元操作，會盡可能一次處理多位元，
而且最好不動用迴圈。

以 8 bit 為例

12345678
=> 21 436587 (奇偶交換)
=> 4321 8765 (兩兩一組交換)
=> 87654321 (前後半交換)

類似 C 風格的寫法大概長這樣，
最後一輪利用整數自然截位所以不用 mask（當然這點要看語言特性）。

x = (((x & 0xAA) » 1) | ((x & 0x55) « 1));
x = (((x & 0xCC) » 2) | ((x & 0x33) « 2));
x = (x » 4) | (x « 4);

更快的作法就是半查表，也就是把問題分解到某階段改用查的。 」
(註：利用連續的bit mask進行處理，可達到交換的目的，
這個方法對於在意效能 來說，
由於if/while/for 等需要判斷 或有分歧狀況 的程式碼，
皆須花費相對於位元運算而言較多的時間，
能夠單純利用位元運算達成互換會是在實際狀況較棒的解法。)

(但，其實沒特別用過的話，面試時其實頗難回想出這種解法就是了XD)
有興趣的話可以參考這兩篇：

另外，Java中內建的bitCount 函式(計算某個數的二進位制含有1的數量)，
也運用了類似的手法達到目的。
參見： https://www.jishuwen.com/d/2HPI/zh-tw

(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

1
如果你／妳覺得這篇文章不錯，請給我5個Like。(點開SHOW EMBED!)