easy

Reverse Bits

Reverse the bits of a 32-bit unsigned integer.

1. Define the problem

Reverse Bits

Given a 32-bit unsigned integer n, return n with its bits reversed . Walk 32 times, each time taking the lowest bit of n and appending it to the top of a result accumulator, then shifting n right to expose the next bit.

Constraints

  • The input is a 32-bit unsigned integer

Example

Inputn = 00000010100101000001111010011100 (binary)
Output964176192 (00111001011110000010100101000000 binary)

Explanation The 32 bits of n are reversed end to end.

2. Know the words first

In plain terms

Unsigned integer
A 32-bit number treated as always non-negative, using all 32 bits for magnitude with none reserved for a sign.
3. Visualize the solution

Peel the lowest bit off n, stack it onto the result

Peel the lowest bit off n, stack it onto the result
Statusinit

Simplified to 8 bits for the illustration: n = 10110001. Lowest bit is 1.

What happens in this step

n = 10110001

Reading n's bits from the top (bit 7) down to the bottom (bit 0): 1,0,1,1,0,0,0,1. The lowest bit (bit 0) is 1 — that bit will be peeled off first and become the top bit of the reversed result.
Step 1 of 5

Steps to visualize

  1. Start result at 0.
  2. For each of 32 rounds: shift result left by 1, then OR in the lowest bit of n.
  3. Shift n right by 1 to expose the next bit.
  4. After 32 rounds, result holds n with every bit reversed.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Peel the lowest bit off n, stack it onto the result
Statusinit

Simplified to 8 bits for the illustration: n = 10110001. Lowest bit is 1.

What happens in this step

n = 10110001

Reading n's bits from the top (bit 7) down to the bottom (bit 0): 1,0,1,1,0,0,0,1. The lowest bit (bit 0) is 1 — that bit will be peeled off first and become the top bit of the reversed result.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function reverseBits(n) {
  let result = 0;

  for (let i = 0; i < 32; i++) {
    result = (result << 1) | (n & 1);
    n >>>= 1;
  }

  return result >>> 0;
}
Time
O(1), always exactly 32 rounds
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
n = 43261596964176192example from the docstring
n = 42949672954294967295all 32 bits set reverses to itself
n = 00no bits set reverses to itself
n = 12147483648a single low bit moves to the top of the 32-bit word
n = 21474836481a single high bit moves to the bottom of the 32-bit word
n = 42949672933221225471a value with mostly set bits and two zeros

Keep reading

TopicDescription
Bit ManipulationUse AND, OR, XOR, and shifts to solve problems directly on the binary representation of numbers, often in O(1) space.
Single NumberFind the one number in an array that does not appear exactly twice.
Number of 1 BitsCount how many bits are set to 1 in the binary form of a number.
Counting BitsFor every number up to n, count how many bits are set to 1 in its binary form.
Missing NumberFind the one number missing from a list containing n distinct numbers from 0 to n.
Single Number IIFind the one number in an array that does not appear exactly three times.