190. 顛倒二進制位

思路

將一個數字的二進制左右翻轉，比如 $11100\to00111$ 。
假設原先的二進制數字為 $\text{abcdefgh}$

1. 先1v1交換：$\text{ba dc fe hg}$
2. 再2v2交換：$\text{dcba hgfe}$
3. 再4v4交換：$\text{hgfedcba}$

這樣就把一個數字反轉了。
為什麼要用這樣看著多此一舉的操作？因為這些交換能用位運算表示。

在第一步時，往右交換的有四個數字 $\text{a c e g}$ ，往左交換的有 $\text{b d f h}$ 。
兩者都能用位運算獲得。

$\begin{array}{} \text{abcdefgh} \\\text{10101010} & \& \\\hline \text{a0c0e0g0} \end{array}$ ， $\begin{array}{} \text{abcdefgh} \\\text{01010101} & \& \\\hline \text{0b0d0f0h} \end{array}$

此時將 $\text{a0c0e0g0}$ 右移 1 位，將 $\text{0b0d0f0h}$ 左移一位，
再將兩者or，就完成第一步的1v1交換了。

$\begin{array}{} \text{a0c0e0g0}\gg1 & \text{0a 0c 0e 0g} \\\text{0b0d0f0h}\ll1 & \text{b0 d0 f0 h0} & \text{or} \\\hline & \text{ba cd fe hg} \end{array}$

第二步，用類似的操作去完成後續的交換，移位的步數增加。
此時往右交換的數字有 $\text{ba fe}$ ，往左交換的數字有 $\text{cd hg}$ ，移位操作之後or。

$\begin{array}{} \text{bacdfehg} \\\text{11001100} & \& \\\hline \text{ba00fe00} \end{array}$ ， $\begin{array}{} \text{bacdfehg} \\\text{00110011} & \& \\\hline \text{00cd00hg} \end{array}$ ， $\begin{array}{} \text{ba00fe00}\gg\blue2 & \text{00ba 00fe} \\\text{00cd00hg}\ll\blue2 & \text{cd00 hg00} & \text{or} \\\hline & \text{cdba hgfe} \end{array}$。

第三步，移位的步數增加。
此時往右交換的數字有 $\text{hgfe}$ ，往左交換的數字有 $\text{cdba}$ ，再透過移位操作or。

$\begin{array}{} \text{cdbahgfe} \\\text{11110000} & \& \\\hline \text{cdba0000} \end{array}$ ， $\begin{array}{} \text{cdbahgfe} \\\text{00001111} & \& \\\hline \text{0000hgfe} \end{array}$ ， $\begin{array}{} \text{cdba0000}\gg\blue4 & \text{0000cdba} \\\text{hgfe0000}\ll\blue4 & \text{hfge0000} & \text{or} \\\hline & \text{hgfecdba} \end{array}$。

程式碼

位運算

class Solution {
public:
    int reverseBits(int n) {
        n = ((n & 0xaaaaaaaa) >> 1) | ((n & 0x55555555) << 1); // 1010, 0101, 交換1位
        n = ((n & 0xcccccccc) >> 2) | ((n & 0x33333333) << 2); // 1100, 0011, 交換2位
        n = ((n & 0xf0f0f0f0) >> 4) | ((n & 0x0f0f0f0f) << 4); // 11110000, 00001111, 交換4位
        n = ((n & 0xff00ff00) >> 8) | ((n & 0x00ff00ff) << 8); // 交換 8 位
        n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16); // 交換 16 位
        return n;
    }
};

複雜度分析

• 時間複雜度：$O(1)$
• 空間複雜度：$O(1)$