codaBack to Academy
bitwise operations
Count Set Bits (Brian Kernighan's)
Brian Kernighan's algorithm counts the number of set bits (1s) in an integer by repeatedly clearing the lowest set bit using n & (n-1). Each iteration removes exactly one set bit, making it O(k) where k is the number of set bits rather than O(log n) for checking every bit position.
Use Cases
- •Calculating Hamming weight for error detection codes
- •Population count in bitmap indices and databases
- •Evaluating game board states in chess engines
- •Measuring similarity between binary feature vectors
Complexity Analysis
| Metric | Best | Average | Worst |
|---|---|---|---|
| Time | O(1) | O(k) | O(log n) |
| Space | O(1) | ||
Visualization
Implementation
Output
Click "Run Code" to see output...