javaxorbitwise-xorgray-code

If given two hexadecimal numbers find if they can be consecutive in gray code


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.


Solution

  • 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.