# [LeetCode] 190. Reverse Bits

## 題目敘述

[Link](https://leetcode.com/problems/reverse-bits/)

* 題目給定一個可在 32-bit 範圍表示的正整數，我們要把其二進位表達式前後顛倒，並回傳顛倒後的十進位數值。

## 解題思路

* 最簡單的一個 bit 一個 bit 慢慢搬：
* 先把 bit 0 搬到存放結果的變數的 bit 31。
* 接著把 bit 1 搬到存放結果的變數的 bit 30。
* 以此類推。

### 複雜度分析

#### 時間複雜度分析

* 需要搬 32 個 bits，故總體時間複雜度為 $O(1)$。

#### 空間複雜度分析

* 沒有使用到會隨著輸入增長的空間，故空間複雜度為 $O(1)$。

## 進階解題思路 - 交換法

* 這種方法是模仿如何顛倒一個字串，顛倒一個 32-bit 的二進位表達式其實就是：
* 把 bit 0 跟 bit 31 交換。
* 把 bit 1 跟 bit 30 交換。
* 以此類推。
* 流程 (以迴圈實作，以下為一個迴圈 body 要做的事情)：
* 先算出兩個要交換的 bits 的值分別是多少。
* **如果兩個 bits 的值是相同的，那就不用交換，直接換下一組**。
* 都一樣的值交換有什麼意思呢？ XD
* 交換兩個 bits：
* **最傳統直覺的方法就是交換兩個 bits，但會需要額外一個變數去儲存交換的結果 (就是答案)**。
* 想一下，這兩個 bits 一定是一個 1 一個 0，要把 1 換成 0，要把 0 換成 1 除了直接交換還可以拿那兩個 bits 跟兩個 1 做 XOR 運算。
* 做一個數字，裡面只有目前要交換的兩個 bits 是 1，其他 bits 都是 0，然後拿去跟原數字做 XOR 運算，這樣子就可以交換那兩個 bits，而其他 bits 則維持原值。

### 複雜度分析

#### 時間複雜度分析

* 迴圈要跑 16 次，每次的時間複雜度為 $O(1)$，故總體時間複雜度為 $O(1)$。

#### 空間複雜度分析

* 沒有使用到會隨著輸入增長的空間，故空間複雜度為 $O(1)$。

## 進階解題思路 - Divide and Conquer 交換法

* **這種解題思路蠻複雜的，但卻可以用幾行程式碼而且不使用判斷式或是迴圈就可以完成顛倒一整個二進為表達式**。
* 其想法是根據分組交換而來的：
* 如果顛倒一個 32-bit 的二進位表達式，後面的 16 個 bits 一定會被搬到前面的 16-bit 區域；而前面 16 個 bits 一定會被搬到後面的 16-bit 區域。
* 假設我們先把前後 16 個 bits 交換。
* 再來考慮每一組 16-bit 區域：因為要顛倒，所以前 8 個 bits 一定會被搬到後面的 8-bit 區域；而後面的 8 個 bits 一定會被搬到前面的 8-bit 區域，**<font color="red">而且這是每一組 16-bit 區域的內部操作，每個 16-bit 區域互不影響</font>**。
* 假設我們都已經對每一組 16-bit 區域交換完。
* 再來考慮每一組 8-bit 區域：因為要顛倒，所以前 4 個 bits 一定會被搬到後面的 4-bit 區域；而後面的 4 個 bits 一定會被搬到前面的 4-bit 區域，**<font color="red">而且這是每一組 8-bit 區域的內部操作，每個 8-bit 區域互不影響</font>**。
* 假設我們都已經對每一個 8-bit 區域交換完。
* 再來考慮每一個 4-bit 區域：因為要顛倒，所以前 2 個 bits 一定會被搬到後面的 2-bit 區域；而後面的 2 個 bits 一定會被搬到前面的 2-bit 區域，**<font color="red">而且這是每一組 4-bit 區域的內部操作，每個 4-bit 區域互不影響</font>**。
* 假設我們都已經對每一個 4-bit 區域交換完。
* 再來考慮每一個 2-bit 區域：因為要顛倒，所以前 1 個 bit 一定會被搬到後面的 1-bit 區域；而後面的 1 個 bit 一定會被搬到前面的 2-bit 區域，**<font color="red">而且這是每一組 2-bit 區域的內部操作，每個 2-bit 區域互不影響</font>**。
* 把上述想法轉成實作 (考慮一個 32-bit 數字 $n$)：
* 如果要把前後 16-bit 區域交換，我們可以這樣子算：$n = \text{((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16)}$。
* 如果要對每一個 16-bits 區域進行交換，可以這樣子算：$n = \text{((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)}$。
* 因為區域內交換不影響其他區域，所以我們可以同時對多個區域進行交換。
* 如果要對每一個 8-bits 區域進行交換，可以這樣子算：$n = \text{((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)}$。
* 因為區域內交換不影響其他區域，所以我們可以同時對多個區域進行交換。
* 如果要對每一個 4-bits 區域進行交換，可以這樣子算：$n = \text{((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)}$。
* 因為區域內交換不影響其他區域，所以我們可以同時對多個區域進行交換。
* 如果要對每一個 2-bits 區域進行交換，可以這樣子算：$n = \text{((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)}$。
* 因為區域內交換不影響其他區域，所以我們可以同時對多個區域進行交換。
* C 範例程式碼：

  /* 假設原數字為 n */
  n = (((n & 0xFFFF0000) >> 16) | ((n & 0x0000FFFF) << 16));
  n = (((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8));
  n = (((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4));
  n = (((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2));
  n = (((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1));

### 複雜度分析

#### 時間複雜度分析

* 只需要執行五行程式碼，每次的時間複雜度為 $O(1)$，故總體時間複雜度為 $O(1)$。
* 雖然時間複雜度以大 O 角度來說跟前兩種解題思路相同，但這種方法保證只要五次計算就可以算出來，其時間複雜度中常數部分每次都是最小的。
* 而且沒有使用到判斷式或是迴圈，代表不會有 branch 指令，對於 CPU 來說不用承擔 branch misprediction 所帶來的 penalty。

#### 空間複雜度分析

* 沒有使用到會隨著輸入增長的空間，故空間複雜度為 $O(1)$。

### 建議

* 這種做法非常複雜，建議理解上面的運作原理再實作。

## Reference

* Gemini
* 詢問進階解題思路