### 13-2
Incrementing a Gray-Coded Integer

The logic for incrementing a 4-bit binary integer abcd
can be expressed as follows, using Boolean algebra notation:

Thus, one way to build a Gray-coded counter
in hardware is to build a binary counter using the above logic, and convert the
outputs a', b',
c', d' to Gray
by forming the exclusive or of adjacent bits,
as shown under "Gray from Binary" in Figure 13-1.

A way that might be slightly better is
described by the following formulas:

That is, the general case is

Because the parity p
alternates between 0 and 1, a counter circuit might maintain p in a separate 1-bit register and simply invert it
on each count.

In software, the best way to find the
successor G' of a Gray-coded integer G is probably simply to convert G to binary, increment the binary word, and convert
it back to Gray code. Another way that's interesting and almost as good is to
determine which bit to flip in G. The pattern
goes like this, expressed as a word to be exclusive or'd
to G:

The alert reader will recognize this as a
mask that identifies the position of the leftmost bit that changes when
incrementing the integer 0, 1, 2, 3, ? corresponding to the positions in the
above list. Thus, to increment a Gray-coded integer G,
the bit position to invert is given by the leftmost bit that changes when 1 is
added to the binary integer corresponding to G.

This leads to the following algorithms for
incrementing a Gray-coded integer G. They both
first convert G to binary, which is shown as `index(G)`.

##### Figure 13-2 Incrementing a Gray-coded integer.

B = index(G);牋牋牋牋牋牋牋 B = index(G);

B = B + 1;牋牋牋牋牋牋牋牋?M = ~B & (B + 1);

Gp = B ^ (B >> 1);牋牋牋牋?Gp = G ^ M;

A pencil-and-paper method of incrementing a
Gray-coded integer is as follows:

Starting from the right, find the first place
at which the parity of bits at and to the left of the position is even. Invert
the bit at this position.

Or, equivalently:

Let p be the
parity of the word G. If p is even, invert the rightmost bit.

If p is odd,
invert the bit to the left of the rightmost 1-bit.

The latter rule is directly expressed in the
Boolean equations given above.