Fog Creek Software
Discussion Board




technical riddles

The question really asks if there is if the integers 0 .. 2^n -1 can be ordered in some way so that two consecutive integers differ in their binary representation by 1 bit.
A sequence with this property is called Gray code. Let's call Gn such a sequence of 2^n elements. It's clear that G1 = 0 1. Now if we know Gn-1 we can easily find Gn by appending a 0 to every element in Gn-1 and concatenating this sequence to the one we obtain by appending a 1 to every element in Gn-1 and reversing this sequence.
A nice way of computing the kth term of Gn without computing the whole sequence is k ^ (k >> 1). You can find more about this here: http://www.library.cornell.edu/nr/bookcpdf/c20-2.pdf

Negruseri Cosmin
Monday, November 08, 2004

*  Recent Topics

*  Fog Creek Home