190. Reverse Bits

Problem Description

The goal of this problem is to reverse the bits of a given 32-bit unsigned integer. This means that every bit in the binary representation of the integer is inverted from end to start; for example, the bit at the far left end (the most significant bit) would swap places with the bit at the far right end (the least significant bit), and so on for each pair of bits in the number.

Intuition

To reverse the bits of an integer, the solution takes each bit individually from the least significant bit to the most significant bit, and places that bit into the reversed position in a new number, which would then become the most significant bit of the new number. This is repeatedly done for all 32 bits of the integer.

Starting with res as 0, which will hold the reversed bits, we loop 32 times since we're dealing with 32-bit numbers. In each iteration, we:

Check the least significant bit of n via (n & 1) which uses the bitwise AND operator to isolate the bit.
Shift this bit to its reversed position with << (31 - i), where i is the current iteration index, thus "moving" the bit to the correct position in the reversed number.
Use |= (bitwise OR assignment) to add this bit to the result res.
Right shift n by 1 with n >>= 1 to move to the next bit for the next iteration.

After the loop finishes, all bits have been reversed in res, and we return res as the answer.

Learn more about Divide and Conquer patterns.

Solution Approach

The implementation of the solution involves a straightforward approach that mostly utilizes bitwise operations. Let's walk through the algorithm step by step:

Initialize an integer res to 0. This variable will hold the reversed bits of the input.
Loop through a range of 32, because we are dealing with a 32-bit unsigned integer. For each index i in this range:

a. Isolate the least significant bit (LSB) of n by using the bitwise AND operation (n & 1). If the LSB of n is 1, the result of the operation will be 1, otherwise, it will be 0.

b. Shift the isolated bit to its reversed position. The reversed position is calculated by subtracting the loop index i from 31 (31 - i), as the most significant bit should go to the least significant position and vice versa. The operator << is used for bitwise left shift.

c. Use the bitwise OR assignment |= to add the shifted bit to res. This step effectively "builds" the reversed number by adding the bits from n in reversed order to res.

d. Right shift the input number n by 1 using n >>= 1 to proceed to the next bit for analysis in the subsequent iteration.
Once the loop is completed, all the bits from the original number n have been reversed and placed in res.
Return res as it now contains the reversed bits of the original input.

No extra data structures are needed in this approach. The solution relies solely on bitwise operations and integer manipulation. This problem is a typical example of bit manipulation technique, where understanding and applying bitwise operators is crucial to achieve the desired outcome.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider the 8-bit binary representation of the number 5 to simplify the understanding of our solution. In binary, 5 is represented as 00000101. To reverse the bits, we would want our output to be 10100000.

Now, let's walk through the steps of the solution approach using this 8-bit number (note: the actual problem expects a 32-bit number, but this simplified example serves to illustrate the approach):

We initialize res to 0, which is 00000000 in binary.
We then loop 8 times (in our simplified case), and for each i from 0 to 7 (for a 32-bit integer, i would range from 0 to 31), we:

a. Isolate the LSB of 5:
- When i = 0, n & 1 is 1 (00000101 & 00000001 equals 00000001).
b. We shift this isolated bit to its reversed position which is 7 - i (for an 8-bit number):
- When i = 0, shift 1 by 7 positions to left, we get 10000000.
c. We then use bitwise OR to add this to res:
- res is now 10000000.
d. We right shift n by 1:
- n becomes 00000010.
Repeat these steps for the remaining iterations of the loop—each time n will be shifted to the right by 1, res will have 1 added in the correct reversed position if the isolated bit from n is 1.

For instance, when i = 2, the LSB is 0 (after shifting n to the right twice). There is nothing to add to res for this bit, as shifting a 0 and OR-ing it would not change res.

Let's look at the case when i = 5, which corresponds to the third least significant 1 in our original number 5:
- n & 1 is 1 (since n was right-shifted by 5 and now is 000000000).
- Shift 1 to the left by 2 (7 - 5), we get 00000100.
- res is now 10000100 after OR-ing.
After looping 8 times (32 times for an actual 32-bit integer), res would contain the reversed bits. In our example, res would be 10100000.
Finally, we return res.

