Count set bits in an integer

Problem Statement

Given a non-negative integer n, count the number of 1s in its binary representation (also known as the Hamming Weight or population count).

Example:

Noob-Friendly Explanation

Every number in a computer is stored as a series of 0s and 1s (binary). For example, the number 13 is stored as 1101.

Set bits are just the 1s in that binary representation. So "count set bits" literally means "count how many 1s are there."

Think of it like a row of light switches — some are ON (1) and some are OFF (0). We just need to count how many are ON!

Approach 1: Brute Force (Check Each Bit)

Intuition

Check each bit of the number one by one. Use the AND operation (n & 1) to check if the last bit is 1, then right-shift the number to check the next bit.

Algorithm

1. Initialize count = 0
2. While n > 0:
   • If last bit is 1 (n & 1 == 1), increment count
   • Right shift n by 1 (n = n >> 1)
3. Return count

class Solution {
    public static int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            // Check if last bit is 1
            if ((n & 1) == 1) {
                count++;
            }
            // Shift right to check next bit
            n = n >> 1;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countSetBits(13)); // 3 (binary: 1101)
        System.out.println(countSetBits(7));  // 3 (binary: 111)
        System.out.println(countSetBits(0));  // 0
    }
}

Complexity Analysis

• Time Complexity: O(log N) — A number N has log₂(N) bits, and we check each one
• Space Complexity: O(1) — Only using a counter variable

Approach 2: Optimal (Brian Kernighan's Algorithm)

Intuition

Instead of checking every bit, we can directly jump from one set bit to the next. The trick: n & (n - 1) removes the lowest set bit of n. So we keep doing this until n becomes 0, counting each step.

Why does n & (n-1) work? When you subtract 1 from n, all bits after the lowest set bit flip. ANDing with n clears that lowest set bit.

Example: n = 12 (1100)

• 12 & 11 = 1100 & 1011 = 1000 (removed rightmost 1) → count = 1
• 8 & 7 = 1000 & 0111 = 0000 → count = 2
• n = 0, stop. Answer = 2 ✓

Algorithm

1. Initialize count = 0
2. While n > 0:
   • n = n & (n - 1) — this removes the lowest set bit
   • Increment count
3. Return count

class Solution {
    public static int countSetBits(int n) {
        int count = 0;
        while (n > 0) {
            n = n & (n - 1); // remove lowest set bit
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(countSetBits(13)); // 3 (binary: 1101)
        System.out.println(countSetBits(7));  // 3 (binary: 111)
        System.out.println(countSetBits(0));  // 0
        System.out.println(countSetBits(16)); // 1 (binary: 10000)
    }
}

Complexity Analysis

• Time Complexity: O(K) — Where K is the number of set bits. We loop only K times, not log(N) times
• Space Complexity: O(1) — Only using a counter variable

Key Takeaways

1. n & 1: Checks if the last bit is 1
2. n & (n-1): Removes the lowest set bit — a must-know bit manipulation trick
3. Brian Kernighan's Algorithm: Only iterates as many times as there are set bits
4. Java Built-in: Integer.bitCount(n) does this, but knowing the algorithm is important for interviews