The Math Forum



Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.


Math Forum » Discussions » sci.math.* » sci.math

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Counting in Gray code.
Replies: 18   Last Post: Jun 17, 2000 4:27 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
eppstein@euclid.ics.uci.edu

Posts: 128
Registered: 12/8/04
Re: Counting in Gray code.
Posted: Jun 15, 2000 2:29 AM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply



Quentin Grady <quentin@paradise.net.nz> writes:
> <hermann.kremer@online.de> wrote:
> >For a given Gray code g > 0; its inverse is
> > n = invgray(g) = g XOR [g/2] XOR [g/4] XOR ...


> If this is easy to program in C++ am I right in thinking converting
> Gray back to standard binary can also be done with shift registers?


If you really want to do it in C++, try

inline unsigned long unGray(unsigned long r) {
r ^= r>>1;
r ^= r>>2;
r ^= r>>4;
r ^= r>>8;
r ^= r>>16;
return r;
}

5 shifts and xors instead of 31.

(I took this from a program I wrote to display properties of cellular
automaton rules -- see e.g. http://www.ics.uci.edu/~eppstein/ca/map.html --
since gray-code-adjacent rules are much more likely to be similar to
each other than binary-code-adjacent ones).
--
David Eppstein UC Irvine Dept. of Information & Computer Science
eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/







Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© The Math Forum at NCTM 1994-2018. All Rights Reserved.