Problem Types - Learning Module

Loading content...

0/276

Reverse Bits

Flipping the Binary World

Reversing the bits of an integer is one of the most instructive exercises in bit manipulation. At first glance, it seems trivially simple: just flip all the bits from left to right. But this problem reveals subtle complexities about bit positions, word sizes, and the art of constructing a result one bit at a time.

Bit reversal appears in surprising places: the Fast Fourier Transform (FFT) algorithm requires bit-reversal permutations, hardware interfaces sometimes transmit bits in reversed order, cryptographic algorithms use it for diffusion, and networking protocols may require byte or bit reordering between big-endian and little-endian systems.

This deceptively simple problem will teach you to think about integers as ordered sequences of bits rather than abstract numbers—a fundamental shift in perspective for bit manipulation mastery.

What You Will Master

By the end of this page, you will understand multiple algorithms for bit reversal—from the straightforward bit-by-bit approach to sophisticated O(log n) divide-and-conquer methods. You'll learn about lookup table optimization, understand why word size matters, and see how these techniques apply to real-world systems.

Understanding the Problem Precisely

Before diving into solutions, let's define the problem precisely. Bit reversal means rearranging the bits of an n-bit integer so that the bit at position i moves to position (n-1-i) for all positions from 0 to n-1.

Defining positions: We'll use the convention where position 0 is the least significant bit (LSB) on the right, and position n-1 is the most significant bit (MSB) on the left.

Example with 8 bits:

Original:  76543210  (bit positions)
           10110100  (bit values)
                  
Reversed:  01234567  (original positions now here)
           00101101  (bit values after reversal)

The bit that was at position 0 (value 0) is now at position 7. The bit that was at position 7 (value 1) is now at position 0.

Bit Reversal: Position Mapping (8-bit Example)
Original Position	Original Bit	→	New Position	Bit Value
7 (MSB)	1	→	0 (LSB)	1
6	0	→	1	0
5	1	→	2	1
4	1	→	3	1
3	0	→	4	0
2	1	→	5	1
1	0	→	6	0
0 (LSB)	0	→	7 (MSB)	0

Word Size Matters!

The result of bit reversal depends on the word size! Reversing the 8-bit value 0b10110100 gives 0b00101101. But reversing the same value as a 32-bit integer gives a completely different result because we're now moving 32 bits around, not 8.

• 8-bit reversal of 180: 45 • 16-bit reversal of 180: 11520 • 32-bit reversal of 180: 754974720

Always know your word size when doing bit reversal!

Mathematical formulation:

For an n-bit unsigned integer x, the bit-reversed value y is defined as:

y = Σ (for i from 0 to n-1) of: bit(x, i) × 2^(n-1-i)

Where bit(x, i) = (x >> i) & 1 extracts the bit at position i.

Alternatively: for each bit position i, if the bit is set in x, set bit (n-1-i) in y.

The Naive Approach: Bit-by-Bit Reversal

The most straightforward approach processes each bit individually: extract each bit from the input, and place it in the mirror position in the output.

Algorithm:

Initialize the result to 0
For each of the n bit positions (0 to n-1):
- Extract the bit at position i from the input
- Set the bit at position (n-1-i) in the result
Return the result

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function reverseBitsNaive(x: number, numBits: number = 32): number {
    let result = 0;
    
    for (let i = 0; i < numBits; i++) {
        // Extract bit at position i
        const bit = (x >>> i) & 1;
        
        // Place it at position (numBits - 1 - i)
        if (bit === 1) {
            result |= (1 << (numBits - 1 - i));
        }
    }
    
    return result >>> 0;  // Convert to unsigned 32-bit
}
 
// Example: Reverse 8 bits of 180 (0b10110100)
console.log(reverseBitsNaive(0b10110100, 8).toString(2));  
// Output: "101101" (which is 45, padded: 00101101)
 
// Example: Reverse all 32 bits of 180
console.log(reverseBitsNaive(180, 32));  
// Output: 754974720
 
