Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

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

Related problem: Reverse Integer

Solution1: 

Run time complexity is O(n), n = 32, so it's constant. Constant space.

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        if(n == 0) {
            return 0;
        }
        
        int result = 0;
        int x = 0;
        for(int i = 1; i < 32; i++) {  //处理前31位
            x = n & 1;
            result = (result + x) << 1;
            n = n >>> 1;
        }
        
        //处理最后一位
        x = n & 1;
        result += x;
        
        return result;
    }
}

Solution2:

Run time complexity is O(n), n = 16, so it's constant. Constant space.

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        if(n == 0) {
            return 0;
        }
        
        for(int i = 0; i < 16; i++) {
            n = swapBits(n, i, 32 - i - 1);
        }
        
        return n;
    }
    
    public int swapBits(int n, int i, int j) {
        int a = (n >>> i) & 1;
        int b = (n >>> j) & 1;
        
        if((a ^ b) != 0) {
            n = n ^ ((1 << i) | (1 << j));
            return n;
        }
        return n;
    }
}

Solution3: 

Divide and conquer: http://articles.leetcode.com/2011/08/reverse-bits.html