Reversing a binary number

 

This post is me trying to understand the solution of an "easy" problem to reverse a binary number.

Given a 32-bit integer, return the number with its bits reversed.

For example, given the binary number 1111 0000 1111 0000 1111 0000 1111 0000, return 0000 1111 0000 1111 0000 1111 0000 1111.

and here is to solution to the code and a link to the source and a more detailed description

    // function to reverse bits of a number
    public static int reverseBits(int n)
    {
        int rev = 0;
 
        // traversing bits of 'n'
        // from the right
        while (n > 0)
        {
            // bitwise left shift
            // 'rev' by 1
            rev <<= 1;
 
            // if current bit is '1'
            if ((int)(n & 1) == 1)
                rev ^= 1;
 
            // bitwise right shift
            //'n' by 1
            n >>= 1;
        }
        // required number
        return rev;
    }

https://www.geeksforgeeks.org/reverse-actual-bits-given-number/

Understanding the problem

I should note that I don't have any experience working with bit operations and a lot of my knowledge comes from what I remember of binary math in college. That said this is an easy problem to solve with a String, however that is not the solution being sought.

I was confident that the solution involved a combination of binary operations like XOR , SHIFT , AND & OR, and I did spend a healthy amount of time attempting a solution. Here were just a few of my brainstorming thoughts -

Take-aways from the solution

The problem promised an easy solution, and indeed the code example is only a few lines of code. That doesn't necessarily make it easy to understand especially if you are not comfortable with bit operations.

While trying to understand the code here were my three take-aways -

Testing the least significant bit

The number 1, can be quite useful when combined with the "AND" operation. It will tell you whether the least significant bit of binary number is a 1 or a 0

Updating the least significant bit

The number 1 again, can be quite useful when combined with the "XOR" operation to toggle the least significant bit. XOR leaves all other bits unaffected.

Shift operations do more that halve and double

• Left Shift
• Shift operations can be used to create space in the least significant bit
• Right Shift
• They can also be used to traverse the binary number by moving the bits into the least significant