// Trace for 8-bit reversal of 180:
// i=0: bit=0, place at pos 7 → result = 0b00000000
// i=1: bit=0, place at pos 6 → result = 0b00000000
// i=2: bit=1, place at pos 5 → result = 0b00100000
// i=3: bit=0, place at pos 4 → result = 0b00100000
// i=4: bit=1, place at pos 3 → result = 0b00101000
// i=5: bit=1, place at pos 2 → result = 0b00101100
// i=6: bit=0, place at pos 1 → result = 0b00101100
// i=7: bit=1, place at pos 0 → result = 0b00101101 = 45 ✓

An alternative formulation that's often seen builds the result by shifting it left and adding bits from the right:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function reverseBitsShiftAccumulate(x: number, numBits: number = 32): number {
    let result = 0;
    
    for (let i = 0; i < numBits; i++) {
        // Shift result left to make room for the next bit
        result <<= 1;
        
        // Add the rightmost bit of x to result
        result |= (x & 1);
        
        // Shift x right to expose the next bit
        x >>>= 1;
    }
    
    return result >>> 0;
}
 
// Trace for 8-bit reversal of 180 (0b10110100):
// Initial: x=10110100, result=0
//
// i=0: result=0<<1=0, result|=(x&1)=0, x>>>=1 → x=01011010, result=0
// i=1: result=0<<1=0, result|=(x&1)=0, x>>>=1 → x=00101101, result=0
// i=2: result=0<<1=0, result|=(x&1)=1, x>>>=1 → x=00010110, result=1
// i=3: result=1<<1=10, result|=(x&1)=0, x>>>=1 → x=00001011, result=10
// i=4: result=10<<1=100, result|=(x&1)=1, x>>>=1 → x=00000101, result=101
// i=5: result=101<<1=1010, result|=(x&1)=1, x>>>=1 → x=00000010, result=1011
// i=6: result=1011<<1=10110, result|=(x&1)=0, x>>>=1 → x=00000001, result=10110
// i=7: result=10110<<1=101100, result|=(x&1)=1, x>>>=1 → x=00000000, result=101101
//
// Final: result = 00101101 = 45 ✓
 
console.log(reverseBitsShiftAccumulate(0b10110100, 8).toString(2));
// Output: "101101" (45)

Complexity Analysis

Time Complexity: O(n) where n is the number of bits (typically 32 or 64)

Space Complexity: O(1) extra space

For a fixed word size like 32 bits, this is O(1) time. However, 32 loop iterations with bit operations may be slow for performance-critical applications. Can we do better?

Divide and Conquer: Logarithmic Approach

The divide-and-conquer approach is one of the most elegant algorithms in bit manipulation. Instead of moving each bit individually, we swap progressively larger groups of bits in log₂(n) steps.

The insight: Bit reversal can be decomposed into a series of pairwise swaps at different scales:

First, swap adjacent bits (groups of 1)
Then, swap adjacent pairs of bits (groups of 2)
Then, swap adjacent nibbles (groups of 4)
Then, swap adjacent bytes (groups of 8)
Finally, swap adjacent 16-bit halves (groups of 16)

After log₂(32) = 5 steps, all bits are in reversed position!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function reverseBitsDivideConquer(x: number): number {
    // Step 1: Swap adjacent bits (groups of 1)
    // Odd bits go left, even bits go right
    //   Mask 0xAAAAAAAA = 10101010... selects odd positions
    //   Mask 0x55555555 = 01010101... selects even positions
    x = ((x & 0xAAAAAAAA) >>> 1) | ((x & 0x55555555) << 1);
    
    // Step 2: Swap adjacent pairs (groups of 2)
    //   Mask 0xCCCCCCCC = 11001100... selects positions 2,3,6,7,...
    //   Mask 0x33333333 = 00110011... selects positions 0,1,4,5,...
    x = ((x & 0xCCCCCCCC) >>> 2) | ((x & 0x33333333) << 2);
    
    // Step 3: Swap adjacent nibbles (groups of 4)
    //   Mask 0xF0F0F0F0 = 11110000... selects high nibbles
    //   Mask 0x0F0F0F0F = 00001111... selects low nibbles
    x = ((x & 0xF0F0F0F0) >>> 4) | ((x & 0x0F0F0F0F) << 4);
    
    // Step 4: Swap adjacent bytes (groups of 8)
    //   Mask 0xFF00FF00 selects bytes 1,3
    //   Mask 0x00FF00FF selects bytes 0,2
    x = ((x & 0xFF00FF00) >>> 8) | ((x & 0x00FF00FF) << 8);
    
    // Step 5: Swap 16-bit halves (groups of 16)
    x = (x >>> 16) | (x << 16);
    
    return x >>> 0;  // Convert to unsigned
}
 
