Gray Code

There are many great articles and videos on gray code, why/when we need gray code, how to compute gray code etc..  Here's a comprehensive one: https://en.wikipedia.org/wiki/Gray_code 

Among all those articles and videos, this formula is used (^ is logical xor, >> is right shift):

 num ^ (num >> 1) 

however, I can't find any good explanation about why. I'll try to explain it here in an easy to understand way (not mathematical way).

First, we need to understand the easy way of generating sequence of gray code. 

You can read the wikipedia page of any other articles out there if you need a very detailed version.

Here's my simple version. Let's start with 1 bit, that's easy

Decimal	Binary	Gray
0	0	0
1	1	1

in order to expand to 2 bit, all we need to do is, flip (or mirror) all existing gray code, and prefix 0 to the top half, prefix 1 to the bottom half. so first flip/mirror:

Decimal	Binary	Gray
0	00	0
1	01	1
2	10	1
3	11	0

then prefix:

Decimal	Binary	Gray
0	00	00
1	01	01
2	10	11
3	11	10

from the process you'll found out:

1. for any half, successive values differ in only one bit, because the half is build from existing gray code, even after mirror, the same property applies
2. because first half has prefix 0, and second half has prefix 1, they doubled gray code range, without duplication
3. the last one from top half and first one from bottom half are the same without new prefix. So with prefix, there's still only 1 bit difference

With all 3 together, you'll easily see result a valid gray code encoding.

in order to expand to 3 bit, we do the same, flip (mirror) existing gray code, prefix 0 and 1 to top half and bottom half respectively:

Decimal	Binary	Gray
0	000	000
1	001	001
2	010	011
3	011	010
4	100	110
5	101	111
6	110	101
7	111	100

and you can expand to 4, 5, ..... bit by applying same method over and over ...

Now, let's see why num ^ (num >>1 ) works

Let's start with 3 bit numbers (or 0-7), so we can use the table we generated above.

Consider number 6, its binary representation is 0b110 (I'll always prefix 0b to binary code presentation), And you can easily find/tell that 6 should be in the bottom half of the 3bit gray code table.

For number is 2, the binary representation is 0b010, it's in the top half. 

If you look close enough, you'll find out the left most bit of binary code and gray code is same, which should not be a surprise, if you follow the way how we build gray code using existing ones.

Since we already have first gray code bit, let's move on to the rest. We need to figure out the gray code for 0b10 (6 or 0b110 without first bit) for 6, and 0b10 (2 or 0b010 without first bit) for 2. The binary bit happen to be the same.

For 0b10, if you look the table of 2 bit gray code, it's in the second half, because left most bit is 1.  

For number 2, because it's in the top half of 3 bit gray code table, the order of second bit is the same as 2 bit gray code. In another word, binary bit 0 is in top half and 1 is in second half, the binary bit and gray bit is the same. 

Now comes the key part, because 6 is in the bottom half of 3 bit gray code, the rest 2 bits are flipped/mirrored from 2 bit gray code.  So the order of the second bit is flipped in 2 bit gray code table, that is if the second binary bit is 1, it's in the top half of the rest (which means gray code  bit 0), and if the second binary bit is 0, it's in the bottom half (which means gray code bit 1). Or, the binary bit and gray bit is different. 

We can continue the process until last bit.

From the process, you'll see below pattern:

previous binary bit	current binary bit	current gray code bit
0	0	0
0	1	1
1	0	1
1	1	0

That's XOR!!

so each gray code bit is the result of binary bit  XOR previous binary bit. That's exactly 

num ^ ( num >> 1)