# Generate all binary numbers, a single bit flip a time

Is it possible to sequentially generate all $n$-bit configurations (say, the binary representation of a an $n$-digit number), a single bit flip a time, in such a way that no configuration is generated twice?

If yes, is there an algorithm for this that doesn't need to remember which configurations have already been generated?

Example for 3-bit configurations

OOO  OOX  OXX  OXO  XXO  XOO  XOX  XXX


Subsequent configurations differ only in a single bit.

-
There is a very good chapter in Knuth: 'The art of computer programming' about this. It's 4.something if I remember well. –  Ragnar Dec 20 '13 at 19:43

You're looking for Gray codes.

-
Exactly what I would have said but you beat me to it. –  Carl Witthoft Dec 20 '13 at 22:39
@Ross: You can either do the second run in reverse order, or do it in the original order but XOR everything with an appropriate constant to make the first element of the second run match the last element of the first run. If start from the base case 0, 1, then these two ways of doubling the length actually end up with the same sequence in the end! –  Henning Makholm Dec 21 '13 at 14:27