218. Count Set Bits in an Integer

Given a non-negative integer n, count the number of 1 bits in its binary representation.

Input: A single line contains the non-negative integer n. Output: Print a single integer - the number of set bits (1s) in n's binary representation.

0 <= n <= 10^9

This exact set-bit-counting logic (popcount) is the foundational building block several harder problems in this category depend on directly - it's worth having memorized, not just understood conceptually.

Look at a number's binary form and count how many of its digits are 1 (as opposed to 0). Brute force: Convert the number to a binary string and count how many '1' characters appear - works, but string conversion is unnecessary overhead compared to working with the bits directly. Optimised: The trick n & (n-1) clears exactly the LOWEST set bit of n in one operation (since subtracting 1 flips all the trailing zeros to ones and the lowest set bit to zero, and ANDing with the original cancels those out) - repeatedly applying this and counting how many times you can do it before n becomes 0 gives you the set-bit count directly, without ever checking bits that are already 0.

Loop over every bit position from 0 up to the highest bit n could have (around 30 for values up to 10^9), and for each position test whether that bit is set using a mask and increment a counter if so. This checks the definition of 'number of 1 bits' directly and always works, but it does the same fixed amount of work regardless of how many bits are actually set, including scanning through long runs of zero bits. Time: O(log n) Space: O(1)

Repeatedly replace n with n & (n-1), an operation that clears exactly the lowest set bit each time it's applied, and count how many times this can be done before n becomes zero. This is a genuine improvement because the loop runs exactly once per set bit rather than once per bit position, so sparsely-set numbers finish much faster than the brute-force bit-by-bit scan, even though the worst case (all bits set) is comparable. Time: O(number of set bits) Space: O(1)

Precompute, once, a small table of the popcount of every 8-bit value from 0 to 255. To count the bits of n, split it into its four constituent bytes and sum the four corresponding table lookups (or, if the language exposes it, use a hardware population-count instruction directly). This turns bit counting into a fixed, small number of array lookups regardless of how many bits are set or where they are, giving genuinely constant time rather than time proportional to the number of bits or set bits. Time: O(1) Space: O(1) (fixed 256-entry table)

1. Look at the number's lowest bit (using n & 1) to check if it's a 1. 2. Shift the number right by one position, discarding the bit you just checked. 3. Repeat until the number becomes 0, keeping a running count of how many 1s you saw. 4. That running count is the total number of set bits.

Time: Proportional to the number of SET bits specifically (not the total bit-width) when using the n & (n-1) trick - genuinely fast, especially for numbers with few 1s. Space: O(1) - just a counter variable.

Test n = 0 (0 set bits), n = 10^9 (upper bound), and a power of two (exactly one set bit).

Know the n & (n-1) 'clear lowest set bit' trick cold - it's one of the most reused bit-manipulation building blocks, appearing in several OTHER problems in this same category (like checking if a number is a power of 2).