Count Set Bits in an Integer

📌 Definition:

📖 Detailed Explanation:

The elegant trick n & (n - 1) clears the lowest set bit; repeat until n is zero, counting iterations — this runs in O(number of set bits) rather than O(total bits). Built-ins (Integer.bitCount) exist and are worth mentioning.

💻 Solutions:

• Java
• JavaScript
• Python

public static int countSetBits(int n) {
    int count = 0;
    while (n != 0) { n &= (n - 1); count++; }
    return count;
}

function countSetBits(n) {
  let count = 0;
  while (n !== 0) { n &= (n - 1); count++; }
  return count;
}

def count_set_bits(n):
    return bin(n).count('1')
# or Brian Kernighan:
# count = 0
# while n: n &= n - 1; count += 1

🔑 Key Points:

• n & (n-1) clears the lowest set bit
• Loops once per set bit — O(k)
• Built-ins: Integer.bitCount
• For negatives, treat as unsigned / mask

🌍 Real-World Example: