Reverse Bits

Leetcode July Challenge: 12th July

Unsigned number representation

Today’s problem is again a fun with bits, hope you enjoy this one too like the last one.

Question: Reverse bits of a given 32 bits unsigned integer.

Example 1:

Input: 00000010100101000001111010011100
Output: 00111001011110000010100101000000
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: 11111111111111111111111111111101
Output: 10111111111111111111111111111111
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, both input and output will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.

In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Follow up:

If this function is called many times, how would you optimise it?

This is a simple still interesting problem, as there are edge cases which might get overlooked if not given enough focus, apart form that it’s an easy problem.

You should read about a number being signed vs. unsigned first, as it’s important to know this concept and when they can be useful.

Simple Approach: Iterate through the number from LSB to MSB and flip the bits till there. But here we are dealing with the unsigned numbers and things get a bit tricky with unsigned numbers, and the numbers are given as the binary representation of the number too.

iterate over the bits of the given number. If bit at "ith" position is set in the input number then set the bit at (NO_OF_BITS – 1) – i in the output number. 
Here NO_OF_BITS is number of bits of our given number.
unsigned int reverseBits(unsigned int num){
    unsigned int  NO_OF_BITS = sizeof(num) * 8;
    unsigned int reverse_num = 0, i, temp;
    for (i = 0; i < NO_OF_BITS; i++){
        temp = (num & (1 << i));
        if(temp)
            reverse_num |= (1 << ((NO_OF_BITS - 1) - i));
    }
    return reverse_num;
}

Efficient Approach: without using any extra memory, i.e not using “tmp” variable.

uint32_t reverseBits(uint32_t n) {
        int pos = 31; // maintains shift
        // store reversed bits of n. Initially all bits are set to 0
        uint32_t reverse = 0;
        // do till all bits are processed
        while (pos >= 0 && n){
        // if current bit is 1, then set corresponding bit in result
            if (n & 1)
                reverse = reverse | (1 << pos);
            n >>= 1; // drop current bit (divide by 2)
            pos--;  // decrement shift by 1
        }
    return reverse;
}

Another Approach: Lookup Table:
It can be done in O(1) if we know the size of the number. We can implement it using look up table. Refer Reverse bits using lookup table in O(1) time for further details.

You can test your approach here: https://leetcode.com/problems/reverse-bits/

For more such explanatory articles and understanding of concepts, stay tuned.

Happy Coding!!!