#190. Reverse Bits

題目描述

反轉無符號32bits整數中的bits。

限制條件

1. 輸入必須是長度為32的二進位字串。

解題思路

限制條件是給測試輸入用的，不用理會。

Divide

首先我們知道32位元整數以二進位表示會有32個數位長度，要反轉所有的位元必須要處理32次。

而我們可以知道二進位的每一個位數的差距都是2倍，因此我們可以使用簡單的除法，來做位元的移動。

public class Solution { 
	public uint reverseBits(uint n) {
        uint ans = 0;
        for(int i=0;i<32;i++){             
            ans*=2;
            if(n%2==1) ans+=1;
            n/=2;
        }
        return ans;
    }
}

複雜度分析：

• 時間複雜度：O(1)
• 空間複雜度：O(1)

Right Shift-Expression & Addition

也可以利用位元移位運算子來處理進位問題。

public class Solution { 
	public uint reverseBits(uint n) {
        uint ans = 0;
        for(int i=0;i<32;i++){             
            ans<<=1;
            if(n%2==1) ans+=1;                        
            n>>=1;            
        }                
        return ans;
    }
}

複雜度分析：

• 時間複雜度：O(1)
• 空間複雜度：O(1)

Follow-up

如果函式會被呼叫很多次，要如何提升效能呢？

學習重點

• 位元操作