console.log(reverseBitsDivideConquer(0b10110100).toString(2).padStart(32, '0'));
// Reverses all 32 bits

Let's visualize how this works with an 8-bit example:

Reversing 10110100:

Divide and Conquer Trace (8-bit example)
Step	Operation	Before	After	Explanation
Initial	—	10110100	10110100	Original value
Step 1	Swap bits	10110100	01111000	Adjacent single bits swapped
Step 2	Swap pairs	01111000	11011000	Adjacent 2-bit groups swapped
Step 3	Swap nibbles	11011000	00101101	High/low nibbles swapped

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// Let's trace through reversing 8-bit value 0b10110100 (180)
// Using simplified 8-bit version of the algorithm
 
let x = 0b10110100;
console.log("Initial:", x.toString(2).padStart(8, '0'));
 
// Step 1: Swap adjacent bits
// Masks: 0xAA = 10101010, 0x55 = 01010101
// Original:  10 11 01 00
// Odd bits:  1_ 1_ 0_ 0_  → extracted: 10 10 00 00
// Even bits: _0 _1 _1 _0  → extracted: 00 01 01 00
// Shifted:   01 01 00 00  (odd>>1) and 00 10 10 00 (even<<1)
// Combined:  01 11 10 00
x = ((x & 0xAA) >>> 1) | ((x & 0x55) << 1);
console.log("Step 1 (swap bits):", x.toString(2).padStart(8, '0'));
// Result: 01111000
 
// Step 2: Swap adjacent pairs
// Masks: 0xCC = 11001100, 0x33 = 00110011
// Current:  01 11 10 00
// High pairs: 01__ 10__  → 0100 1000
// Low pairs:  __11 __00  → 0011 0000
// Shifted:  __01 __10  and 11__ 00__
// Combined: 1101 0010 → wait, let me recalculate...
 
// Actually for 8 bits:
// 01111000 & 11001100 = 01001000, shift right 2 → 00010010
// 01111000 & 00110011 = 00110000, shift left 2  → 11000000
// Combined: 11010010 → Hmm, let me show the correct 8-bit version
 
function reverseBits8(x: number): number {
    x = ((x & 0xAA) >>> 1) | ((x & 0x55) << 1);  // Swap adjacent bits
    x = ((x & 0xCC) >>> 2) | ((x & 0x33) << 2);  // Swap adjacent pairs
    x = ((x & 0xF0) >>> 4) | ((x & 0x0F) << 4);  // Swap nibbles
    return x & 0xFF;
}
 
console.log("8-bit reversal of 180:", reverseBits8(180).toString(2).padStart(8, '0'));
// Output: 00101101 = 45 ✓

Why This Works

This algorithm works because bit reversal is self-similar at different scales. Think of it like reversing a word by first reversing each letter's strokes, then reversing pairs of letters, then reversing the whole word. Each step brings elements closer to their final positions through hierarchical swapping.

Complexity Analysis:

Metric	Value	Notes
Time	O(log n)	5 steps for 32 bits, 6 for 64 bits
Operations	10 ops for 32-bit	2 ops per step (mask+shift twice)
Space	O(1)	Only uses the variable and constants
Dependencies	Low	Steps are independent after prior step

