Reverse Bits

Reverse Bits sounds like a puzzle but it tests something practical. Can you pull bits out of a number, one by one, and place them somewhere new? That skill shows up in graphics, networking, and compression. So interviewers like it. Let us learn the clean way to do it.

🎯 The Problem

You get a number. You flip its row of bits end to end. This end-to-end flip is called a bit reversal.

The rules:

• Think of the number as a row of 32 bits.
• The first bit becomes the last bit.
• The last bit becomes the first bit.
• Return the mirrored number.

To keep the example small and clear, picture an 8-bit number 00000011, which is 3. Reverse the bits and you get 11000000, which is 192. The real problem uses 32 bits, but the idea is the same.

Input:  n = 3      (8-bit binary 00000011)
Output: 192        (8-bit binary 11000000)

Explanation: The bits 00000011 reversed end to end become 11000000.

So we mirror the bits. The bit that was on the right end moves to the left end.

Here is the mirror for the small example. The right bits swing over to the left.

🐢 Approach 1: Build a String (Brute Force)

The idea in one line: turn the number into binary text, reverse the text, turn it back.

The idea:

• Convert the number to its binary string.
• Pad it to the full width with leading zeros.
• Reverse that text like any string.
• Convert the reversed text back into a number.

Why it is weak:

• Building a string for every number is slow.
• It uses extra memory for the characters.
• You must pad carefully or you lose the leading zeros.
• The interviewer is hoping you work with the bits directly.

Here is the string-building code:

def reverse_bits(n):
    bits = bin(n)[2:].zfill(32)
    return int(bits[::-1], 2)

⚡ Approach 2: Shift Bit by Bit (Best)

The idea in one line: pull the lowest input bit and push it onto the answer, 32 times.

The idea:

• Move bits directly, with no string at all.
• The key tool is the bit shift.
• Shifting left slides every bit toward the big end.
• Shifting right slides every bit toward the small end, dropping the lowest.

How it works:

• Shift the answer left by one to make room.
• Read the lowest input bit with n & 1.
• Add that bit into the answer.
• Shift the input right by one, so the next bit becomes the lowest.
• Repeat 32 times.

Why it is fast:

• The first bit read sits at the bottom, then later shifts push it to the top.
• So the order mirrors itself naturally.
• It uses no string and only a couple of variables.

Here is a picture of the shift loop. Each step takes the lowest input bit and pushes it into the answer.

Steps to Solve

1. Set the answer to 0.
2. Repeat the next steps 32 times, once per bit.
3. Shift the answer left by one to make room.
4. Read the lowest bit of the input with n & 1.
5. Add that bit into the answer, then shift the input right by one.
6. After 32 rounds, return the answer.

#include <stdio.h>

unsigned int reverseBits(unsigned int n, int width) {
    unsigned int result = 0;
    for (int i = 0; i < width; i++) {
        result = (result << 1) | (n & 1);  // push lowest bit into result
        n >>= 1;                            // move to next input bit
    }
    return result;
}

int main(void) {
    unsigned int n = 3;                     // 8-bit 00000011
    printf("%u\n", reverseBits(n, 8));      // reverse over 8 bits
    return 0;
}

192

#include <iostream>
using namespace std;

unsigned int reverseBits(unsigned int n, int width) {
    unsigned int result = 0;
    for (int i = 0; i < width; i++) {
        result = (result << 1) | (n & 1);  // push lowest bit into result
        n >>= 1;                            // move to next input bit
    }
    return result;
}

int main() {
    unsigned int n = 3;                     // 8-bit 00000011
    cout << reverseBits(n, 8) << endl;      // reverse over 8 bits
    return 0;
}

192

public class ReverseBits {
    public static int reverseBits(int n, int width) {
        int result = 0;
        for (int i = 0; i < width; i++) {
            result = (result << 1) | (n & 1);  // push lowest bit into result
            n >>= 1;                           // move to next input bit
        }
        return result;
    }

    public static void main(String[] args) {
        int n = 3;                             // 8-bit 00000011
        System.out.println(reverseBits(n, 8)); // reverse over 8 bits
    }
}

192

def reverse_bits(n, width):
    result = 0
    for _ in range(width):
        result = (result << 1) | (n & 1)  # push lowest bit into result
        n >>= 1                           # move to next input bit
    return result


n = 3  # 8-bit 00000011
print(reverse_bits(n, 8))  # reverse over 8 bits

192

function reverseBits(n, width) {
  let result = 0;
  for (let i = 0; i < width; i++) {
    result = (result << 1) | (n & 1); // push lowest bit into result
    n >>= 1; // move to next input bit
  }
  return result >>> 0; // read as an unsigned value
}

const n = 3; // 8-bit 00000011
console.log(reverseBits(n, 8)); // reverse over 8 bits

192

Let us read the Python version line by line and see why the bits end up mirrored.

def reverse_bits(n, width):
    result = 0
    for _ in range(width):
        result = (result << 1) | (n & 1)
        n >>= 1
    return result

The line result = 0 starts the answer empty. We will fill it one bit at a time.

The line for _ in range(width): runs once per bit. For the real problem width is 32. For our small example it is 8. We use _ because we do not need the loop number, only the repeats.

The line result = (result << 1) | (n & 1) does two things. The result << 1 shifts the answer left by one, opening a fresh empty slot at the bottom. The n & 1 reads the lowest bit of the input. The | is a bit OR, which drops that read bit into the new slot. So each pass adds one input bit to the bottom of the answer.

The line n >>= 1 shifts the input right by one. The bit we just read falls off, and the next bit moves into the lowest spot, ready for the next pass.

The line return result gives back the mirrored number. Because the first bit we read sits at the bottom and then keeps getting pushed up by later shifts, it lands at the top. So the order comes out reversed.

⏱️ Time and Space Complexity

The string way builds and reverses text, which is slow and needs extra memory for the characters. The shift way does a fixed number of cheap steps, one per bit, so it is O(k) where k is the bit width, usually 32. It uses only a couple of variables, so memory is O(1). Since the bit width is fixed, people often call this constant time. The shift loop is the answer interviewers want to see.

🧩 Key Takeaways

• ✅ Reversing bits mirrors the bit order, so the right end moves to the left end.
• ✅ Shifting left makes room, and n & 1 reads the lowest input bit.
• ✅ The first bit read lands at the top after all the pushes, which mirrors the order.
• ✅ The shift method needs no string, so it uses only O(1) memory.
• ✅ With a fixed 32-bit width, the work is constant and fast.

🚀 What’s Next?

• Counting Bits
• Number of 1 Bits