1

What is "consecutive in gray code" supposed to mean? I mean 10 and 11 are consecutive in decimal system but what is "consecutive in gray code" meaning? I only know gray code is a binary numeral system where two successive values differ in only one bit.

Here is a solution online but I cannot understand this

private static int graycode(byte term1, byte term2) {  
  byte x = (byte)(term1^term2);  // why use XOR?
  int count = 0;  
  while(x!=0)  
  {  
    x = (byte)(x &(x-1));  // why use bitwise operator?
    count++;               // what is count?
  }  
  return count == 1;  
}

I try to understand spending a hour but I still do not have a clue.

Gene
  • 46,253
  • 4
  • 58
  • 96
KKKK
  • 347
  • 7
  • 18
  • Possible duplicate of [How to find if two numbers are consecutive numbers in gray code sequence](http://stackoverflow.com/questions/27218894/how-to-find-if-two-numbers-are-consecutive-numbers-in-gray-code-sequence) – Morwenn Mar 01 '16 at 12:38
  • 1
    Note that two neighbours in Gray code differ by only one bit (which is what the function you have computes), but two numbers differing by only bit are not always neighbours in Gray code: the Gray codes 1000 and 1010 differ by only one bit but are not neighbours (1000 and 1010 are respectively 15 and 12 in decimal). – Morwenn Mar 01 '16 at 12:40

4 Answers4

5

Two numbers are considered consecutive in gray code if they differ by only one bit in their binary representation e.g. 111 and 101 differ by only the 2nd bit. The function you have checks if two input bytes have only one bit that makes them different. So 111 and 101 would return 1 from the function whereas 111 and 100 would return 0.

XOR is used to find differences between both numbers; XOR yields 1 when bits are different and 0 otherwise e.g. 1111 XOR 1011 would give 0100. So with XOR, each bit difference is highlighted by a 1 in that position. If both numbers are consecutive gray codes then there should be only one 1 in the XOR's result. More than one 1 would indicate multiple differences thus failing the criterion. The XOR result is stored in variable x.

The next task is then to count the number of 1's -- hence the variable count. If you try other gray code pairs (of greater bit length), you will notice the XOR value obtained will always be in this format (neglecting leading zeros): 10, 100, 1000, etc. Basically, 1 followed by zeros or, in other words, always a power of 2.

If these sample XOR results were decremented by 1, you would get: 01, 011, 0111, etc. If these new values were ANDed with the original XOR results, 0 would be the result everytime. This is the logic implemented in your solution: for a consecutive gray code pair, the while loop would run only once (and increment count) after which it would terminate because x had become 0. So count = 1 at the end. For a non-consecutive pair, the loop would run more than once (try it) and count would be greater than 1 at the end.

The function uses this as a basis to return 1 if count == 1 and 0 otherwise. A bit obscure but it gets the job done.

SoreDakeNoKoto
  • 1,175
  • 1
  • 9
  • 16
1

It means the two numbers differ in exactly one bit.

So the solution begins with xor'ing the two numbers. The xor operation results in a 1 where the bits of the operands differ, else zero.

So you need to count the number of bits in the xor result and compare with 1. That's what your downloaded example does. This method of counting 1's in a binary number is a rather well-known method due to Brian Kernighan. The state x = (byte)(x & (x-1)) is bit magic that resets the highest order 1 bit to zero. There are lots of others.

Alternately you could search a table of the 8 possible bytes with 1 bit. 

byte one_bit_bytes[] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };
Gene
  • 46,253
  • 4
  • 58
  • 96
1

It is a very non-intuitive way to count how many bits in a binary number are equal to '1'.

It requires a knowledge of binary arithmetic. Start with what happens when you subtract 1 for a decimal number which is written by a '1' followed by one or more zeroes: you get a sequence of 9's, which length is equal to the number of zeroes:

1000000 - 1 = 999999

A similar thing happens with binary numbers. If you subtract 1 from a non-negative binary number, all the lowest '0' digits are replaced by '1', and the '1' just before theses zeroes is replaced by zero. This follows from the way borrowing is done in binary. Example:

0101_0000_0001_0000 - 1 = 0101_0000_0000_1111
aaaa aaaa aaab cccc   ->  aaaa aaaa aaab cccc

Notation: Underscores to improve legibility. All the digits that appear above the letter a are unchanged. The digit '1' that appears above the letter b is changed to a '0'. And the digits '0' that appear above the letter c are changed to '1'.

The next step consists of doing a bitwise AND operation with the two numbers (X) and (X-1). With the arithmetic property described above, at each iteration there is exactly one '1' digit that disappear from the number (starting from the right, i.e. the least significant bit).

By counting the number of iterations, we can know how many '1' bits were initially present in number X. The iteration stops when the variable X equals zero.

