TIC
The Interns Company

Reverse Bits

EasyAcceptance: 50.6%
Bit Manipulation

Problem Statement

Reverse bits of a given 32 bits unsigned integer. 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.

Constraints:

  • The input must be a binary string of length 32

Input Format:

  • A 32-bit unsigned integer

Output Format:

  • Return the integer after reversing its bits

Examples:

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.

Solutions

Bit by Bit Approach

Time: O(1)
Space: O(1)

Iterate through each bit of the input integer, from right to left. For each bit, shift the result to the left by 1 and add the current bit to the result. Then shift the input to the right by 1.

Divide and Conquer Approach

Time: O(1)
Space: O(1)

Use a divide and conquer strategy to reverse bits. First, swap adjacent bits, then swap adjacent pairs of bits, then adjacent groups of 4 bits, and so on.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Initialize result = 0
  2. Iteration 1: n's rightmost bit is 0, shift result left to 0, shift n right to 21630798
  3. Iteration 2: n's rightmost bit is 0, shift result left to 0, shift n right to 10815399
  4. Iteration 3: n's rightmost bit is 1, shift result left to 0, add 1 to get result = 1, shift n right to 5407699
  5. Iteration 4: n's rightmost bit is 1, shift result left to 2, add 1 to get result = 3, shift n right to 2703849
  6. ... (continue for all 32 bits) ...
  7. Final result: 964176192 (binary: 00111001011110000010100101000000)

Hints

Hint 1
Think about how to handle each bit one by one.
Hint 2
Use bit manipulation operations like shift and OR.
Hint 3
Start with the rightmost bit of the input and add it to the leftmost position of the result.
Hint 4
Shift the result to the left by 1 and the input to the right by 1 in each iteration.

Video Tutorial

Reverse Bits - Bit Manipulation Techniques

YouTube•Learn the Reverse Bits solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the bit-by-bit reversal process, showing the original number, the current bit being processed, and the result so far.

Key visualization elements:

  • current bit
  • current result
  • remaining bits

Similar Questions

Number of 1 Bits

Easy

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight). Note that in some languages, such as Java, there is no unsigned integer type. In this case, the input will be given as a signed integer type. It should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned.

Asked By

AmazonAppleMicrosoftNvidiaQualcomm

Implementation Notes

This problem tests understanding of bit manipulation operations which are fundamental for low-level programming and optimization. The divide and conquer approach is less intuitive but more efficient in certain architectures.