題目敘述: Reverse Bits
給定一個32bit的整數，請逆序翻轉其二進位表達式，輸出翻轉過後的數字。
例如輸入是二進位1010111 逆序翻轉後是 1110101，對應的十進位數值是117
測試範例
Example 1:Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.
Example 2:
Input: n = 11111111111111111111111111111101
Output: 3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.
約束條件
Constraints:
- The input must be a binary string of length
32
輸入保證在32bit整數範圍內
演算法 二進位操作
逆序翻轉bit相當於從LSB低位元到MSB高位元把每個bit讀取出來，
接著反方向從MSB到LSB擺好，
最後整個binary bits representation就相當於逆序翻轉的二進位數字。
原本的數字 逆序的數字
高位元MSB ...低位元LSB <-> 低位元LSB ... 高位元MSB
例如輸入是二進位1010111 逆序翻轉後是 1110101，對應的十進位數值是117
詳細過程
1010111
讀取到1 -> 逆序輸出1
1010111
讀取到1 -> 逆序輸出11
1010111
讀取到1 -> 逆序輸出111
1010111
讀取到0 -> 逆序輸出1110
1010111
讀取到1 -> 逆序輸出11101
1010111
讀取到0 -> 逆序輸出111010
1010111
讀取到0 -> 逆序輸出1110101
最後，對應的十進位數值是117
程式碼 二進位操作
class Solution:
def reverseBits(self, n: int) -> int:
rev_bits = 0
for i in range( 32 ):
rev_bits = rev_bits << 1
# rev_bits get binary bit from LSB to MSB of n
rev_bits = rev_bits | ( n & 1 )
n = n >> 1
return rev_bits
複雜度分析
時間複雜度: O(1)
for loop長度固定為O(32) = O(1)
空間複雜度O(1)
只有用到固定尺寸的臨時變數，所需空間為O(1)
