給定一個 32 位元無號整數，將其二進位反轉後回傳結果。
Example:
Input: n = 00000010100101000001111010011100 Output: 964176192 (00111001011110000010100101000000)
Intuition
TIP
核心思路：逐位從 n 取出最低位，左移放入結果的對應位置。
- 想像把一個 32 位元的數字「鏡像翻轉」
- 每次取 n 的最低位，放到結果的高位；迭代 32 次完成反轉
- 也可以用分治法，先交換相鄰的 1-bit 區塊，再交換 2-bit 區塊，依此類推
Approaches
1. Digit-by-Digit Reverse — O(32) / O(1)
- Idea: 迭代 32 次，每次把 n 的最低位取出，左移放入結果
- Time:
O(32)=O(1) - Space:
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 & Conquer — O(1) / O(1)
- Idea: 用遮罩分層交換：先交換相鄰 1 位、再交換相鄰 2 位、4 位、8 位、最後 16 位
- Time:
O(1)- 固定 5 步操作 - Space:
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
}
}WARNING
Kotlin 中沒有無號整數運算子，需要用 ushr（unsigned shift right）來避免符號擴展問題。同時 0x55555555 超出 Int 正數範圍，需要 .toInt() 轉換。
Note: Integer.reverse built-in
Java/Kotlin 的 Integer.reverse 內部實作就是分治法：
class Solution {
fun reverseBits(n: Int): Int {
return Integer.reverse(n)
}
}🔑 Takeaways
- Pattern: 逐位處理和分治法是位元操作的兩大基本策略
- Key trick: 分治法用特定遮罩（0x55555555, 0x33333333 等）交換位元區塊，這組遮罩在很多位元問題中反覆出現