1
$\begingroup$

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$?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – André Souza Lemos
    Jan 14, 2017 at 4:07
  • $\begingroup$ If you can do it when bits are fixed to 1, you can probably use the very same algorithm for the general case. $\endgroup$
    – Yuval Filmus
    Jan 14, 2017 at 11:51

2 Answers 2

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

In python:

n = 4
or_mask =  0b1000
and_mask = 0b1101
answer_set = set()
for i in range(2**n):
    answer_set.add((i | or_mask) & and_mask)
return sorted(answer_set)
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Jan 14, 2017 at 11:48
  • $\begingroup$ Python sets are amortized O(1). And while you're right that there's an extra O(2^k) spent, what the solution loses in efficiency, it gains in simplicity, which was also an explicit goal of the OP. It being a complete, working solution doesn't hurt either. I suspect this question should actually be moved to stack overflow, but I don't have the rep to do so. $\endgroup$
    – Eli Stevens
    Jan 15, 2017 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.