190. Reverse Bits (Easy)

Problem

Reverse the bits of a given 32-bit unsigned integer.

Example

• Input: 00000010100101000001111010011100 → Output: 00111001011110000010100101000000
• Input: 11111111111111111111111111111101 → Output: 10111111111111111111111111111111

LeetCode 190 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Bit-by-bit shift

Python

def reverse_bits(n):
    result = 0
    for _ in range(32):                     # L1: always 32 iterations
        result = (result << 1) | (n & 1)    # L2: O(1), shift result and OR in LSB
        n >>= 1                             # L3: O(1), shift input right
    return result

TypeScript

function reverseBits(n: number): number {
    let result = 0;
    for (let i = 0; i < 32; i++) {          // L1: always 32 iterations
        result = ((result << 1) | (n & 1)) >>> 0; // L2: O(1), shift result and OR in LSB
        n >>>= 1;                            // L3: O(1), shift input right (unsigned)
    }
    return result >>> 0;
}

Go

func reverseBits(n uint32) uint32 {
    var result uint32
    for i := 0; i < 32; i++ {              // L1: always 32 iterations
        result = (result << 1) | (n & 1)   // L2: O(1), shift result and OR in LSB
        n >>= 1                            // L3: O(1), shift input right
    }
    return result
}

Swift

final class Solution {
    func reverseBits(_ n: UInt32) -> UInt32 {
        var value = n
        var result: UInt32 = 0
        for _ in 0..<32 {
            result = (result << 1) | (value & 1)
            value >>= 1
        }
        return result
    }
}

Where the time goes, line by line

Variables: B = 32 (fixed bit width).

Line	Per-call cost	Times executed	Contribution
L1-L3 (bit loop)	$O(1)$	32	$O(1)$ ← dominates (constant)
L2 (shift + OR)	$O(1)$	32	$O(1)$
L3 (shift input)	$O(1)$	32	$O(1)$

All 32 iterations are constant-time; the whole function is $O(1)$.

Complexity

• Time: $O(32)$ = $O(1)$, driven by L1/L2/L3 (32 fixed iterations).
• Space: $O(1)$.

Approach 2: String conversion (cheating)

Python

def reverse_bits(n):
    return int(f"{n:032b}"[::-1], 2)        # L1: O(32) format + reverse + parse

TypeScript

function reverseBits(n: number): number {
    return parseInt(n.toString(2).padStart(32, '0').split('').reverse().join(''), 2); // L1: O(32)
}

Go

import (
    "fmt"
    "strconv"
)

func reverseBits(n uint32) uint32 {
    s := fmt.Sprintf("%032b", n)                    // L1: O(32) format to binary string
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]    // L2: O(32) reverse in place
    }
    val, _ := strconv.ParseUint(string(runes), 2, 32) // L3: O(32) parse
    return uint32(val)
}

Swift

final class Solution {
    func reverseBits(_ n: UInt32) -> UInt32 {
        let binary = String(n, radix: 2)
        let padded = String(repeating: "0", count: 32 - binary.count) + binary
        return UInt32(String(padded.reversed()), radix: 2) ?? 0
    }
}

Where the time goes, line by line

Variables: B = 32 (fixed bit width).

Line	Per-call cost	Times executed	Contribution
L1 (format + reverse + parse)	$O(32)$	1	$O(1)$ ← dominates (constant)

Complexity

• Time: $O(32)$ = $O(1)$.
• Space: $O(32)$ = $O(1)$ for the string.

Clear and short, but doesn’t show bit mechanics.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Byte-wise swap with masks (mask-and-swap)

For a fixed-size reversal, use two-way swap on halves: swap 16-bit halves, then 8-bit, then 4-bit, then 2-bit, then 1-bit. Each step uses a constant mask.

Python

def reverse_bits(n):
    n = ((n >> 16) | (n << 16)) & 0xFFFFFFFF           # L1: swap 16-bit halves
    n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)   # L2: swap bytes
    n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)   # L3: swap nibbles
    n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)   # L4: swap pairs
    n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)   # L5: swap individual bits
    return n & 0xFFFFFFFF

TypeScript

