Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Counting Set Bits

EASYProblemSolveExternal Links

Description

Given a positive integer n, return the number of set bits (bits that are 1) in its binary representation.

The count of set bits in a number is also known as the Hamming weight of that number. For example, the number 11 in binary is 1011, which has three 1 bits, so the answer is 3.

You need to write a function that takes a single positive integer and returns how many of its binary digits are 1.

Examples

Example 1

Input: n = 11

Output: 3

Explanation: The binary representation of 11 is 1011. Reading from left to right, the digits are 1, 0, 1, 1. Three of these four digits are 1, so the count of set bits is 3.

Example 2

Input: n = 128

Output: 1

Explanation: The binary representation of 128 is 10000000. Only the most significant bit is 1 and all other seven bits are 0. So the count of set bits is 1.

Example 3

Input: n = 13

Output: 3

Explanation: The binary representation of 13 is 1101. Out of the four binary digits, three of them are 1 (positions 0, 2, and 3 from the right). So the answer is 3.

Constraints

  • 1 ≤ n ≤ 2^31 - 1

Editorial

Brute Force

Intuition

The most straightforward way to count set bits is to examine each bit of the number one by one, from the rightmost bit (least significant bit) towards the left.

Think of it like reading a row of light switches. You start at one end, check if each switch is ON or OFF, and keep a running tally of how many are ON. When you reach the end of the row (no more switches to check), you report your total count.

In binary terms, we can check the rightmost bit of a number using the bitwise AND operation n & 1. If the rightmost bit is 1, this gives 1; if it is 0, this gives 0. After checking, we shift the number one position to the right using n >> 1 (or equivalently, n = n / 2), which effectively discards the bit we just checked and brings the next bit into the rightmost position. We repeat until the number becomes 0, meaning all bits have been examined.

Step-by-Step Explanation

Let's trace through with n = 11 (binary: 1011):

Step 1: Initialize count = 0. The number n = 11 in binary is 1011. We will check each bit from right to left.

Step 2: Check the rightmost bit: n & 1 = 11 & 1 = 1 (binary 1011 AND 0001 = 0001). The rightmost bit is 1, so increment count to 1.

Step 3: Right-shift n: n = 11 >> 1 = 5 (binary 0101). We have effectively removed the rightmost bit and moved the remaining bits over.

Step 4: Check the rightmost bit: n & 1 = 5 & 1 = 1 (binary 0101 AND 0001 = 0001). The rightmost bit is 1, so increment count to 2.

Step 5: Right-shift n: n = 5 >> 1 = 2 (binary 0010). Another bit has been discarded.

Step 6: Check the rightmost bit: n & 1 = 2 & 1 = 0 (binary 0010 AND 0001 = 0000). The rightmost bit is 0, so count stays at 2.

Step 7: Right-shift n: n = 2 >> 1 = 1 (binary 0001). One bit left to check.

Step 8: Check the rightmost bit: n & 1 = 1 & 1 = 1 (binary 0001 AND 0001 = 0001). The rightmost bit is 1, so increment count to 3.

Step 9: Right-shift n: n = 1 >> 1 = 0. The number is now 0, so we stop.

Result: count = 3. The number 11 has 3 set bits.

Counting Set Bits — Check Each Bit Right to Left — Watch how we inspect each binary digit from right to left, incrementing our count whenever we find a 1, then shifting the number right to expose the next bit.

Algorithm

  1. Initialize a counter count to 0
  2. While n is not 0:
    a. Check the rightmost bit using n & 1
    b. If the result is 1, increment count
    c. Right-shift n by 1 position: n = n >> 1
  3. Return count

Code

class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count += (n & 1);
            n >>= 1;
        }
        return count;
    }
};
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            count += n & 1
            n >>= 1
        return count
class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count += (n & 1);
            n >>>= 1;
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(log n)

The loop runs once for each bit in the binary representation of n. A number n has ⌊log₂(n)⌋ + 1 bits. Since n can be at most 2^31 - 1, the loop runs at most 31 times. This is O(log n) in terms of the value of n, or equivalently O(k) where k is the number of bits.

Space Complexity: O(1)

We only use a single integer variable count to keep track of the result. No additional data structures are needed, so space usage is constant regardless of input size.