Other people have already answered the question about gray code. My answer only explains how the "bit counting" works (after XOR'ing the two values).

Sci Prog
  • 2,651
  • 1
  • 10
  • 18
0

Here is a naive test for a particular Gray code monotonic ordering (the binary reflected Gray code): 

// convert Gray code binary number to base 2 binary number
int Base2(byte Gray){ Gray^=Gray>>4; Gray^=Gray>>2; return Gray^=Gray>>1; }

// test if Gray codes are consecutive using "normal" base 2 numbers
boolean GraysAdjacent(byte x, byte y){ return 1 == abs(Base2(x)-Base2(y)); }

see especially this answer (best):
How to find if two numbers are consecutive numbers in gray code sequence

coded in C as: 

int GraysTouch(byte x, byte y){ return !( (x^y ^ 1) && ( x^y ^ (y&-y)<<1 ) ); }

 //   test          x marks the spots!    (where they touch!)
for(int i=31; i>-1; --i )
  for(int j=31; j>-1; --j )
    Serial.print((String)(GraysTouch( i^i>>1, j^j>>1 )?"x":".") +
                         (GraysTouch( j^j>>1, i^i>>1 )?"X":".") + (j?"":"\n"));

How this works: ... will be explained and not the OP code because it is highly suspect (see Caveats commentary below).

A property of XOR, aka the ^ operator, is that bits that match are 0 and bits that are different are 1. 

 1^0 == 0^1 == 1
 1^1 == 0^0 == 0

Also, for a bit, 0 XOR b works as the identity function or simply b
and
1 XOR b works as the complement (no compliments please) function or ~b.

 id(x)       ==  x == x^0
 opposite(x) == ~x == x^11111111      Why eight 1's? Are eight enough?

When comparing two bit strings with XOR, bits that are different XOR as 1, otherwise the bits must match and the XOR is 0 :

     0101                  0001111001100111000
XOR  0011            XOR   0001111001100000111
    ------                ---------------------
     0110                  0000000000000111111

This explains the x^y part of the code above.
----------------------------------------------------------------------
An aside:
n^n>>1 does a quick conversion from base 2 binary to the Gray code binary numbers used here.

Also note how potent it is that f(a,b)=a^b^b=a is idempotent for any b!
An in place swap is then a=a^b; b=a^b; a=a^b;.
Unrolled c=a^b; d=c^b; e=c^d; ie. d=a^b^b=a; e=a^b^a=b;
----------------------------------------------------------------------

Now, by definition, for two Gray coded numbers to be adjacent or consecutive there must be one and only one bit that can change and be different.

Examples:

   Johnson
     Code
     000         000         000         000 
     001         001         001         100
     011         101         011         110
     111         111         010         010
     110         011         110         011
     100         010         111         111
                 110         101         101
                 100         100         001
                             ^^^
                       this Gray coding
                     is the one used here

Examine it carefully.

Case 1
When the lowest order bit of consecutive numbers, x and y, for any of the Gray codes, are different, the rest must be the same! This is the definition of a Gray code. This means x^y must look like 0000...0001.

Remember complement, the ~ function aka 1^b? To test the last bit x^y is XOR'd with 1.

This explains the x^y ^ 1.
-------------------------------------------

Case 2
The location of the different bit in the consecutive Gray code numbers x and y is not the lowest order bit. Look carefully at these Gray code consecutive numbers. 

 001       010       101     lower order bits all match
 011       110       111
   |        |          | <-- | mark location of lowest 1 
 010       100       010  <-- XOR's

Interestingly, in this Gray code, when the lowest order bits match in x and y, so too does the location of the lowest order 1.

Even more interesting is that, for consecutive numbers, the bits are always different (for this Gray code) in the next higher order bit position!

So, x^y looks like ???...?1000...0 where 1000...0 must have at least one 0, 10 (Why?) and ???...? are the mystery bits that for consecutive Gray code numbers must be 000...0. (Why? ie. to be consecutive x^y must look like ... )

The observation is that 

  x^y    looks like  ???...?100...0   if and only if
x and y  look  like  ???...?:10...0   
                             | <-- remember? the 1 location !!

The | location can be found by either x&-x or y&-y. (Why? Why must the - be done using a 2's complement machine?)
However, the : location must be checked to see that it is 1 (Why?) and the ???...? are 000...0. (Why?)

So,

  x^y      looks like  ???...?100...0  and
(y&-y)<<1  looks like  000...0100...0

and this explains the x^y ^ ((y&-y)<<1) test.
-------------------------------------------------------------------

Why this works: ... is a consequence of the properties of the particular Gray code used here. An examination and explanation is too complicated to be given here as to why this Gray code should have these properties.

----------------------------------------------------------------------
Commentary on the inadequacies of previous answers due to OP code issues.

Caveat 1: Just to be explicit, the algorithm in the OP's question:

private static int graycode(byte term1, byte term2) {  
  byte x = (byte)(term1^term2);  // why use XOR?
  int count = 0;  
  while(x!=0)  
  {  
    x = (byte)(x &(x-1));  // why use bitwise operator?
    count++;               // what is count?
  }  
  return count == 1;  
}

has an interesting interpretation of consecutive Gray codes. It does report correctly when any two binary sequences differ in a single bit position.

If, by consecutive codes it is meant that the Gray codes are used to enumerate a monotonic ordering, there is a problem.

Specifically, the code will return true for all these pairs:

000, 001 or 000, 010 or 000, 100

so an ordering might be 001, 000, 010 but then where can 100 go? The algorithm reports (correctly) that the "consecutiveness" of 100 with either of 001 or 010 is false.

Thus 100 must immediately precede or follow 000 in an enumeration but cannot immediately precede or follow 001 or 010. DOH!!!

Caveat 2: Note x = (byte)(x & (x-1)) resets the lowest order 1 bit of x to zero.

refs:

Gray code increment function
Deriving nth Gray code from the (n-1)th Gray Code
https://electronics.stackexchange.com/questions/26677/3bit-gray-counter-using-d-flip-flops-and-logic-gates
How do I find next bit to change in a Gray code in constant time?
How to find if two numbers are consecutive numbers in gray code sequence

Community
  • 1
  • 1
ekim
  • 1