Count Set Bits algorithm explained step-by-step: bitwise operations, Brian Kernighan’s n & (n - 1) clearing technique, population count, time complexity, and JavaScript implementation.
Counting set bits (often termed Population Count or Hamming Weight) calculates the total number of 1-bits in the binary representation of an integer.
A naive loop tests all 32 bits by shifting one by one, always taking 32 iterations regardless of how few 1s exist. Brian Kernighan’s algorithm uses the algebraic identity `n & (n - 1)` to clear the lowest (rightmost) set bit in a single CPU instruction. Thus, the loop executes only K times, where K is the exact count of set bits (O(k) time and O(1) space).
Subtracting 1 from `n` flips the lowest set bit (1 -> 0) and inverts all trailing zeros to 1s. Performing `n & (n - 1)` preserves all higher bits while zeroes out that lowest 1-bit.
Set `count = 0`.
While `n > 0`, execute `n = n & (n - 1)` to clear one set bit, and increment `count++`.
When `n` reaches 0, all set bits have been processed; `count` holds the exact population count in O(k) iterations.
1// 1. Brian Kernighan's Algorithm - O(k) time where k = number of 1 bits2function countSetBits(n) {3 let count = 0;4 // Convert to unsigned 32-bit integer5 let num = n >>> 0;6 7 while (num > 0) {8 num = num & (num - 1); // Clears the lowest set bit9 count++;10 }11 12 return count;13}14 15// 2. Built-in alternative using binary string conversion16function countSetBitsString(n) {17 return (n >>> 0).toString(2).split('0').join('').length;18}19 20// Example usage:21// countSetBits(29); // 4 (29 in binary is 11101 -> four 1s)22// countSetBits(0); // 0Play through every comparison, swap, and state change, adjust the speed, or enter custom inputs to test edge cases.
The full interactive roadmap is unlocking — these specialized modules land in upcoming releases.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
Explore the full catalog — 30+ algorithms with more unlocking every release.
Bitwise operator & binary bit manipulation inspector
Test your understanding of Count Set Bits (Brian Kernighan Algorithm) complexity and step mechanics.
Q1.What does the expression n & (n - 1) accomplish in bit manipulation?
Q2.How can you check in O(1) time if a positive integer n is a power of 2?
Apply Count Set Bits (Brian Kernighan Algorithm) to real coding interview questions.
Write a function that returns the number of set bits in an unsigned integer.
Given an integer n, return an array ans of length n + 1 such that ans[i] is the number of 1s in the binary representation of i.