190. Reverse Bits

Easy

Description

給定一個 32 位元無號整數，將其二進位反轉後回傳結果。

Example:

Input: n = 00000010100101000001111010011100 Output: 964176192 (00111001011110000010100101000000)

Intuition#

核心思路：逐位從 n 取出最低位，左移放入結果的對應位置。

想像把一個 32 位元的數字「鏡像翻轉」
每次取 n 的最低位，放到結果的高位；迭代 32 次完成反轉
也可以用分治法，先交換相鄰的 1-bit 區塊，再交換 2-bit 區塊，依此類推

Approaches#

1: 逐位反轉#

概念: 迭代 32 次，每次把 n 的最低位取出，左移放入結果
時間複雜度: O(32) = O(1)
空間複雜度: O(1)

class Solution {
    fun reverseBits(n: Int): Int {
        var result = 0
        var num = n
        for (i in 0 until 32) {
            result = result shl 1
            result = result or (num and 1)
            num = num ushr 1
        }
        return result
    }
}

⭐2: 分治法（Divide and Conquer）#

概念: 用遮罩分層交換：先交換相鄰 1 位、再交換相鄰 2 位、4 位、8 位、最後 16 位
時間複雜度: O(1) - 固定 5 步操作
空間複雜度: O(1)

class Solution {
    fun reverseBits(n: Int): Int {
        var num = n
        num = ((num and 0x55555555.toInt()) shl 1) or ((num ushr 1) and 0x55555555.toInt())
        num = ((num and 0x33333333) shl 2) or ((num ushr 2) and 0x33333333)
        num = ((num and 0x0f0f0f0f) shl 4) or ((num ushr 4) and 0x0f0f0f0f)
        num = ((num and 0x00ff00ff) shl 8) or ((num ushr 8) and 0x00ff00ff)
        num = (num shl 16) or (num ushr 16)
        return num
    }
}

Kotlin 中沒有無號整數運算子，需要用 ushr（unsigned shift right）來避免符號擴展問題。同時 0x55555555 超出 Int 正數範圍，需要 .toInt() 轉換。

補充：Integer.reverse 內建函數

Java/Kotlin 的 Integer.reverse 內部實作就是分治法：

class Solution {
    fun reverseBits(n: Int): Int {
        return Integer.reverse(n)
    }
}

🔑 Takeaways#

Pattern: 逐位處理和分治法是位元操作的兩大基本策略
關鍵技巧: 分治法用特定遮罩（0x55555555, 0x33333333 等）交換位元區塊，這組遮罩在很多位元問題中反覆出現