@dsadaily

  • Home
  • Tags
  • About
  • TryMe

Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

Problem Statement

LeetCode-190: Reverse bits of a given 32 bits unsigned integer.

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

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

Approach

  1. The idea is to iterate over the 32 bits of the given integer and extract the last bit of the integer. We can do this by performing a bitwise AND operation with 1.
  2. Then shift the result to the left by 1 and add the extracted bit to the result.
  3. Finally, shift the given integer to the right by 1.

Implementation

Here is a java implementation:

public int reverseBits(int n) {
    int res = 0;

    for(int i=0; i < 32; i++){
        // extract last bit
        int bit = n & 1; 
        // shift result to left by 1 and add extracted bit
        res = res << 1;
        res+= bit;
        // shift given integer to right by 1
        n = n >> 1;
    }   
    return res;
}

Complexity Analysis

The time complexity for this approach is $O(1)$ as we are iterating over 32 bits of the given integer. The space complexity is also $O(1)$ as we are using only a constant amount of space to store res and intermediate values.

See Also

Be notified of new posts. Subscribe to the RSS feed.