二進位操作: bit逆序翻轉 Reverse Bits_Leetcode_#190

Lucas Miguel on Unsplash

題目敘述: 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)

Reference:

[1] Reverse Bits - LeetCode