In the detailed steps of the 32-bit reversal, we would do this loop 32 times, and the resulting res would represent the reversed bits of the original 32-bit integer.

Solution Implementation

1class Solution:
2    def reverseBits(self, n: int) -> int:
3        # Initialize result as 0. This will hold the reversed bits.
4        result = 0
5      
6        # Loop over the 32 bits of the integer.
7        for i in range(32):
8            # Extract the least significant bit (LSB) using the bitwise AND operation (&)
9            # and shift it to its reversed position. Then, use the bitwise OR operation (|)
10            # to set the corresponding bit in the result.
11            # (31 - i) gives the bit's reversed position.
12            result |= (n & 1) << (31 - i)
13          
14            # Shift `n` to the right by 1 bit to process the next bit in the next iteration.
15            n >>= 1
16      
17        # Return the reversed bit pattern as an integer.
18        return result
19

1public class Solution {
2
3    /**
4     * Reverses the bits of a given integer treating it as an unsigned value.
5     *
6     * @param number The integer to reverse bits for.
7     * @return The reversed bits integer.
8     */
9    // The method name is kept as-is to maintain API contract
10    public int reverseBits(int number) {
11        // Initialize result to zero to start with a clean slate of bits
12        int result = 0;
13
14        // Loop over all the 32 bits of an integer
15        // The loop continues while there are non-zero bits remaining
16        for (int i = 0; i < 32 && number != 0; i++) {
17            // Using bitwise OR and shift to add the least significant bit of 'number' to the result
18            // (1) number & 1 isolates the least significant bit of 'number'
19            // (2) << (31 - i) moves the bit to its reversed position
20            // (3) |= assigns the bit to the correct position in result
21            result |= ((number & 1) << (31 - i));
22          
23            // Unsigned right shift the 'number' by one to process the next bit in the next iteration
24            number >>>= 1;
25        }
26
27        // Return the reversed bits integer
28        return result;
29    }
30}
31

1class Solution {
2public:
3    uint32_t reverseBits(uint32_t n) {
4        uint32_t reversedNumber = 0; // Initialize the result to represent the reversed number.
5      
6        // Loop through all 32 bits of the input number.
7        for (int bitPosition = 0; bitPosition < 32; ++bitPosition) {
8            // Isolate the least-significant bit (rightmost bit) of 'n' and shift it to the correct position
9            // in 'reversedNumber' (which starts from the leftmost bit and goes rightwards with each iteration).
10            reversedNumber |= (n & 1) << (31 - bitPosition);
11            // Shift input number 'n' right by one bit to process the next bit in the next iteration.
12            n >>= 1;
13        }
14      
15        // Return the reversed number after all 32 bits have been processed.
16        return reversedNumber;
17    }
18};
19

1/**
2 * Reverses bits of a given 32-bits unsigned integer.
3 * 
4 * @param n - A positive integer representing the 32-bits unsigned integer to be reversed.
5 * @returns A positive integer representing the reversed bits of the input.
6 */
7function reverseBits(n: number): number {
8    let result: number = 0;
9
10    // Loop through all 32 bits of the integer
11    for (let i = 0; i < 32 && n > 0; ++i) {
12        // Extract the least significant bit of 'n' and shift it to the correct position,
13        // then OR it with the result to put it in its reversed position.
14        result |= (n & 1) << (31 - i);
15      
16        // Logical shift the bits of 'n' right by 1, to process the next bit in the next iteration.
17        n >>>= 1;
18    }
19  
20    // The >>> 0 ensures the result is an unsigned 32-bit integer.
21    return result >>> 0;
22}
23

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(1). This is because the loop runs a fixed number of times (32 iterations), one for each bit in a 32-bit integer. Because this number does not depend on the size of the input, but rather on the fixed size of an integer, the time complexity is constant.

Space Complexity

The space complexity of the code is also O(1). The function uses a fixed amount of space: one variable to accumulate the result (res) and a single integer (n) whose bits are being reversed. No additional space that grows with the input size is used, so the space complexity is constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know