[Leetcode] 190. Reverse Bits

題目敘述

Reverse bits of a given 32 bits unsigned integer.

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.

限制:

• The input must be a binary string of length 32

解題思路：

因為他要做的是把數字轉成二進制時的表達法顛倒過來（第 1 位跟第 32 位交換，第 2 為跟第 31 位交換...），

所以最重要的事情就是我們要可以知道原始數字轉成二進制的每一位數是 1 還是 0，之後把他放到相應的位數裡面。

解題步驟：

1. 宣告一個 variable result = 0（可以把他想像是 32 位全部都是 0 的二進制數字）
2. 利用迴圈對原始數字從第一位開始的每一個位數進行以下動作：
   1. 把要比對的位數不停右移直到他變成第 1 位
   2. 把第 1 位和 1 做 &，判斷他是 1 或是 0。（0 & 1 = 0, 1 & 1 = 1，所以進行 & 1 的操作就可以知道該位數是 0 還是 1）
   3. 把這個 1 或是 0 放到 result 相對應的格子裡面（因為 1 跟 0 都是在第一位數，所以需要往左移到對的地方）
3. 回傳 result

Java 解法

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int result = 0;
 
        for (int i = 0; i < 32; i ++) {
            int bit = (n >> i) & 1;
            result += (bit << 31 - i);
        }
 
        return result;
    }
}

Complexity

• Time Complexity: O(1);
• Space Complexity: O(1);