Reverse Bits

Easy

Nvidia

1 view

Topics:

Bit Manipulation

Reverse bits of a given 32 bits unsigned integer.

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 a signed integer type. They should not affect your implementation, as the integer's internal binary representation 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.

Example 1:

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.

Example 2:

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.

Constraints:

The input must be a binary string of length 32

Follow up: If this function is called many times, how would you optimize it?

Reverse Bits

Easy

Nvidia

1 view

Topics:

Bit Manipulation

Reverse bits of a given 32 bits unsigned integer.

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 a signed integer type. They should not affect your implementation, as the integer's internal binary representation 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.

Example 1:

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.

Example 2:

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.

Constraints:

The input must be a binary string of length 32

Follow up: If this function is called many times, how would you optimize it?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the input guaranteed to be a 32-bit unsigned integer, or should I handle potential invalid inputs?
Are we optimizing for space or instruction count (time complexity is implied, but clarifying which operations to reduce could be relevant)?
What is the expected behavior if the input is zero?
Can I assume that the reversed number should also be interpreted as an unsigned integer?
Besides reversing the bits, are there any specific formatting or output requirements for the reversed integer?

Brute Force Solution

Approach

The core idea is to flip the order of the bits in the given number. We'll examine each bit individually, determine its new position, and place it there.

Here's how the algorithm would work step-by-step:

Look at each bit of the number one at a time, starting from the rightmost bit.
For each bit, figure out what its new position will be after the reversal (e.g., the rightmost bit becomes the leftmost bit).
Move that bit to its new position.
Repeat this process for every bit in the number.
Combine all the repositioned bits to form the final reversed number.

Code Implementation

def reverse_bits_brute_force(number):
    reversed_number = 0

    for bit_index in range(32):
        # Check if the current bit is set.
        if (number >> bit_index) & 1:

            # Move the current bit to its reversed position.
            reversed_number |= 1 << (31 - bit_index)

    return reversed_number

Big(O) Analysis

Time Complexity

O(1) – The algorithm iterates through each bit of the input number. Since the input is a 32-bit integer, the loop runs a fixed 32 times, irrespective of the specific value of the integer. Therefore, the time complexity is constant and independent of the input value, resulting in O(1).

Space Complexity

O(1) – The plain English explanation suggests operating directly on the input number's bits without creating any auxiliary data structures like lists or arrays to store intermediate bit values. Only a few variables might be used to keep track of the current bit position or the new position after reversal. Therefore, the space required remains constant regardless of the size of the input number. Thus the space complexity is O(1).

Optimal Solution

Approach

The key to efficiently reversing the bits of a number is to swap pairs of bits strategically. Instead of individually moving each bit, we'll focus on swapping bits across the number in a series of stages to achieve the reversal quickly.

Here's how the algorithm would work step-by-step:

First, swap adjacent pairs of bits.
Then, swap pairs of bits that are two positions apart.
Next, swap pairs of bits that are four positions apart.
Continue this pattern, doubling the distance between the bits being swapped in each step until you've swapped bits across half the number.
This process efficiently reorganizes the bits, resulting in the reversed bit pattern.

Code Implementation

def reverse_bits(number):
    reversed_number = 0

    # Swap adjacent bits
    number = (number & 0x55555555) << 1 | (number & 0xAAAAAAAA) >> 1

    # Swap pairs of bits that are two positions apart
    number = (number & 0x33333333) << 2 | (number & 0xCCCCCCCC) >> 2

    # Swap nibbles (4 bits)
    number = (number & 0x0F0F0F0F) << 4 | (number & 0xF0F0F0F0) >> 4

    # Swap bytes (8 bits)
    number = (number & 0x00FF00FF) << 8 | (number & 0xFF00FF00) >> 8

    # Swap 16-bit halves
    number = (number & 0x0000FFFF) << 16 | (number & 0xFFFF0000) >> 16

    reversed_number = number
    return reversed_number

Big(O) Analysis

Time Complexity

O(log n) – The algorithm performs a series of bit swaps, where in each step the distance between the swapped bits doubles. Specifically, we swap bits 1 position apart, then 2 positions apart, then 4, then 8, and so on. If the input integer has n bits, the number of steps required is proportional to the number of times we can double the distance until we reach half the size of n. This iterative doubling until we reach n can be expressed logarithmically as log base 2 of n, hence O(log n).

Space Complexity

O(1) – The algorithm described in the plain English explanation only involves swapping bits using bitwise operations. No auxiliary data structures like arrays, lists, or hash maps are created to store intermediate results. The operations are performed in place, and the algorithm utilizes only a few constant space variables for managing the bit swaps, independent of the input size N, which represents the number being reversed.

Edge Cases

Case	How to Handle
Input n is 0	The reversed bits of 0 is also 0, so the algorithm should return 0.
Input n is a power of 2 (e.g., 1, 2, 4, 8)	This tests the shifting and bit manipulation logic to ensure correct reversal.
Input n is 2^31 - 1 (maximum positive signed 32-bit integer represented as unsigned)	Check for integer overflow during bit manipulation.
Input n is 2^32 - 1 (all bits are 1)	This tests the case where all bits need to be flipped.
Input n has leading zeros (already reversed)	The algorithm should still correctly reverse the bits, even if the input seems pre-processed.
Input n is close to the maximum unsigned 32 bit integer (2^32 - 2 or 2^32 - 3)	This tests edge cases regarding the upper limit and bit manipulation correctness when the MSB is flipped.
Input n contains alternating bits (e.g., 010101... or 101010...)	Tests the algorithm's ability to correctly flip a pattern.
Algorithm performs excessive bit shifts or iterations	Verify performance, the algorithm should complete in a fixed number of operations proportional to the bit size (32).