C++: Gray Code

Gray code is a form of binary encoding where transitions between consecutive numbers differ by only one bit. This is a useful encoding for reducing hardware data hazards with values that change rapidly and/or connect to slower hardware as inputs. It is also useful for generating inputs for Karnaugh maps in order from left to right or top to bottom.

Create functions to encode a number to and decode a number from Gray code. Display the normal binary representations, Gray code representations, and decoded Gray code values for all 5-bit binary numbers (0-31 inclusive, leading 0’s not necessary).

There are many possible Gray codes. The following encodes what is called “binary reflected Gray code.”

Encoding (MSB is bit 0, b is binary, g is Gray code):

if b[i-1] = 1
   g[i] = not b[i]
else
   g[i] = b[i]

Or:

g = b xor (b logically right shifted 1 time)

Decoding (MSB is bit 0, b is binary, g is Gray code):

b[0] = g[0]

for other bits:
b[i] = g[i] xor b[i-1]

#include <bitset>
#include <iostream>
#include <string>

uint32_t gray_encode(uint32_t b)
{
	return b ^ (b >> 1);
}

uint32_t gray_decode(uint32_t g)
{
	for (uint32_t bit = 1U << 31; bit > 1; bit >>= 1)
	{
		if (g & bit) g ^= bit >> 1;
	}
	return g;
}

std::string to_binary(int value) // utility function
{
	const std::bitset<32> bs(value);
	const std::string str(bs.to_string());
	const size_t pos(str.find('1'));
	return pos == std::string::npos ? "0" : str.substr(pos);
}

int main()
{
	std::cout << "Number\tBinary\tGray\tDecoded\n";
	for (uint32_t n = 0; n < 32; ++n)
	{
		uint32_t g = gray_encode(n);
		uint32_t b = gray_decode(g);

		std::cout << n << "\t" << to_binary(n) << "\t" << to_binary(g) << "\t" << b << "\n";
	}
}

Output:

Number	Binary	Gray	Decoded
0	0	0	0
1	1	1	1
2	10	11	2
3	11	10	3
4	100	110	4
5	101	111	5
6	110	101	6
7	111	100	7
8	1000	1100	8
9	1001	1101	9
10	1010	1111	10
11	1011	1110	11
12	1100	1010	12
13	1101	1011	13
14	1110	1001	14
15	1111	1000	15
16	10000	11000	16
17	10001	11001	17
18	10010	11011	18
19	10011	11010	19
20	10100	11110	20
21	10101	11111	21
22	10110	11101	22
23	10111	11100	23
24	11000	10100	24
25	11001	10101	25
26	11010	10111	26
27	11011	10110	27
28	11100	10010	28
29	11101	10011	29
30	11110	10001	30
31	11111	10000	31

SOURCE

Content is available under GNU Free Documentation License 1.2.