190. Reverse Bits.md

190. Reverse Bits

Question

Reverse bits of a given 32 bits unsigned integer.

Example:

Input: 43261596
Output: 964176192
Explanation: 43261596 represented in binary as 00000010100101000001111010011100,
return 964176192 represented in binary as 00111001011110000010100101000000.

Follow up: If this function is called many times, how would you optimize it?

Thinking:

• Method 1: 首尾取出元素，并交换位置存入一个新的int型数据中。

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int low = 1;
        int high = 1 << 31;
        int result = 0;
        for(int i = 16; i >= 1; i--){
            int right = n & low;
            int left = n & high;
            left >>= i * 2 - 1;
            result += left;
            right <<= i * 2 - 1;
            result += right;
            low <<= 1;
            right >>= 1;
        }
        return result;
    }
}

二刷

1. 唯一要注意的就是右移补零是>>>

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