Marc Lester Tan

This problem does not support Kotlin yet so I have to do it in Java.

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int output = 0;
        for(int i=0 ; i < 32; i++){
            // push 1 bit to the left
            output <<= 1;
            
            // check the LSB of our number and copy it to output
            if((n & 1) == 1) output |= 1;
            
            // drop the LSB from our input number
            n >>= 1;
        }
        
        return output;
    }
}

Runtime: 1 ms, faster than 100.00% of Java online submissions for Reverse Bits.
Memory Usage: 29.2 MB, less than 7.32% of Java online submissions for Reverse Bits.

The first version of my solution converts the input into a reversed binary string which is enough for the Example 1 test case but it couldn’t handle if the input is a negative value so I had to cheat and look for other people’s solution and this is by far the best solution ever.

The idea is to go through each bit using bitwise logical operators to recreate a reversed version of the input number. First, push 1 bit to the output variable. Then, for every bit, using AND operator, check if it’s a 1 and if it is, OR output with 1 to set the output LSB to 1. Finally, drop the LSB of the input number.

All in all, the time complexity would be O(1).