?190. 顛倒二進制位

難度：簡單

顛倒給定的 32 位無符號整數的二進制位。

提示：

• 請注意，在某些語言（如 Java）中，沒有無符號整數類型。在這種情況下，輸入和輸出都將被指定為有符號整數類型，并且不應影響您的實現，因為無論整數是有符號的還是無符號的，其內部的二進制表示形式都是相同的。
• 在 Java 中，編譯器使用 二進制補碼 記法來表示有符號整數。因此，在 示例 2 中，輸入表示有符號整數 -3，輸出表示有符號整數 -1073741825 。

示例 1：

輸入：n = 00000010100101000001111010011100
輸出：964176192 (00111001011110000010100101000000)
解釋：輸入的二進制串 00000010100101000001111010011100 表示無符號整數 43261596，
因此返回 964176192，其二進制表示形式為 00111001011110000010100101000000。

示例 2：

輸入：n = 11111111111111111111111111111101
輸出：3221225471 (10111111111111111111111111111111)
解釋：輸入的二進制串 11111111111111111111111111111101 表示無符號整數 4294967293，
因此返回 3221225471 其二進制表示形式為 10111111111111111111111111111111 。

提示：

• 輸入是一個長度為 32 的二進制字符串

進階: 如果多次調用這個函數，你將如何優(yōu)化你的算法？

??思路：

基礎知識必知：一篇文章搞懂位運算

法一：循環(huán)

• 將 n 視作一個長為 32 的二進制串，從低位往高位枚舉 n 的每一位，將其倒序添加到翻轉結果 ans 中。
• 代碼實現中，每枚舉一位就將 n 右移一位，這樣當前 n 的最低位就是我們要枚舉的比特位。當 n 為 0 時即可結束循環(huán)。

需要注意的是，在某些語言（如 Java）中，沒有無符號整數類型，因此對 n 的右移操作應使用邏輯右移（無符號右移）。

法二：分治

若要翻轉一個二進制串，可以將其 均分 成左右兩部分，對每部分 遞歸 執(zhí)行翻轉操作，然后將左半部分拼在右半部分的后面，即完成了翻轉。

由于左右兩部分的計算方式是相似的，利用位掩碼和位移運算，我們可以自底向上地完成這一分治流程。

對于遞歸的最底層，我們需要交換所有奇偶位：

1. 取出所有奇數位和偶數位；
2. 將奇數位移到偶數位上，偶數位移到奇數位上。

類似地，對于倒數第二層，每兩位分一組，按組號取出所有奇數組和偶數組，然后將奇數組移到偶數組上，偶數組移到奇數組上。以此類推。

??代碼：(Java、C++)

法一：循環(huán)
Java

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int ans = 0;
        for(int i = 0; i < 32; i++){
            ans <<= 1;
            ans |= (n & 1);
            n >>>= 1;
        }
        return ans;
    }
}

C++

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ans = 0;
        for(int i = 0; i < 32; i++){
            ans <<= 1;
            ans |= (n & 1);
            n >>= 1;
        }
        return ans;
    }
};

法二：分治
Java

public class Solution {
    // you need treat n as an unsigned value
    private static final int M1 = 0x55555555; // 01010101010101010101010101010101
    private static final int M2 = 0x33333333; // 00110011001100110011001100110011
    private static final int M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    private static final int M8 = 0x00ff00ff; // 00000000111111110000000011111111

    public int reverseBits(int n) {
        n = n >>> 1 & M1 | (n & M1) << 1;
        n = n >>> 2 & M2 | (n & M2) << 2;
        n = n >>> 4 & M4 | (n & M4) << 4;
        n = n >>> 8 & M8 | (n & M8) << 8;
        return n >>> 16 | n << 16;
    }
}

C++

class Solution {
private:
    const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101
    const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011
    const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111

public:
    uint32_t reverseBits(uint32_t n) {
        n = n >> 1 & M1 | (n & M1) << 1;
        n = n >> 2 & M2 | (n & M2) << 2;
        n = n >> 4 & M4 | (n & M4) << 4;
        n = n >> 8 & M8 | (n & M8) << 8;
        return n >> 16 | n << 16;
    }
};

?? 運行結果：

?? 復雜度分析：

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

題目來源：力扣。

放棄一件事很容易，每天能堅持一件事一定很酷，一起每日一題吧！
關注我 leetCode專欄，每日更新！文章來源地址http://www.zghlxwxcb.cn/news/detail-438427.html

注： 如有不足，歡迎指正！

到了這里，關于( 位運算 ) 190. 顛倒二進制位 ——【Leetcode每日一題】的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！