Number of 1 Bits

Number of 1 Bits is a small question with a famous twist. Anyone can count the ones by checking each bit. But there is a clever trick that skips all the zero bits. The interviewer wants to see if you know it. So let us learn both ways.

🎯 The Problem

You get a number. You count how many bits in its binary form are 1. The count of 1 bits even has a name. It is called the Hamming weight.

The rules:

• A bit is a single 0 or 1 inside the binary form of a number.
• Count only the bits that are 1.
• Return that count.

Let us take the number 11. In binary, 11 is 1011. Count the ones. There are three of them. So the answer is 3.

Input:  n = 11   (binary 1011)
Output: 3

Explanation: The binary 1011 has three bits set to 1.

So the job is simple. Look at the binary form. Count the ones.

Here is the binary of 11 laid out bit by bit. The shaded bits are the ones we count.

🐢 Approach 1: Check Every Bit (Brute Force)

The idea in one line: look at each bit one by one and count the ones.

The idea:

• A number has a fixed number of bits, usually 32 for an integer.
• Loop once per bit, so 32 times.

How it works:

• n & 1 is a bit AND that reads the lowest bit.
• AND gives 1 only when both bits are 1, so n & 1 is 1 when the lowest bit is on.
• If it is on, add one to the count.
• Shift the number right by one, so the next bit becomes the new lowest bit.

Why it is weak:

• It always loops the full bit width, even for a tiny number.
• A number with one 1 bit still costs 32 steps.
• The work is fixed no matter how few ones there are.

Here is the check-every-bit code:

def hamming_weight(n):
    count = 0
    for bit in range(32):
        if n & (1 << bit):
            count += 1
    return count

⚡ Approach 2: Brian Kernighan’s Trick (Best)

The idea in one line: jump straight from one 1 bit to the next, skipping every zero.

The idea:

• We use a trick named after Brian Kernighan, a computer scientist.
• The whole trick is one line: n = n & (n - 1).

How it works:

• Subtracting one flips the lowest 1 bit to 0 and turns the zeros below it into ones.
• The AND with the original n clears that lowest 1 bit.
• So one move removes exactly one 1 bit.
• Repeat and count until n becomes 0.

Why it is fast:

• It loops only as many times as there are ones.
• Three ones means three loops.
• It never wastes time on the zero bits.

Here is a picture of the trick removing ones from 11, which is 1011, until nothing is left.

Steps to Solve

1. Set a counter to 0.
2. While the number is not 0, do the next steps.
3. Run n = n & (n - 1), which removes the lowest 1 bit.
4. Add one to the counter for each removal.
5. Stop when the number reaches 0.
6. Return the counter.

#include <stdio.h>

int hammingWeight(unsigned int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);   // clear the lowest 1 bit
        count++;           // we removed one set bit
    }
    return count;
}

int main(void) {
    unsigned int n = 11;   // binary 1011
    printf("%d\n", hammingWeight(n));
    return 0;
}

3

#include <iostream>
using namespace std;

int hammingWeight(unsigned int n) {
    int count = 0;
    while (n != 0) {
        n = n & (n - 1);   // clear the lowest 1 bit
        count++;
    }
    return count;
}

int main() {
    unsigned int n = 11;   // binary 1011
    cout << hammingWeight(n) << endl;
    return 0;
}

3

public class HammingWeight {
    public static int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1);   // clear the lowest 1 bit
            count++;
        }
        return count;
    }

    public static void main(String[] args) {
        int n = 11;            // binary 1011
        System.out.println(hammingWeight(n));
    }
}

3

def hamming_weight(n):
    count = 0
    while n != 0:
        n = n & (n - 1)   # clear the lowest 1 bit
        count += 1        # we removed one set bit
    return count


n = 11  # binary 1011
print(hamming_weight(n))

3

function hammingWeight(n) {
  let count = 0;
  while (n !== 0) {
    n = n & (n - 1); // clear the lowest 1 bit
    count++;
    n = n >>> 0; // keep it as an unsigned 32-bit value
  }
  return count;
}

const n = 11; // binary 1011
console.log(hammingWeight(n));

3

Let us read the Python version slowly and see why each line is there.

def hamming_weight(n):
    count = 0
    while n != 0:
        n = n & (n - 1)
        count += 1
    return count

The line count = 0 starts our tally at nothing. We have not removed any 1 bits yet.

The line while n != 0: keeps the loop running until the number is fully empty of ones. When n becomes 0, there is nothing left to count, so we stop.

The line n = n & (n - 1) is the trick itself. Subtracting one flips the lowest 1 bit off and fills the lower zeros with ones. The AND with the old n then wipes that lowest 1 bit clean. So one set bit disappears each pass. We never touch the zero bits, which is why this is fast.

The line count += 1 records that we just removed one set bit. Since each loop removes exactly one, the count grows by exactly the number of ones.

The line return count gives back the final tally. It equals the number of 1 bits in the original number.

⏱️ Time and Space Complexity

The check-every-bit way always does a fixed number of steps, one for each bit, so it is O(k) where k is the bit width, usually 32. The Brian Kernighan way loops only once per 1 bit. So if a number has few ones, it does little work. Both use just a counter, so the memory is O(1). The Brian Kernighan trick is the one to show off in the interview.

🧩 Key Takeaways

• ✅ A 1 bit is a bit set to 1 inside the binary form of a number.
• ✅ The simple way checks each bit with n & 1 and shifts right.
• ✅ Brian Kernighan’s trick n & (n - 1) clears the lowest 1 bit in one step.
• ✅ That trick loops only once per set bit, so it skips all the zeros.
• ✅ Both ways use O(1) memory, but the trick is faster for sparse numbers.

🚀 What’s Next?

• Counting Bits
• Single Number