ReverseBits.java

public int reverseBits(int n) {
    int res = 0;

    for (int i = 0; i < 32; i++) {
        int t = n & 1;
        n = n >> 1;
        res = res << 1;
        res = res | t;

    }
    return res;
    // return Integer.reverse(n);
    }

public int reverseBitsWithCache(int n) {
    byte[] bytes = new byte[4];
    Map<Byte, Integer> lookup = new HashMap<>();

    int reversedResult = 0;

    for (int i = 0; i < 4; i++) {
        bytes[i] = (byte)((n >> (8 * i)) & 0xFF);
        reversedResult = reversedResult << 8;
        reversedResult = reversedResult | this.reverseByte(bytes[i], lookup);
    }

    return reversedResult;
}

public int reverseByte(byte a, Map<Byte, Integer> lookup) {
    // TODO: validate input
    if (lookup.containsKey(a)) {
        return lookup.get(a);
    }

    int reversedByte = 0;
    for (int i = 0; i < 8; i++) {
        int t = (a >> i) & 1;
        reversedByte = reversedByte << 1;
        reversedByte = reversedByte | t;
    }

    lookup.put(a, reversedByte);

    return reversedByte;
}