Sharing my 2ms Java Solution with Explanation


  • 71
    A

    "
    We first intitialize result to 0. We then iterate from
    0 to 31 (an integer has 32 bits). In each iteration:
    We first shift result to the left by 1 bit.
    Then, if the last digit of input n is 1, we add 1 to result. To
    find the last digit of n, we just do: (n & 1)
    Example, if n=5 (101), n&1 = 101 & 001 = 001 = 1;
    however, if n = 2 (10), n&1 = 10 & 01 = 00 = 0).

    Finally, we update n by shifting it to the right by 1 (n >>= 1). This is because the last digit is already taken care of, so we need to drop it by shifting n to the right by 1.

    At the end of the iteration, we return result.

    Example, if input n = 13 (represented in binary as
    0000_0000_0000_0000_0000_0000_0000_1101, the "_" is for readability),
    calling reverseBits(13) should return:
    1011_0000_0000_0000_0000_0000_0000_0000

    Here is how our algorithm would work for input n = 13:

    Initially, result = 0 = 0000_0000_0000_0000_0000_0000_0000_0000,
    n = 13 = 0000_0000_0000_0000_0000_0000_0000_1101

    Starting for loop:
    i = 0:
    result = result << 1 = 0000_0000_0000_0000_0000_0000_0000_0000.
    n&1 = 0000_0000_0000_0000_0000_0000_0000_1101
    & 0000_0000_0000_0000_0000_0000_0000_0001
    = 0000_0000_0000_0000_0000_0000_0000_0001 = 1
    therefore result = result + 1 =
    0000_0000_0000_0000_0000_0000_0000_0000
    + 0000_0000_0000_0000_0000_0000_0000_0001
    = 0000_0000_0000_0000_0000_0000_0000_0001 = 1

    Next, we right shift n by 1 (n >>= 1) (i.e. we drop the least significant bit) to get:
    n = 0000_0000_0000_0000_0000_0000_0000_0110.
    We then go to the next iteration.

    i = 1:
    result = result << 1 = 0000_0000_0000_0000_0000_0000_0000_0010;
    n&1 = 0000_0000_0000_0000_0000_0000_0000_0110 &
    0000_0000_0000_0000_0000_0000_0000_0001
    = 0000_0000_0000_0000_0000_0000_0000_0000 = 0;
    therefore we don't increment result.
    We right shift n by 1 (n >>= 1) to get:
    n = 0000_0000_0000_0000_0000_0000_0000_0011.
    We then go to the next iteration.

    i = 2:
    result = result << 1 = 0000_0000_0000_0000_0000_0000_0000_0100.
    n&1 = 0000_0000_0000_0000_0000_0000_0000_0011 &
    0000_0000_0000_0000_0000_0000_0000_0001 =
    0000_0000_0000_0000_0000_0000_0000_0001 = 1
    therefore result = result + 1 =
    0000_0000_0000_0000_0000_0000_0000_0100 +
    0000_0000_0000_0000_0000_0000_0000_0001 =
    result = 0000_0000_0000_0000_0000_0000_0000_0101
    We right shift n by 1 to get:
    n = 0000_0000_0000_0000_0000_0000_0000_0001.
    We then go to the next iteration.

    i = 3:
    result = result << 1 = 0000_0000_0000_0000_0000_0000_0000_1010.
    n&1 = 0000_0000_0000_0000_0000_0000_0000_0001 &
    0000_0000_0000_0000_0000_0000_0000_0001 =
    0000_0000_0000_0000_0000_0000_0000_0001 = 1
    therefore result = result + 1 =
    = 0000_0000_0000_0000_0000_0000_0000_1011
    We right shift n by 1 to get:
    n = 0000_0000_0000_0000_0000_0000_0000_0000 = 0.

    Now, from here to the end of the iteration, n is 0, so (n&1)
    will always be 0 and and n >>=1 will not change n. The only change
    will be for result <<=1, i.e. shifting result to the left by 1 digit.
    Since there we have i=4 to i = 31 iterations left, this will result
    in padding 28 0's to the right of result. i.e at the end, we get
    result = 1011_0000_0000_0000_0000_0000_0000_0000

    This is exactly what we expected to get
    "

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

  • 0
    X

    this is really amazing.


  • 0
    A

    thank you so much


  • 0
    T

    this solution is sick!! How much thought went into this?


  • 0
    A

    A lot of thought :)


  • 0
    H

    Nice explanation. And add if((n&1)==1) check is great!
    But no need to check n==0. :)


  • 0
    H

    And use result += n&1 seems more efficient.

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

  • 0
    C

    Really cool, thanks a lot


  • 0
    A

    @hu26 Thanks buddy, I appreciate it


  • 0
    A

    @John567 You are more than welcome


  • 0
    J

    Why can't I use if( n % 2) == 1) to replace if( n & 2) == 1)?


  • 0
    A

    Hi @journey0408
    We used (( n &1) == 1) not (( n & 2) == 1)

    For sure, you can go ahead and try (( n % 2) == 1)


  • 0
    S

    @journey0408 If you treat it as a normal int, it is signed by default, so there is overflow.


  • 0

    I have a question, how does it deal with 2,147,483,648, which is larger than Integer.MAX_VALUE?

    I know it works, but why this int result can store this large value?


  • 0

    @solstice1993 So you mean in Java, we can deal it as unsigned int in this way ? I saw the doc, it says:

    Use the Integer class to use int data type as an unsigned integer

    Here, in this question we use (( n & 2) == 1), and the int result will be automatically be unsigned, right?


  • 0
    A

    @zhugejunwei The question is "Reverse bits of a given 32 bits unsigned integer."


  • 0

    @arafat324 Yeah, I know what this question means.

    My question is how Java know my integer is unsigned or not. It cannot be unsigned when you say it unsigned, you should represent it as unsigned, right? So, in Java, how to represent it please?


  • 0
    M

    I do not think it is a good solution for ++ operation, maybe you can use result |= (n&1)


  • 0

    @zhugejunwei @Amadou @arafat324 @CherryDrPepper @hu26
    Why do left shift result variable first

    (n&1) should be added to result variable first, then result variable should be left shifted ?

    public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {

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

    }


  • 1
    M

    @hu26 how about this for efficiency

    for(int i=0; i<32; i++){
    result = result << 1;
    //bitwise OR is cheaper than add
    result = result | n&1;
    n = n >> 1;
    }
    

Log in to reply
 

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