# Java Solution and Optimization

• The Java solution is straightforward, just bitwise operation:

``````public int reverseBits(int n) {
int result = 0;
for (int i = 0; i < 32; i++) {
result += n & 1;
n >>>= 1;   // CATCH: must do unsigned shift
if (i < 31) // CATCH: for last digit, don't shift!
result <<= 1;
}
return result;
}
``````

How to optimize if this function is called multiple times? We can divide an int into 4 bytes, and reverse each byte then combine into an int. For each byte, we can use cache to improve performance.

``````// cache
private final Map<Byte, Integer> cache = new HashMap<Byte, Integer>();
public int reverseBits(int n) {
byte[] bytes = new byte[4];
for (int i = 0; i < 4; i++) // convert int into 4 bytes
bytes[i] = (byte)((n >>> 8*i) & 0xFF);
int result = 0;
for (int i = 0; i < 4; i++) {
result += reverseByte(bytes[i]); // reverse per byte
if (i < 3)
result <<= 8;
}
return result;
}

private int reverseByte(byte b) {
Integer value = cache.get(b); // first look up from cache
if (value != null)
return value;
value = 0;
// reverse by bit
for (int i = 0; i < 8; i++) {
value += ((b >>> i) & 1);
if (i < 7)
value <<= 1;
}
cache.put(b, value);
return value;
}``````

• Same idea, but the running time is almost the same as before for test cases on OJ.

``````public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
if(base == null) {
base = new int[256];
for(int i = 0; i < 256; ++i) base[i] = reverseBitsByte(i);
}

int result = 0;
for(int i = 0; i < 4; ++i) {
int low = n&0xFF;
low = base[low];
result <<= 8;
result |= low;
n = n >>> 8;
}
return result;
}

private int reverseBitsByte(int n) {
int result = 0;
for(int i = 0; i < 8; ++i) {
int low = n&1;
result <<= 1;
result = result | low;
n = n >>> 1;
}
return result;
}

private int[] base = null;
}
``````

• I think the benefit will only be visible if the function was called repeatedly; with hits rate rising, average speed will improve.

• Exactly. I think only idea matters

• your if statement in loop body is not needed.
Since result starts with 0, you can simply do this:

result = (result<<<1) + (n & 1);
n = n >>>1;

• For input 11 in the first method, it outputs -805306368

• 11's binary format:

00000000000000000000000000001011

-805306368's binary format:

11010000000000000000000000000000

I think you got the right result.

• In your first solution, the if statement to check if i < 31 is not necessary.
just put result <<= 1 in the very beginning of the for loop.

• I feel this kind of bit manipulation doesn't make a lot of sense for Java. Most of the time this kind of bit manipulation is used in embedded system and Java is not designed for this low level work any way.

• Great solution. Here is my version based on your solution

``````public class Solution {
// you need treat n as an unsigned value
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
public int reverseBits(int n) {
int res = 0;
for(int i = 0; i < 4; i++){
int tmp = n & 0xFF;
if(map.containsKey(tmp)){
res = (res << 8) + map.get(tmp);
} else{
res = (res << 8) + reverse8Bits(tmp);
}
n >>= 8;
}

return res;
}

private int reverse8Bits(int n){
int res = 0;
int tmp = n;
for(int i = 0; i < 8; i++){
res = (res << 1) + (tmp & 1);
tmp >>= 1;
}
map.put(n, res);
return res;
}
}``````

• Sorry, I didn't understand why using the Byte can optimize.. Doesn't it still need shifting 32 bits? Could you please give me an explanation.. Thx a lot!!!

• He used the cache to improve performance.

• I don't quite understand. I mean why not simply use map<integer, integer>? Can anybody answer me? Thanks

• Same but Used bitwise | Or instead of plus

``````public int reverseBits(int n) {

int nReverse=0;

for(int i=0;i<32;i++)
{
nReverse|=n&1;  // I used OR instead of PLUS.
n>>>=1;
if(i<31)nReverse<<=1;
}

return nReverse;

}``````

• It seems that HashMap can accelerate the algorithm, but the fact is not as we hope.

If we repeat the function 10,000,000 times, the first algorithm you provide will cost 8,940 ms, the second algorithm you provide will cost 12,454 ms, while the following code will cost only 3,500 ms.

The optimized code runs slower.

I think reasons are as follows:

1.In the following code, the bit operation is QUITE FAST, no if/while/for statment, thus no branch predictions, and the efficiency of every statement will be almost 100%.

2.In the "cache" solution, the function callsbrach predictionsread/write-memory operations or even hash collisions will all contribute to the cost of time.

``````public int reverseBits(int n) {
int ret=n;
ret = ret >>> 16 | ret<<16;
ret = (ret & 0xff00ff00) >>> 8 | (ret & 0x00ff00ff) << 8;
ret = (ret & 0xf0f0f0f0) >>> 4 | (ret & 0x0f0f0f0f) << 4;
ret = (ret & 0xcccccccc) >>> 2 | (ret & 0x33333333) << 2;
ret = (ret & 0xaaaaaaaa) >>> 1 | (ret & 0x55555555) << 1;
return ret;
}``````

• You don't want to get hit by too much memory usage. It is a trade off.

• Here is my solution, 2ms.
No need to check the last digit !

``````public int reverseBits(int n) {
int result = 0;
for(int i=0; i<32; i++){
result <<= 1;
result += n&1;
n >>= 1;
}
return result;
}``````

• In a real-world-scenario I hope we would all do

``````int reverseBits(int n) {
return Integer.reverse(n);
}
``````

• @coder0h1t Take `12345678` as an example.
First step, interchange `1234` with `5678` -> `56781234`
Second step, interchange `56~~12~~` with `~~78~~34`-> `78563412`
Last step, interchange `7~5~3~1~` with `~8~6~4~2` ->`87654321`