CODEWITHSUNDEEP
bitwise-operatorsbit-shiftgray-code
difda3a
difda3a

Reputation: 1

What is the intuition behind gray code generation?

uint BinaryToGray(uint num)
{
    return num ^ (num >> 1); // The operator >> is shift right. The operator ^ is exclusive or.
}

Why does this work?

Upvotes: 0

Views: 120

Answers (1)

luser droog
luser droog

Reputation: 19504

The wikipedia page for Gray Codes, in the section on Constructing an n-bit code, says:

Each bit is inverted if the next higher bit of the input value is set to one. This can be performed in parallel by a bit-shift and exclusive-or operation if they are available

And then a few paragraphs further down, the same C function is shown.

Consider what is happening on a bitwise level when this expression is evaluated, for a 16 bit number to keep it shorter,

  abcdefgh ijklmnop 
^ 0abcdefg hijklmno 
  -----------------
  a(a^b)(b^c)(c^d)(d^e)(e^f)(f^g)(g^h) (h^i)(i^j)(j^k)(k^l)(l^m)(m^n)(n^o)(o^p)

Each bit is being compared to the next higher bit and set if they differ, cleared if they are the same. This follows from the definitions listed earlier on the page.

Upvotes: 0

Related Questions