[Java] Reverse integer

Given a 32 bit integer, reverse it.

Example:

123 becomes 321

The initial thought was to treat the integer as a bit array, swapping each from left to right.

This would have some tricks in the implementation, especially since Java uses 2's complement for negative representation, but could be done and has a complexity of O(32) at most as we consider each bit in the number.

However, turns out there is a much better approach that uses divide and conquer logic to achieve the same result:

 public static int reverseBits(int n){  
     //take half of the bits from MSB to mid portion  
     //take half of the bits from mid to LSB portion  
     //swap them  
     //repeat the process with always smaller masks and portions  
     //mask is always 32 bit in size  
   
     //initial swap, throw away 16 LSB and 16 MSB, combine them together  
     //now we have the two halves reversed  
     n = n >>> 16 | n << 16;  
   
     //mask for left portion: 1111 1111 0000 0000 1111 1111 0000 0000  
     //mask for right portion: 0000 0000 1111 1111 0000 0000 1111 1111  
     //then shift by half of previous size (8 bit)  
     n = (n & 0xff00ff00) >>> 8 | (n & 0x00ff00ff) << 8;  
   
     //mask for left portion: 1111 0000 1111 0000 1111 0000 1111 0000  
     //mask for right portion: 0000 1111 0000 1111 0000 1111 0000 1111  
     //then shift by half of previous size (4 bit)  
     n = (n & 0xf0f0f0f0) >>> 4 | (n & 0x0f0f0f0f) << 4;  
   
     //mask for left portion: 1100 1100 1100 1100 1100 1100 1100 1100  
     //mask for right portion: 0011 0011 0011 0011 0011 0011 0011 0011  
     //then shift by half of previous size (2 bit)  
     n = (n & 0xcccccccc) >>> 2 | (n & 0x33333333) << 2;  
   
     //mask for left portion: 1010 1010 1010 1010 1010 1010 1010 1010  
     //mask for right portion: 0101 0101 0101 0101 0101 0101 0101 0101  
     //then shift by half of previous size (1 bit)  
     n = (n & 0xaaaaaaaa) >>> 1 | (n & 0x55555555) << 1;  
   
     //now all the bits have been moved around in the reverse place  
     return n;  
   }  

The idea is to split the integer in two halves, shift them by half the size of the integer, and combine them back.

Repeating this process on each half will in the end give the desired result.