1
$\begingroup$

For an algorithm I need to be able to iterate over all bit strings where $k$ bits are flipped given a bit string with length $n$ and $n \geq k$. For instance let's say I have the bit string $1001$ and I want to have all bit strings with $2$ bits flipped. That should result in the following bit strings:

1010
1100
1110
0000
0011
0101

So given a bit string of length $n$ and where $k$ bits will be flipped the result will be $\binom{n}{k}$ bit strings. Is there an efficient way to generate all of them? The bit strings I have as input are just unsigned integers so I can use bit twiddling!

$\endgroup$
2
$\begingroup$

Let your initial bit string be x.

For all numbers b with k bits set (i.e. where k bits are 1), output x xor b.

Finding all numbers with k bits set is described elsewhere, for example here

$\endgroup$

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.