Java Solution and Optimization


  • 129
    A

    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;
    }

  • 2
    O

    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;
    }
    

  • 3
    A

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


  • 0
    R

    Exactly. I think only idea matters


  • 3
    G

    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;


  • 0
    I

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


  • 0
    A

    11's binary format:

    00000000000000000000000000001011

    -805306368's binary format:

    11010000000000000000000000000000

    I think you got the right result.


  • 2
    H

    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.


  • 0
    E

    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.


  • 1
    C

    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;
        }
    }

  • 0
    M

    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!!!


  • 2
    H

    He used the cache to improve performance.


  • 2
    S

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


  • 1
    D

    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;
                
            }

  • 14
    D

    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;
    }

  • 0
    W

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


  • 5
    H

    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;
    }

  • 5

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

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

  • 0
    C

    @dugu9sword Hello! What is your optimized solution doing? a little overview would be helpful please. I am trying to get my head around the seemingly advanced bit manipulation. Thanks in advance!


  • 0
    D

    @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


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.