# How to generate all $n$-bit numbers with certain bits fixed?

Consider the example where $n = 4$, bit 0 is fixed at 1, and bit 2 is fixed at 0. I would like to generate all $n$-bit numbers with those bits fixed. Essentially, everything I generate would have the form:

$$1*0*$$

where $*$ represents a bit that can vary. The fixed bits can be in arbitrary positions, and there can be arbitrarily-many of them (anywhere from 1 bit fixed to $n-1$ bits fixed). Ideally, I would prefer these to be generated in lex order; what I'm looking to generate for the example case would be:

$$1000, 1001, 1100, 1101$$

I've only found solutions for doing something like this when specific bits are set to 1 - my question is more general, as it allows bits to be set to 0 or 1. What is a good algorithm (in terms of simplicity and efficiency) to do this for arbitrary $n$?

• Hardly a question of computer science, but as you can see, excluding the $k$ bits that are fixed, the others just form a binary enumeration of $n-k$ digits. Generate that sequence, insert the fixed bits in the proper positions, and you're done. – André Souza Lemos Jan 14 '17 at 4:07
• If you can do it when bits are fixed to 1, you can probably use the very same algorithm for the general case. – Yuval Filmus Jan 14 '17 at 11:51

Practically speaking, here is one thing you could try:

1. Make a list $A[1],\ldots,A[m]$ of powers of two corresponding to free bits.

2. Generate a list of all XORs of elements from $A[i]$ (in the correct order), XORed to a mask consisting of the fixed bits.

If you don't care about the order, then an efficient way to generate the list is using a Gray code. Otherwise, you could use a recursive procedure.

In python:

n = 4

• This is not so efficient, since it runs in $O(2^n)$ rather than in $O(2^m)$, where $m$ is the number of free bits. More overhead arises from the set data structure. – Yuval Filmus Jan 14 '17 at 11:48