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.
Visualization
Interactive visualization for Count Set Bits (Brian Kernighan's Algorithm)
Count Set Bits (Brian Kernighan)
• Time: O(k) where k = number of set bits
• n & (n-1) clears rightmost set bit
• Brian Kernighan's algorithm
Interactive visualization with step-by-step execution
Implementation
1function countSetBits(n: number): number {
2 let count = 0;
3 while (n > 0) {
4 n &= (n - 1); // Removes rightmost set bit
5 count++;
6 }
7 return count;
8}
9
10// Alternative: Lookup table method
11function countSetBitsLookup(n: number): number {
12 const table = [0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4];
13 let count = 0;
14 while (n > 0) {
15 count += table[n & 0xF];
16 n >>= 4;
17 }
18 return count;
19}Deep Dive
Theoretical Foundation
Brian Kernighan's algorithm exploits a brilliant property: n & (n-1) always clears the rightmost set bit. Why? When you subtract 1 from n, all bits after the rightmost set bit get flipped, and the rightmost set bit becomes 0. ANDing with the original number clears that bit. Example: n=12 (binary 1100), n-1=11 (1011), n&(n-1)=8 (1000). The algorithm loops exactly once per set bit, making it O(k) where k is the count of 1s. This is significantly better than naive O(log n) approaches that check every bit position. The algorithm is used in CPU instructions like POPCNT and is fundamental in many optimization problems.
Complexity
Time
O(1)
O(k)
O(k)
Space
O(1)
Applications
Industry Use
Population count in genomics (DNA sequences)
Hamming weight calculation in error detection
Network routing table optimization
Chess/game programming (board representations)
Image processing (pixel counting)
Database bitmap indices
CPU instruction implementation (POPCNT)
Use Cases
Related Algorithms
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.
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.