Loop over bit permutation one flip at a time

Question

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

Answer 1

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.

Answer 2

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.