[Java] Test whether two numbers are at Gray distance

The binary representation of two numbers respects the Gray code if the numbers differ by only one bit.

Spoiler alert, our magic formula is part of one possible solution :)

Let's see some examples

1 = 01

2 = 10

They are not at Gray distance since they differ in both bits.

1 = 01

3 = 11

They are at Gray distance since they only differ in one bit. 

We could loop over all bits in both numbers and check how many differences we find but that takes time proportional to the bits in the number (arguably with the big-O tricks since the number of bits is always limited to a fix amount we could discuss whether it's constant time).

However we remember our magic formula from last time to get the lowest set bit in a number and want to use it again. Our approach could be:

x = XOR the numbers to get only the different bits. If they are Gray, there must be only one different bit.

y = getLowestSetBit(x): to get the lowest set bit in x with our magic formula

x - y == 0: if there was only one set bit x and y must be equal therefore the difference must be zero

 

When looking at the video that proposed the exercise, they present another valid solution:

x = XOR the numbers to get only the different bits. If they are Gray, there must be only one different bit.

y = x - 1: if there was only one set bit now we removed it from that place and therefore x and y don't align anymore on that bit

x & y == 0: if there was only one set bit, x and y don't align therefore the bitwise AND will give all zeros

One thing to note in both cases, is that we are talking about unsigned sequences of bits, but Java has no unsigned type, therefore in some cases (two numbers are equal or negative) we wouldn't get the correct result as going into negative territory changes the whole number in Java and not only the sign bit.