This is a significant improvement over the O(n) naive approach for large word sizes!

Lookup Table Optimization

For maximum performance when reversing bits repeatedly, we can precompute a lookup table of reversed values for smaller chunks (typically bytes) and combine them.

The strategy:

Precompute reversed values for all 256 possible byte values
For a 32-bit integer, split into 4 bytes
Look up the reversed value for each byte
Reassemble the bytes in reversed order

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// Precompute the reversed values for all bytes (0-255)
function buildReverseLookupTable(): Uint8Array {
    const table = new Uint8Array(256);
    
    for (let i = 0; i < 256; i++) {
        // Reverse 8 bits of value i
        let reversed = 0;
        let value = i;
        for (let bit = 0; bit < 8; bit++) {
            reversed = (reversed << 1) | (value & 1);
            value >>>= 1;
        }
        table[i] = reversed;
    }
    
    return table;
}
 
// Build table once at initialization
const REVERSE_TABLE = buildReverseLookupTable();
 
// Now reversing any byte is O(1)
console.log("Reversed 180:", REVERSE_TABLE[180]);  // 45
 
// For 32-bit integers, we split and recombine
function reverseBitsLookup(x: number): number {
    return (
        (REVERSE_TABLE[x & 0xFF] << 24) |
        (REVERSE_TABLE[(x >>> 8) & 0xFF] << 16) |
        (REVERSE_TABLE[(x >>> 16) & 0xFF] << 8) |
        (REVERSE_TABLE[(x >>> 24) & 0xFF])
    ) >>> 0;
}
 
// Example:
const value = 0x12345678;
console.log("Original:", value.toString(16));
console.log("Reversed:", reverseBitsLookup(value).toString(16));
 
// The lookup table for bytes 0-15 (for illustration):
// 0 (0000) → 0 (0000)
// 1 (0001) → 8 (1000)
// 2 (0010) → 4 (0100)
// 3 (0011) → 12 (1100)
// 4 (0100) → 2 (0010)
// 5 (0101) → 10 (1010)
// 6 (0110) → 6 (0110)
// 7 (0111) → 14 (1110)
// 8 (1000) → 1 (0001)
// 9 (1001) → 9 (1001)
// 10 (1010) → 5 (0101)
// 11 (1011) → 13 (1101)
// 12 (1100) → 3 (0011)
// 13 (1101) → 11 (1011)
// 14 (1110) → 7 (0111)
// 15 (1111) → 15 (1111)

Lookup Table Approach Complexity
Metric	Build Phase	Query Phase	Notes
Time	O(256 × 8) = O(1)	O(4) = O(1)	Constant time operations
Space	256 bytes	0 extra	Small fixed-size table
Operations per query	N/A	4 lookups + 4 shifts + 3 ORs	~11 operations total
Cache behavior	N/A	Excellent	256 bytes fits in L1 cache

Why Use Bytes?

We could use 16-bit chunks (65,536 entries) for fewer lookups, but the table would be 64KB—too large for L1 cache. The 256-byte table for 8-bit chunks provides an excellent balance between lookup count and cache efficiency. Memory access patterns matter enormously for performance!

Hardware-Level Bit Reversal

Modern processors often provide specialized instructions for bit manipulation that can reverse bits in a single CPU cycle. Understanding these helps you write the most efficient code for your target platform.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// ARM: RBIT instruction reverses bits directly
#ifdef __ARM_NEON
uint32_t reverseBitsARM(uint32_t x) {
    return __rbit(x);  // Single instruction!
}
#endif
 
// x86 doesn't have direct bit reversal, but has BSWAP for byte reversal
// Combined with nibble reversal table for full bit reversal
 
// GCC/Clang might optimize this to BSWAP
uint32_t reverseBytes(uint32_t x) {
    return __builtin_bswap32(x);
}
 
// For byte reversal: BSWAP reverses byte order, not bit order
// 0x12345678 → 0x78563412
// This is useful for endianness conversion
 
// In Rust:
// x.reverse_bits()  // Available since Rust 1.37
 
