Introduction

If you need the number of set bits at position p or lower, the efficient approach is to ignore all bits above p, then run a population-count operation on the remaining value. In other words, this is really a mask-plus-popcount problem.

Mask Off the Higher Bits

Assume bit positions are zero-based from the least significant bit. Then the mask that keeps bits 0 through p is:

unsigned mask = (1u << (p + 1)) - 1u;

Apply it to the value:

unsigned lower_bits = x & mask;

Now lower_bits contains exactly the part of x you want to count.

Count the Set Bits

If your compiler provides a population-count intrinsic, use it:

1#include <stdio.h>
2
3int count_set_bits_at_or_below(unsigned x, unsigned p) {
4    unsigned mask = (1u << (p + 1)) - 1u;
5    return __builtin_popcount(x & mask);
6}
7
8int main(void) {
9    unsigned x = 0b11011010;
10    printf("%d\n", count_set_bits_at_or_below(x, 4));
11    return 0;
12}

For x = 11011010 and p = 4, the relevant portion is 11010, which has three set bits.

Handle Full-Width Edge Cases

The expression (1u << (p + 1)) can overflow if p is the highest bit position of the type. Guard that case explicitly:

1int count_set_bits_at_or_below(unsigned x, unsigned p) {
2    unsigned width = sizeof(unsigned) * 8;
3    unsigned mask = (p + 1 >= width) ? ~0u : ((1u << (p + 1)) - 1u);
4    return __builtin_popcount(x & mask);
5}

This makes the function safe for p values at or beyond the word width.

If You Do Not Have a Built-In Popcount

If no intrinsic is available, Brian Kernighan’s bit trick is a solid fallback:

1int popcount_unsigned(unsigned value) {
2    int count = 0;
3    while (value != 0) {
4        value &= (value - 1);
5        count++;
6    }
7    return count;
8}
9
10int count_set_bits_at_or_below(unsigned x, unsigned p) {
11    unsigned width = sizeof(unsigned) * 8;
12    unsigned mask = (p + 1 >= width) ? ~0u : ((1u << (p + 1)) - 1u);
13    return popcount_unsigned(x & mask);
14}

This loops once per set bit, which is often much faster than testing every individual bit manually.

Why This Is Better Than a Naive Loop

A naive solution might check each bit from 0 to p:

1int slow_count(unsigned x, unsigned p) {
2    int count = 0;
3    for (unsigned i = 0; i <= p; i++) {
4        if (x & (1u << i)) {
5            count++;
6        }
7    }
8    return count;
9}

That works, but it does more work than necessary when a hardware or compiler-assisted popcount is available. The mask-plus-popcount approach is shorter, clearer, and typically faster.

Clarify the Meaning of “Position or Lower”

The phrase can be ambiguous, so define it explicitly in your code or docs:

• “lower” usually means lower-order bits
• position p is usually inclusive
• indexing is usually zero-based

Without those assumptions, different developers may count different bit ranges and both think they are correct.

Common Pitfalls

• Forgetting whether the bit position is zero-based or one-based.
• Shifting by the full width of the type and invoking undefined behavior.
• Using signed integers when unsigned bit logic would be clearer and safer.
• Writing a per-bit loop when a popcount intrinsic is already available.
• Misreading “lower” as a more significant position instead of a less significant one.

Summary

• Keep bits 0 through p with a mask, then count the set bits in that masked value.
• Use a compiler or hardware popcount when available.
• Guard the full-width shift edge case explicitly.
• Fall back to Kernighan’s algorithm if no popcount intrinsic exists.
• Document bit numbering assumptions so everyone counts the same range.