1
$\begingroup$

A bitstring is defined by a sequence of ones and zeros, e.g. "0101110111". Equivalently, it is defined by an integer as its binary representation.

I want to calculate a certain function of a bitstring for all bitstrings of a certain length $l$. This is equivalent to calculating that function for all integers from 0 up to $2^l-1$

I want to optimize my code by making less computation. I have noticed that if the difference between previous and next bitstring is only in 1 arbitrary bit (e.g. for "110010" and "111010" only the 3rd bit differs), the result of the function for the previous bitstring can be reused to significantly decrease the computation cost of the function for the next bitstring.

Question: Is there an easy algorithm to loop over all bitstrings of length $l$ in such a way, that the difference between any two consecutive bitstrings is only in 1 bit.

Bad example of length 2: 00 -> 01 -> 10 -> 11: the second step has difference of 2 bits

Good example of length 2: 00 -> 01 -> 11 -> 10: all steps have difference of only 1 bit

$\endgroup$
5
$\begingroup$

The thing you're looking for is called a Gray code. There are many ways such a thing can be constructed (there are 9 sequences, after considering flipping bit meaning, changing bit ordering, and similar simple transformations for four-bit numbers, and over 200,000 for 5-bit numbers), but there is one that is "the" Gray code, and this is simple to implement if you have bitwise XOR and bit shifts available in your language of choice: gray = x ^ (x >> 1) will convert a positive number to the number in the Gray code at that index.

$\endgroup$
1
$\begingroup$

What you are asking is equivalent to finding a hamiltonian path on a hypercube, since you can equate the string $000100$, for example, with the point $(0,0,0,1,0,0)\in\mathbb R^6$, and the neighboring strings are exactly those that share a side of the $6$-dimensional hypercube.

The hamiltonian path on a hypercube exists, so your loop also exists. See Wikipedia about it.

$\endgroup$
  • $\begingroup$ Thanks a lot for the answer. However, the question is not whether such a path exists, but how to construct it $\endgroup$ – Aleksejs Fomins Nov 17 '17 at 11:39

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.