Bit Count (popcount), Leading & Trailing Zeros

Understanding the bit count calculator — concept and principle

Population count (popcount) is the number of 1 bits in a binary number; leading and trailing zeros count the 0 bits before the highest and after the lowest set bit. These quantities appear in bitboard chess engines, Hamming distance, error-correcting codes, memory allocators, hash tables sized to powers of two and in choosing how many bits a field needs. Enter an unsigned 32-bit number (0 to 4,294,967,295) to get all of them.

How it is calculated

• Popcount: the number of 1 bits, found by testing the lowest bit and shifting right until the value is 0.
• Leading zeros: zeros before the highest 1 bit in a 32-bit word (Math.clz32); 32 for x = 0.
• Trailing zeros: x AND −x keeps only the lowest 1 bit; its position is 31 − clz32 of that value. Defined as 32 for x = 0.
• Bits needed: 32 − leading zeros, i.e. floor(log₂ x) + 1; 1 for x = 0.
• Parity: even or odd number of 1 bits.
• Power of two: x > 0 and x AND (x − 1) = 0.

The principle

In two's complement, −x equals NOT x + 1. Adding 1 to NOT x turns its trailing 1s back to 0s and stops at the first 0, which is exactly where x has its lowest 1, so x AND −x isolates that bit. Subtracting 1 does the mirror image: it clears the lowest 1 and sets the zeros below it, so x AND (x − 1) removes the lowest set bit; it is zero only when x had a single 1 bit, which is the definition of a power of two. Leading zeros measure the position of the highest bit, which is why they give the bit length.

Worked example

1. Input: 40 = 32 + 8 = 101000 in binary.
2. Popcount: two 1 bits, so 2; parity is even.
3. The number uses 6 bits, so 6 bits are needed and leading zeros are 32 − 6 = 26.
4. 40 AND −40 = 8 = 2³, so trailing zeros are 3.
5. 40 AND 39 = 101000 AND 100111 = 100000 = 32, not zero, so 40 is not a power of two.

How to read the result

Bits needed tells you the smallest field that can hold the value: 40 fits in 6 bits, since 6 bits cover 0–63. Trailing zeros tell you the largest power of two dividing the number (2³ = 8 divides 40). The popcount of A XOR B is the Hamming distance between two bit patterns.

Common mistakes

• Counting leading zeros relative to 8 or 64 bits when the tool uses a 32-bit word.
• Treating 0 as a power of two; it is not, and the test checks x > 0 first.
• Forgetting that parity here is the parity of the bit count, not whether the number itself is even (40 is even and its bit-parity is also even, but 3 is odd with even bit-parity).

Frequently asked questions

Is there a CPU instruction for popcount?

Many processors have one (for example POPCNT on x86-64), and compilers expose it as built-ins such as __builtin_popcount.

How do I round up to the next power of two?

For x > 1 it is 2 to the power of (32 − clz32(x − 1)).

What does trailing zeros tell me about divisibility?

A number with k trailing zeros is divisible by 2ᵏ but not by 2ᵏ⁺¹.

Sources: Henry S. Warren Jr., Hacker's Delight, 2nd ed., Addison-Wesley, 2012, Chapter 5 (Counting bits) · Ecma International, ECMA-262 ECMAScript Language Specification (Math.clz32)