SimuVedaAlgorithms Lab Open in the lab

Bit manipulation / Beginner

Count Set Bits (Kernighan) Visualizer

Subtracting 1 flips the lowest 1 bit to 0 and every 0 below it to 1. So n & (n − 1) erases exactly the lowest 1 bit. Count how many times you can do that before n is 0.

Start the Count Set Bits (Kernighan) simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(1)
Average timeO(k)
Worst timeO(k)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. n = 108, which is 1101100 in binary. Column headers show what each bit is worth.
  2. n − 1 = 107. The lowest 1 bit of n (worth 4) flips to 0 and the bits below it flip to 1.
  3. AND keeps only bits that are 1 in both rows: 104. Exactly one 1 bit is gone.
  4. count = 1. n is now 104.
  5. n − 1 = 103. The lowest 1 bit of n (worth 8) flips to 0 and the bits below it flip to 1.
  6. AND keeps only bits that are 1 in both rows: 96. Exactly one 1 bit is gone.
  7. count = 2. n is now 96.
  8. n − 1 = 95. The lowest 1 bit of n (worth 32) flips to 0 and the bits below it flip to 1.
  9. AND keeps only bits that are 1 in both rows: 64. Exactly one 1 bit is gone.
  10. count = 3. n is now 64.
  11. n − 1 = 63. The lowest 1 bit of n (worth 64) flips to 0 and the bits below it flip to 1.
  12. AND keeps only bits that are 1 in both rows: 0. Exactly one 1 bit is gone.
  13. count = 4. n is now 0.
  14. n is 0, so stop. 108 has 4 set bits.

Try it with your own input →

Count set bits (Kernighan) in Java, Python, C++, C and JavaScript

int hammingWeight(int n) {
  int count = 0;
  while (n != 0) {
    n &= (n - 1);
    count++;
  }
  return count;
}
def hamming_weight(n):
    count = 0
    while n != 0:
        n &= n - 1
        count += 1
    return count
int hammingWeight(unsigned int n) {
  int count = 0;
  while (n != 0) {
    n &= (n - 1);
    count++;
  }
  return count;
}
int hammingWeight(unsigned int n) {
  int count = 0;
  while (n != 0) {
    n &= (n - 1);
    count++;
  }
  return count;
}
function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n &= (n - 1);
    count++;
  }
  return count;
}

In an interview

LeetCode 191, Number of 1 Bits. The same trick powers 338 Counting Bits and 231 Power of Two (n & (n − 1) == 0).

This loops once per set bit (k), not once per bit position. Java also has Integer.bitCount(n), which interviewers may let you use after you explain the trick.

More bit manipulation