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

$\endgroup$
  • 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 '17 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 '17 at 11:51
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.

$\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)
$\endgroup$
  • 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 '17 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 '17 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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