// In modern JavaScript, no direct hardware access, but:
// WebAssembly SIMD has some related operations
 
// Key takeaway: check if your target platform has
// hardware support before implementing in software

Platform-specific bit reversal support:

Hardware Bit Reversal Support
Platform	Instruction	Latency	Notes
ARM (v6+)	RBIT	1 cycle	Full 32-bit reversal in hardware
ARM64	RBIT	1 cycle	64-bit reversal available
x86/x64	None direct	—	Use BSWAP + software for nibbles
RISC-V	Zbkb extension	1 cycle	brev8 for byte bit reversal
PowerPC	None	—	Software implementation required

Byte Reversal vs Bit Reversal

Don't confuse these operations!

• BSWAP (byte swap): Reverses the ORDER of bytes, not the bits within them Example: 0x12345678 → 0x78563412

• RBIT (bit reverse): Reverses ALL bits in the entire word Example: 0x12345678 → 0x1E6A2C48

BSWAP is common (endianness conversion) while RBIT is rarer (signal processing, FFT).

Real-World Applications

Bit reversal might seem academic, but it appears in several important real-world contexts. Understanding where it's used helps you recognize when to reach for these techniques.

Key Applications

•Fast Fourier Transform (FFT): The Cooley-Tukey FFT algorithm requires bit-reversal permutation to reorder input or output arrays. This is the most common application.
•Hardware Communication Protocols: Some serial protocols (like certain I2C or SPI variants) transmit LSB first, requiring bit reversal when working with MSB-first data.
•CRC Calculations: Certain CRC polynomials are defined with bit-reversed conventions, requiring reversal for correct computation.
•Cryptography: Some cipher modes and S-boxes use bit reversal as part of diffusion operations.
•Graphics and Image Processing: Certain sampling patterns and dithering algorithms use bit-reversed indices.
•Binary Counters: Bit-reversed counters produce Gray-code-like sequences with useful properties.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// In FFT, we need to reorder array elements by bit-reversed indices
// For an 8-element array (indices 0-7, 3 bits each):
//
// Index   Binary   Reversed   New Index
//   0      000       000          0
//   1      001       100          4
//   2      010       010          2
//   3      011       110          6
//   4      100       001          1
//   5      101       101          5
//   6      110       011          3
//   7      111       111          7
//
// Elements are swapped to positions determined by their bit-reversed index
 
function bitReversalPermutation<T>(arr: T[]): void {
    const n = arr.length;
    const bits = Math.log2(n);
    
    if (!Number.isInteger(bits)) {
        throw new Error("Array length must be a power of 2");
    }
    
    for (let i = 0; i < n; i++) {
        // Compute bit-reversed index
        let reversed = 0;
        let temp = i;
        for (let b = 0; b < bits; b++) {
            reversed = (reversed << 1) | (temp & 1);
            temp >>>= 1;
        }
        
        // Swap only if i < reversed (to avoid double-swapping)
        if (i < reversed) {
            [arr[i], arr[reversed]] = [arr[reversed], arr[i]];
        }
    }
}
 
const data = [0, 1, 2, 3, 4, 5, 6, 7];
console.log("Before:", data);
bitReversalPermutation(data);
console.log("After:", data);
// Output: [0, 4, 2, 6, 1, 5, 3, 7]

Why FFT Needs This

The FFT's divide-and-conquer structure splits the array into even and odd indices recursively. After all levels of recursion, the output is in bit-reversed order relative to the input. By pre-permuting with bit-reversal (or post-permuting the output), we can compute FFT iteratively without recursion overhead.

Variations: Partial Reversal and Related Operations

Beyond simple full-word bit reversal, several related operations appear in practice. Understanding these variations extends your bit manipulation toolkit.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// 1. Reverse only the least significant k bits
function reverseLowBits(x: number, k: number): number {
    // Extract low k bits, reverse them, put back
    const mask = (1 << k) - 1;  // k ones
    const lowBits = x & mask;
    const highBits = x & ~mask;
    
    let reversed = 0;
    let temp = lowBits;
    for (let i = 0; i < k; i++) {
        reversed = (reversed << 1) | (temp & 1);
        temp >>>= 1;
    }
    
    return highBits | reversed;
}
 
