The following table generalizes some operations decribed in that section.

Value of one or more bits | Inversion of smallest bit | Inversion of trailing bits | Bitmask of smallest bit | Bitmask of traling bits |
---|---|---|---|---|

0 | x | (x + 1) | x | (x - 1) | ~x & (x + 1) | ~x & (x - 1) |

1 | x & (x - 1) | x & (x + 1) | x & (~x + 1) | x & (~x - 1) |

Negation operation expressed as logical NOT and arithmetic ADD:

-x = ~x + 1 = ~(x - 1) (we assume twos complement representation of negative numbers)

Logical NOT of a sum can be rewritten as a difference between the inverted first term and the second term:

~(x + a) = ~x - a Proof: Inversion is defined as: ~x = 2^n - 1 - x, where n - word size. Then substitute inversion with that expression: ~(x + a) = ~x - a 2^n - 1 - (x + a) = 2^n - 1 - x - a -x - a = -x - a 1 = 1

Gosper algorithm produces the next higher number with the same number of bits. The algorithm requires a division which is not available in some instruction sets. Fortunately, the division can be replaced by right shifts since the divisor is always a power of two. Here is the modified C function:

unsigned snoob(unsigned x) { unsigned smallest; unsigned ripple; unsigned ones; // generate higher bits of result by adding the smallest 1-bit to x smallest = x & -x; ripple = x + smallest; // the remaining bits should be a consecutive string of 1-bits // starting from bit 0 ones = x ^ ripple; // bitmask of remaining bits plus two extra bits while((ones & 1) == 0) // shift the bitmask to bit 0 ones >>= 1; // ones >>= 2; // remove the extra 2 bits return ripple | ones; // merge higher and lower bits and return }

The reflective binary Gray Code can be generalized to any natural integer radix (except base 1). For example, in base 10, first 100 encoded numbers are:

0 19 20 39 40 59 60 79 80 99 1 18 21 38 41 58 61 78 81 98 2 17 22 37 42 57 62 77 82 97 3 16 23 36 43 56 63 76 83 96 4 15 24 35 44 55 64 75 84 95 5 14 25 34 45 54 65 74 85 94 6 13 26 33 46 53 66 73 86 93 7 12 27 32 47 52 67 72 87 92 8 11 28 31 48 51 68 71 88 91 9 10 29 30 49 50 69 70 89 90(read the table by columns)

Encoding a number to Gray Code can be done as follows:

G(i) = B(i), if B(i+1) is an even digit G(i) = n - 1 - B(i), if B(i+1) is odd i - digit index (1..m-1, 1 - least significant, m - most significant) n - the radix base (2, 3, 4, ...) B - original number in base n G - Gray Code number in base n

Decoding a Gray Code number:

First, initialize the result: B = G Then, scan all the digits starting from the most significant one (i = m-1, m-2, ... 1): B(i) = B(i), if B(i+1) is even B(i) = n - 1 - B(i), if B(i+1) is odd

The following MATLAB programs can be used to verify the algorithms:

generateGrayCode.m - generate Gray Code in any base using
reflection

convertToGrayCode.m - encoding

convertFromGrayCode.m - decoding

Last updated: 7-Mar-2004