function reverseBits(n: number): number {
    n = (((n >>> 16) | (n << 16)) >>> 0);                           // L1: swap 16-bit halves
    n = (((n & 0xFF00FF00) >>> 8) | ((n & 0x00FF00FF) << 8)) >>> 0; // L2: swap bytes
    n = (((n & 0xF0F0F0F0) >>> 4) | ((n & 0x0F0F0F0F) << 4)) >>> 0; // L3: swap nibbles
    n = (((n & 0xCCCCCCCC) >>> 2) | ((n & 0x33333333) << 2)) >>> 0; // L4: swap pairs
    n = (((n & 0xAAAAAAAA) >>> 1) | ((n & 0x55555555) << 1)) >>> 0; // L5: swap individual bits
    return n >>> 0;
}

Go

func reverseBits(n uint32) uint32 {
    n = (n >> 16) | (n << 16)                                    // L1: swap 16-bit halves
    n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)       // L2: swap bytes
    n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)       // L3: swap nibbles
    n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)       // L4: swap pairs
    n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)       // L5: swap individual bits
    return n
}

Swift

final class Solution {
    func reverseBits(_ n: UInt32) -> UInt32 {
        var value = (n >> 16) | (n << 16)
        value = ((value & 0xFF00_FF00) >> 8) | ((value & 0x00FF_00FF) << 8)
        value = ((value & 0xF0F0_F0F0) >> 4) | ((value & 0x0F0F_0F0F) << 4)
        value = ((value & 0xCCCC_CCCC) >> 2) | ((value & 0x3333_3333) << 2)
        value = ((value & 0xAAAA_AAAA) >> 1) | ((value & 0x5555_5555) << 1)
        return value
    }
}

Where the time goes, line by line

Variables: B = 32 (fixed bit width), 5 mask-and-swap stages.

Line	Per-call cost	Times executed	Contribution
L1-L5 (mask swaps)	$O(1)$	5	$O(1)$ ← dominates (constant)

Five constant-time bitwise operations regardless of input value.

Complexity

• Time: $O(1)$. Constant number of bitwise operations.
• Space: $O(1)$.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift notes

UInt32 makes the 32-bit width part of the method signature. Right shifts insert zero bits, left shifts stay in the unsigned representation, and every mask has the intended width. The string approach allocates, while the mask-and-swap version performs a fixed sequence of UInt32 operations.

Summary

Approach	Time	Space
Bit-by-bit	$O(32)$	$O(1)$
String reversal	$O(32)$	$O(32)$
Mask-and-swap	$O(1)$	$O(1)$

Mask-and-swap is the classic “known-width bit reversal” trick, also used in FFT bit-reversal permutations.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_190.py and run.
# Uses the canonical implementation (Approach 1: bit-by-bit, clearest for verification).

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

def _run_tests():
    assert reverse_bits(0b00000010100101000001111010011100) == 0b00111001011110000010100101000000
    assert reverse_bits(0b11111111111111111111111111111101) == 0b10111111111111111111111111111111
    assert reverse_bits(0) == 0                  # all zeros stay zero
    assert reverse_bits(0xFFFFFFFF) == 0xFFFFFFFF  # all ones stay all ones
    assert reverse_bits(1) == 0x80000000         # single LSB becomes MSB
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function reverseBits(n: number): number {
    let result = 0;
    for (let i = 0; i < 32; i++) {
        result = ((result << 1) | (n & 1)) >>> 0;
        n >>>= 1;
    }
    return result >>> 0;
}

console.assert(reverseBits(43261596) === 964176192);
console.assert(reverseBits(4294967293) === 3221225471);
console.assert(reverseBits(0) === 0);
console.assert(reverseBits(4294967295) === 4294967295);
console.assert(reverseBits(1) === 2147483648);
console.log("all tests pass");

Go

func reverseBits(n uint32) uint32 {
    var result uint32
    for i := 0; i < 32; i++ {
        result = (result << 1) | (n & 1)
        n >>= 1
    }
    return result
}

Related data structures

• None.

Related concepts

• Bit Manipulation, the binary representation pattern for masks, toggles, shifts, and arithmetic shortcuts.
• Math and Number Theory, the arithmetic invariant behind digits, divisibility, modulo behavior, and identities.