Reverse Bits
Reverse the bit pattern of a 32-bit unsigned integer efficiently using bit manipulation. For example, 43261596 (binary: 00000010100101000001111010011100) becomes 964176192 (binary: 00111001011110000010100101000000) after reversal. This operation is critical in Fast Fourier Transform (FFT) bit-reversal permutation, graphics processing, cryptographic operations, and understanding little-endian/big-endian conversions at the bit level.
Visualization
Interactive visualization for Reverse Bits
Interactive visualization with step-by-step execution
Implementation
1function reverseBits(n: number): number {
2 let result = 0;
3 for (let i = 0; i < 32; i++) {
4 result = (result << 1) | (n & 1);
5 n >>= 1;
6 }
7 return result >>> 0; // Convert to unsigned
8}Deep Dive
Theoretical Foundation
Bit reversal mirrors the bit pattern of an integer. Iterative approach: process each of 32 bits, extracting rightmost bit from input and building result from right-to-left by left-shifting result and ORing with extracted bit. Time: O(32) = O(1) for fixed width. Divide-and-conquer optimization: recursively swap halves (16 bits), then quarters (8 bits), then 4-bit chunks, 2-bit pairs, finally adjacent bits - this gives O(log log n) = O(log 32) = O(5) operations. Lookup table method: precompute reversal for bytes, process 4 bytes separately. Choice depends on use case: iterative is simple, divide-conquer is faster for many calls, lookup uses more memory.
Complexity
Time
O(log n)
O(log n)
O(log n)
Space
O(1)
Applications
Industry Use
Fast Fourier Transform (FFT) bit-reversal permutation
Graphics rendering (texture mapping)
Cryptographic operations
Network protocol implementation
Digital signal processing
Binary tree level-order to in-order conversion
Endianness conversion
Reed-Solomon error correction
Use Cases
Related Algorithms
Count Set Bits (Brian Kernighan's Algorithm)
Efficiently count the number of 1 bits (set bits) in the binary representation of an integer. Brian Kernighan's algorithm is one of the most elegant bit manipulation techniques, invented by Brian Kernighan (co-author of 'The C Programming Language'). The algorithm repeatedly clears the rightmost set bit, making it optimal as it only loops for the number of set bits rather than all bits.
Check if Power of Two
Determine if a given integer is a power of 2 using a brilliant single bitwise operation. Powers of 2 in binary have exactly one set bit: 1=0001, 2=0010, 4=0100, 8=1000, 16=10000. This unique property enables an O(1) constant-time check using the elegant formula: n > 0 && (n & (n-1)) == 0. This trick is widely used in systems programming, memory management, and optimization.
XOR Operations Collection
Comprehensive collection of XOR (exclusive OR) bit manipulation techniques with unique mathematical properties: a ⊕ a = 0 (self-inverse), a ⊕ 0 = a (identity), commutative, and associative. XOR is fundamental in finding unique/missing elements, in-place swapping, parity checking, cryptography, error detection, and many optimization problems. These elegant properties make XOR one of the most powerful bitwise operators.
Add Two Numbers (Bitwise)
Perform integer addition using only bitwise operations (XOR, AND, shift) without the + operator, mimicking how CPUs add numbers at the hardware level using logic gates. This algorithm decomposes addition into sum-without-carry (XOR) and carry-generation (AND + shift), iterating until no carry remains. Fundamental for understanding computer architecture, ALU design, and implementing arithmetic when + operator is unavailable or expensive.