Medium · Bits

Count the 1-Bits

How many 1-bits are in a number's binary form? This is called popcount — and it is a real CPU instruction.

At a glanceCount set bits by shifting n right one bit at a time and adding n & 1 — or clear one bit per step with n &= n - 1, which loops only as many times as there are ones.

Problem

Input: One non-negative integer (0 <= n <= 1000000).

Output: The number of 1-bits in n.

Sample:

Input	Output
`7`	`3`

Your solution

main.cpp — your solution

Custom input for "Run my input"

Judging runs in your browser against hidden tests. A runaway loop is cut off after 3 seconds — still, make sure every loop has an exit. Your code is saved in this browser as you type.

Stuck? Hints

Hint 1 — Sum the remainders

While n > 0: ones += n % 2; n /= 2;. The remainders you printed in Binary Representation are these bits.

Hint 2 — Kernighan's trick

while (n) { n &= n - 1; ones++; } clears the lowest 1-bit each pass — iterations equal the number of ones.

Solution (try it first!)

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int ones = 0;
    while (n > 0) {
        ones += n % 2;
        n /= 2;
    }
    cout << ones << endl;
    return 0;
}

Modern C++ has std::popcount(n) (C++20) compiling to one CPU instruction. You just wrote it by hand.

Deep dive

Why this works

Three ways to count set bits — shift-and-test, Kernighan's n&(n-1), hardware popcount — are a compact tour of 'same answer, three cost profiles'.

The cost

Naive: always 32 iterations. Kernighan: one per set bit. Hardware: O(1) via a single instruction.

Where it goes wrong

Right-shifting a signed negative value is implementation-defined and can loop forever, because the sign bit keeps being refilled.
n >>= 1 on a negative number never reaches zero. Use unsigned.

Next step

Put the bits to work: Binary Representation.

Two things to remember

Kernighan: loop once per set bit, not once per bit.
Shift unsigned values only — signed shift is implementation-defined.

🐞 This version fails — open it and try

Only looks at the low 8 bits

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int c = 0;
    for (int i = 0; i < 8; i++) {
        if (n % 2 == 1) c++;
        n /= 2;
    }
    cout << c << endl;
    return 0;
}