Why This Approach Is Not Efficient

The brute force approach always iterates through every bit of the number, even the bits that are 0. For a 32-bit integer, it always performs up to 31 iterations regardless of how many set bits there actually are.

Consider the number 128 (binary 10000000). It has only 1 set bit, but the brute force still checks all 8 bits (or all 31 bits if working with 32-bit integers). The work done is proportional to the total number of bits, not the number of set bits.

Key insight: What if we could skip directly from one set bit to the next, ignoring all the 0 bits in between? If a number has only 2 set bits out of 31, we should only need 2 iterations, not 31. Brian Kernighan discovered a clever bit manipulation trick that does exactly this: the expression n & (n - 1) clears the rightmost set bit of n in a single operation.

Optimal Approach - Brian Kernighan's Algorithm

Intuition

Brian Kernighan's Algorithm relies on a beautiful property of binary arithmetic: when you subtract 1 from any number, all the bits after (and including) the rightmost set bit get flipped.

For example, take the number 12 (binary 1100). Subtracting 1 gives 11 (binary 1011). Notice what happened: the rightmost set bit at position 2 became 0, and all bits to its right flipped. Now, if we perform 12 & 11 = 1100 & 1011 = 1000, we get 8 — which is 12 with its rightmost set bit removed!

Think of it like popping balloons on a number line. Each time you do n = n & (n - 1), you pop exactly one balloon (clear one set bit). You keep popping until no balloons remain (n becomes 0). The number of pops you performed is the number of set bits.

The beauty is that this loop runs exactly as many times as there are set bits — not as many times as there are total bits. For a number like 128 (just one set bit), the loop runs only once instead of 31 times.

Step-by-Step Explanation

Let's trace through with n = 11 (binary: 1011):

Step 1: Initialize count = 0. n = 11, binary 1011. The number has 3 set bits — the algorithm will need exactly 3 iterations.

Step 2: First iteration. Compute n - 1 = 10 (binary 1010). Subtracting 1 flipped the rightmost set bit and all bits to its right: bit0 changed from 1 to 0.

Step 3: Apply n & (n - 1): 11 & 10 = 1011 & 1010 = 1010 = 10. The rightmost set bit has been cleared. Increment count to 1.

Step 4: Second iteration. n = 10, binary 1010. Compute n - 1 = 9 (binary 1001). Subtracting 1 flipped bit1 from 1 to 0, and bit0 from 0 to 1.

Step 5: Apply n & (n - 1): 10 & 9 = 1010 & 1001 = 1000 = 8. Another set bit cleared. Increment count to 2.

Step 6: Third iteration. n = 8, binary 1000. Compute n - 1 = 7 (binary 0111). Subtracting 1 flipped bit3 from 1 to 0, and all lower bits to 1.

Step 7: Apply n & (n - 1): 8 & 7 = 1000 & 0111 = 0000 = 0. The last set bit is cleared. Increment count to 3.

Step 8: n is now 0, so the loop terminates. Return count = 3.

Brian Kernighan's Algorithm — Clearing Set Bits One by One — Watch how n & (n-1) clears the rightmost set bit in each iteration. The loop runs exactly as many times as there are set bits, skipping all zero bits.

Algorithm

  1. Initialize a counter count to 0
  2. While n is not 0:
    a. Clear the rightmost set bit: n = n & (n - 1)
    b. Increment count by 1
  3. Return count

The key operation n & (n - 1) works because subtracting 1 flips the rightmost set bit and all bits below it. AND-ing with the original number keeps everything above the rightmost set bit unchanged but zeroes out the rightmost set bit and everything below.

Code

class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
};
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n = n & (n - 1)
            count += 1
        return count
class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(k), where k is the number of set bits in n

Unlike the brute force which iterates through all bits (up to 31 for a 32-bit integer), Brian Kernighan's algorithm only iterates once per set bit. In the worst case (all bits set, like n = 2^31 - 1), k = 31, which matches the brute force. But for sparse numbers like 128 (only 1 set bit), it runs in just 1 iteration instead of 31. On average, a random 32-bit number has about 16 set bits, making this roughly twice as fast as the brute force.

Space Complexity: O(1)

Only a single counter variable is used. No additional memory scales with the input.