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.
Visualization
Interactive visualization for Check if Power of Two
Interactive visualization with step-by-step execution
Implementation
1function isPowerOfTwo(n: number): boolean {
2 return n > 0 && (n & (n - 1)) === 0;
3}Deep Dive
Theoretical Foundation
A power of 2 has exactly one bit set in binary. When we subtract 1, this bit becomes 0 and all bits to the right become 1. Example: 8 (1000) - 1 = 7 (0111). AND-ing these gives 0. For non-powers: 6 (0110) - 1 = 5 (0101), 6 & 5 = 4 (≠0). The formula n & (n-1) clears the rightmost set bit. For powers of 2, this leaves 0. For others, bits remain. Edge case: 0 is not a power of 2, hence n > 0 check. This technique generalizes: n & (n-1) == 0 also detects 0, so we need both conditions.
Complexity
Time
O(1)
O(1)
O(1)
Space
O(1)
Applications
Industry Use
Memory alignment checks in systems programming
Hash table size validation (must be power of 2)
Buffer size validation in networking
Graphics programming (texture dimensions)
Page size validation in virtual memory
Quick modulo operations (x % 2^n = x & (2^n - 1))
Fast multiplication/division by powers of 2
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.
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.
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.
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.