Reverse Bits

Difficulty: Easy

You're given a number, treated as an unsigned 32-bit integer (so it's always thought of as exactly 32 binary digits, padded with leading zeros if needed). Reverse the order of its bits, and return the number that those reversed bits represent.

In other words, the bit that was in the very first (most significant) position moves to the very last (least significant) position, and vice versa, and every bit in between mirrors around the middle the same way.

Examples

Input: n = 1 (binary: 00000000000000000000000000000001)
Output: 2147483648 (binary: 10000000000000000000000000000000)

The single 1 bit sits at the very last position; after reversing, it moves to the very first position, which is worth 2^31.

Input: n = 43261596 (binary: 00000010100101000001111010011100)
Output: 964176192 (binary: 00111001011110000010100101000000)

Reading the original 32 bits back to front produces this new bit pattern.

Input: n = 0
Output: 0

A number with no 1 bits reverses to itself.

Constraints

The input is treated as an unsigned integer represented using 32 bits.

Approach

One way to reverse the bits is to lean on their text representation: write the number out as a 32-character binary string (padding with leading zeros so it's always exactly 32 characters), reverse that string, and parse the reversed string back into a number.

A more direct approach builds the reversed number bit by bit, without ever converting to a string. Walk through all 32 bit positions of n, from its last bit to its first. At each step, pull off n's current last bit (using n & 1), shift the result being built one position to the left to make room, and drop that bit into the newly opened last position (using |). Then shift n itself one position to the right, so its next bit becomes available to pull off next. By the time all 32 bits have been moved over this way, the result holds them in exactly reversed order.

Solutions

Brute Force - Reverse the Binary String

Convert n to a 32-character binary string (padded with leading zeros), reverse the string, and parse the reversed string back into a number.

function reverseBits(n) {
  const binary = n.toString(2).padStart(32, "0");
  const reversed = binary.split("").reverse().join("");
  return parseInt(reversed, 2) >>> 0;
}

Time: O(1) - always exactly 32 characters · Space: O(1) - the 32-character string is a fixed size

Optimal - Build the Result Bit by Bit

Loop 32 times. Each time, pull the current last bit off n, shift the result left by one to make room, and OR that bit into the result's new last position. Then shift n right by one so its next bit is ready to be pulled off.

function reverseBits(n) {
  let result = 0;

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

  return result >>> 0;
}

Time: O(1) - always exactly 32 iterations · Space: O(1)