Introduction

Generating numbers with exactly a fixed number of set bits is really a combinations problem written in binary. If you want all n-bit numbers with exactly k ones, the two most common solutions are either to choose the set-bit positions directly or to step through the bitmasks with a bit-manipulation trick such as Gosper's hack.

Think of Set Bits as Chosen Positions

If a number has exactly k bits set among n positions, then you are really choosing k positions out of n.

For example, with n = 5 and k = 3, the mask 10110 means positions 1, 2, and 4 were chosen.

That makes the problem naturally equivalent to combinations.

A Clear Combinatorial Generator

In Python, the most readable approach is to generate combinations of bit positions and then build the number.

1from itertools import combinations
2
3
4def numbers_with_k_bits(n, k):
5    for positions in combinations(range(n), k):
6        value = 0
7        for pos in positions:
8            value |= 1 << pos
9        yield value
10
11
12for number in numbers_with_k_bits(5, 3):
13    print(f"{number:05b}")

This is easy to reason about because the code mirrors the math directly.

Why This Is Already Optimal in Spirit

The total number of answers is C(n, k), so any correct algorithm must at least spend time proportional to the number of outputs it emits. That means the real performance question is usually about how efficiently you move from one valid mask to the next, not about escaping the combinatorial nature of the task.

Gosper's Hack for Efficient Next-Step Generation

If you want a lower-level bit trick that jumps directly to the next larger integer with the same number of set bits, Gosper's hack is a classic technique.

1def gosper_next(x):
2    smallest = x & -x
3    ripple = x + smallest
4    ones = x ^ ripple
5    ones = (ones >> 2) // smallest
6    return ripple | ones
7
8
9def generate_fixed_popcount(n, k):
10    if k == 0:
11        yield 0
12        return
13    if k > n:
14        return
15
16    limit = 1 << n
17    value = (1 << k) - 1
18
19    while value < limit:
20        yield value
21        value = gosper_next(value)
22
23
24for number in generate_fixed_popcount(5, 3):
25    print(f"{number:05b}")

This is compact and efficient when you want each next value without rebuilding masks from positional combinations.

Which Approach Should You Choose?

Use the combinations approach when:

• readability matters most
• you are teaching or explaining the idea
• you are writing a high-level utility

Use the bit-hack approach when:

• you want tight low-level iteration
• bit operations are natural in the surrounding code
• constant-factor efficiency matters more than readability

Both generate the same set of values.

Edge Cases Matter

Two edge cases should be handled deliberately:

• 'k == 0, where the only valid number is zero'
• 'k > n, where there are no valid n-bit numbers at all'

Failing to handle these cases cleanly often leads to confusing output or invalid loops.

A Java Version of the Combinatorial Idea

Here is a simple recursive Java approach that builds masks by deciding whether each bit is included.

1public class BitMasks {
2    static void generate(int n, int k, int index, int chosen, int value) {
3        if (chosen == k) {
4            System.out.println(Integer.toBinaryString(value));
5            return;
6        }
7        if (index == n) {
8            return;
9        }
10
11        generate(n, k, index + 1, chosen + 1, value | (1 << index));
12        generate(n, k, index + 1, chosen, value);
13    }
14
15    public static void main(String[] args) {
16        generate(5, 3, 0, 0, 0);
17    }
18}

This is not the most optimized implementation, but it makes the combinatorial structure clear.

Common Pitfalls

The biggest mistake is iterating through all numbers from 0 to 2^n - 1 and filtering by popcount when a direct generator would be much cleaner.

Another issue is forgetting that the output size is inherently combinatorial. If n is large and k is near the middle, there may simply be a huge number of valid outputs.

Developers also sometimes mix up bit positions with visual left-to-right string positions, which can lead to off-by-one confusion.

Finally, if you use Gosper's hack, test it carefully around edge conditions. It is elegant, but it is also easy to treat as magic and misuse.

Summary

• Numbers with exactly k set bits correspond to combinations of k positions out of n.
• A combinations-based generator is the clearest high-level solution.
• Gosper's hack is a compact low-level way to step through masks with fixed popcount.
• The number of outputs is combinatorial, so enumeration cost scales with output size.
• Handle k == 0 and k > n explicitly.