Introduction

Counting the number of 1 bits in a binary representation is called population count, popcount, or Hamming weight. It comes up in bitmasks, compression, cryptography, and performance-sensitive code. The best implementation depends on the language and whether you want clarity, portability, or raw speed.

The Core Idea

If a number in binary is 101101, it has four set bits because there are four positions containing 1.

That is the quantity you are counting. The simplest way to think about it is:

• convert or inspect bits
• count how many are set

The algorithmic question is how to do that efficiently.

Straightforward String-Based Approach

In high-level languages, the most obvious solution is to convert to binary text and count the 1 characters.

n = 45  # binary 101101
count = bin(n).count("1")
print(count)

This is fine for simple scripts or teaching, but it is not the lowest-level or most efficient method because it allocates a string.

Bitwise Loop Approach

The classic bitwise method checks the least significant bit and shifts right until the number becomes zero.

1def popcount_shift(n: int) -> int:
2    count = 0
3    while n:
4        count += n & 1
5        n >>= 1
6    return count
7
8
9print(popcount_shift(45))

This is easy to understand and works well across many languages.

Brian Kernighan's Algorithm

A better classic approach repeatedly clears the lowest set bit:

n = n & (n - 1)

Each iteration removes exactly one 1 bit, so the loop runs once per set bit rather than once per bit position.

1def popcount_kernighan(n: int) -> int:
2    count = 0
3    while n:
4        n &= n - 1
5        count += 1
6    return count
7
8
9print(popcount_kernighan(45))

For sparse bit patterns, this can be significantly faster than the shift-and-test version.

Built-In Language Support

Modern languages often provide built-in popcount support, which is usually the best production answer.

Python:

n = 45
print(n.bit_count())

C++20:

1#include <bit>
2#include <iostream>
3
4int main() {
5    unsigned int n = 45;
6    std::cout << std::popcount(n) << '\n';
7}

These built-ins are preferable because they are clear and may compile down to optimized CPU instructions when available.

Handling Negative Numbers

With negative numbers, you need to define the bit width first. In Python, integers are unbounded, so "the number of 1 bits" in a negative number is not a simple standalone concept unless you decide on a two's-complement width.

Example for 8-bit interpretation:

n = -5
masked = n & 0xFF
print(bin(masked), masked.bit_count())

This counts bits in the 8-bit representation, not in Python's abstract infinite-precision integer model.

Use Cases in Real Code

Popcount is useful for:

• counting enabled flags in a bitmask
• computing Hamming distance
• subset and combinatorics algorithms
• low-level networking and compression code

Example Hamming distance:

1def hamming_distance(a: int, b: int) -> int:
2    return (a ^ b).bit_count()
3
4
5print(hamming_distance(0b1011, 0b1001))

The XOR marks positions that differ, and popcount counts them.

Which Method to Choose

Use this rule set:

• use a built-in popcount when the language has one
• use Brian Kernighan's algorithm for a portable low-level implementation
• use string conversion only for quick scripts or debugging

That gives you a good balance of readability and correctness.

Common Pitfalls

The most common mistake is forgetting that negative numbers need a defined bit width before a popcount makes sense. Another is writing a custom loop when the language already provides a built-in method. Teams also sometimes confuse the number's decimal digits with its binary set-bit count. Finally, using string conversion in hot loops can create unnecessary overhead when a bitwise or built-in solution would be simpler and faster.

Summary

• Counting 1 bits is called population count or Hamming weight.
• String conversion works, but it is mostly a teaching or quick-script approach.
• Brian Kernighan's algorithm is a classic efficient bitwise solution.
• Built-in functions such as int.bit_count() and std::popcount are usually best.
• Define a fixed width first if you need to count bits in negative values.