console.log(reverseLowBits(0b11010110, 4).toString(2));
// Original: 11010110, reverse low 4 bits (0110)
// Result:   11010110 → 1101 + 0110 reversed = 11010110
// Low 4: 0110 → 0110 (happens to be palindromic)
 
console.log(reverseLowBits(0b11010101, 4).toString(2));
// Low 4: 0101 → 1010
// Result: 11011010
 
 
// 2. Check if a number is a binary palindrome
function isBinaryPalindrome(x: number): boolean {
    if (x === 0) return true;
    if (x < 0) return false;
    
    // Find the number of significant bits
    let temp = x;
    let bits = 0;
    while (temp > 0) {
        bits++;
        temp >>>= 1;
    }
    
    // Reverse and compare
    let reversed = 0;
    temp = x;
    for (let i = 0; i < bits; i++) {
        reversed = (reversed << 1) | (temp & 1);
        temp >>>= 1;
    }
    
    return x === reversed;
}
 
console.log(isBinaryPalindrome(0b101));    // true: 101 reversed is 101
console.log(isBinaryPalindrome(0b1001));   // true: 1001 reversed is 1001  
console.log(isBinaryPalindrome(0b1010));   // false: 1010 reversed is 0101
console.log(isBinaryPalindrome(0b10001));  // true
 
 
// 3. Reverse nibbles (4-bit groups) within a byte
function reverseNibbles(x: number): number {
    // For each byte, swap high and low nibble
    return ((x & 0xF0F0F0F0) >>> 4) | ((x & 0x0F0F0F0F) << 4);
}
 
console.log(reverseNibbles(0x12345678).toString(16));
// 0x12345678 → 0x21436587 (each nibble pair swapped)

Related Bit Reordering Operations
Operation	Description	Example
Bit Reverse	Reverse all bits	0x12 → 0x48 (8-bit)
Byte Swap	Reverse byte order	0x1234 → 0x3412 (16-bit)
Nibble Swap	Swap nibbles in each byte	0x12 → 0x21
Bit Rotate	Circular shift	0b1100 ROL 1 → 0b1001
Bit Shuffle	Interleave/deinterleave bits	Used in cryptography

Summary: Bit Reversal Mastered

We've thoroughly explored bit reversal—from naive approaches to sophisticated optimizations. Let's consolidate the key insights:

Key Takeaways

•Word size matters: The same value reversed as 8-bit vs 32-bit gives completely different results
•Naive approach is O(n): Process each bit individually, shifting and accumulating
•Divide-and-conquer is O(log n): Swap progressively larger groups in 5 steps for 32 bits
•Lookup tables trade space for speed: Precompute reversed bytes for O(1) queries
•Hardware support varies: ARM has RBIT, x86 only has BSWAP (byte swap)
•Primary application is FFT: Bit-reversal permutation is essential for in-place FFT
•Related operations exist: Nibble swap, byte swap, and partial reversal extend the technique

Algorithm Selection Guide:

Scenario	Recommended Approach
One-off reversal	Divide-and-conquer (clean, no setup)
Repeated reversals	Lookup table (amortizes construction cost)
ARM platform	Use RBIT instruction via intrinsic
FFT implementation	Lookup table with specialized bit-width
Teaching/interviews	Start with naive, then show optimization

What's next:

With bit reversal mastered, we'll explore another fundamental bit manipulation problem: adding two numbers without using the addition operator. This problem reveals how arithmetic emerges from pure logic operations—a fascinating insight into how CPUs actually perform addition at the hardware level.

Page Complete

You now understand bit reversal deeply—from the mathematical definition to multiple implementation strategies. More importantly, you've learned to think about integers as ordered sequences of bits, a perspective that unlocks many other bit manipulation techniques.