https://leetcode.com/problems/reverse-bits/

bitwise op

In java there is >> and >>>, the difference is >>> is used for unsigned right shift.
For all the 32 bits in the unsigned int n, we read one bit by one bit.
Add to the new int result, then left shit one bit to let the new tail bit coming in.

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int rst = 0;
        for (int i = 0; i < 32; i++) {
            rst <<= 1;
            rst += n & 1;
            n >>>= 1;
        }
        return rst;
    }
}

optimize

If multiple calls to the function, we could use some Map to cache the intermediate result. For this question, we can
divide one integer into 4 bytes and cache the reversed bits of each bytes. If later we see the same byte, we don’t need
to re-compute the result again.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class Solution {
    // you need treat n as an unsigned value
    Map<Byte, Integer> cache = new HashMap<>();
    public int reverseBits(int n) {
        byte[] rst = new byte[4];
        for (int i = 0; i < 4; i++) {
            rst[i] = (byte) (n & 0xff);
            n >>>= 8;
        }
        int result = 0;
        for (int i = 0; i < 4; i++) {
            result <<= 8;
            result |= helper(rst[i]);
        }
        return result;
    }
    private int helper(byte b){
        if (cache.containsKey(b)) {
            return cache.get(b);
        }
        int rst = 0;
        for (int i = 0; i < 8; i++) {
            rst <<= 1;
            rst |= (b >>> i) & 1;
        }
        cache.put(b, rst);
        return rst;
    }
}