Sure. First the ordering. East is chosen to be zero simply because that matches the (most) standard mathematical notion..but any would do. Next the remaining are chosen in a counter-clockwise order, again to match convention. So the we have:

E=0, N=1, W=2, S=3. These four values fit exactly in 2-bits: 00, 01, 10, 11. Any direction counter-clock wise is +1 from the current and clockwise is -1. The catch is that we need to keep the values in the legal range. You could use an 'if', but the properties of 2s complement integers allow us to simply restrict the result to 2-bits and everything works out. So the AND-masking of 3 (the lower 2-bit set) restrict us to that range: 3+1 = 4 (11+01=100), 4 & 3 = 0 (100 & 011 = 0) and likewise 0-1 = -1 (00-01=11111111111111111111111111111111), -1 & 3 = 3 (111..11 & 11 = 11). These properties hold regardless the number being added or subtracted...you're moving 'n' steps in one direction or the other.

Now for the opposite version: we could turn twice CC:

`(value+2)&3`, or twice clockwise:

`(value-2)&3` and get the same result. But consider the values: N <-> S & E <-> W, or the values (in binary): 01 <-> 11 & 00 <-> 10. So the opposite direction is simply flipping the value of the 2nd bit. The "why" of this is a bit long winded (stuck below). Notice that this means that x+2 and x-2 have identical meaning (results) in 2-bit numbers. Moving on to 3, you'd find that (x+3)&3 = (x-1)&3 and (x-3)&3 = (x+1)&3.

Next I'm computing the offsets (or vector if you wish) between the two points, then compute the magnitude of each component. The comparison:

`(ax != ay || ax != 0)`, say that if the magnitudes are different then do the block OR if they aren't both zero then do the block. This could have been written as

`(dx != 0 || dy != 0)`..the reason that I didn't make that choice is because the likelihood of needed to perform two 'if's is drastically higher.

Inside that block I choose the direction with the greatest difference (arbitrary choosing N/S if the two deltas are equal in magnitude). Given an integer 'x', then (x>>31) = -1 (all bits set) if x is negative, otherwise it's zero. Anding that with '2' gives a 2 if negative, otherwise zero. So if (ax > ay) then we want to move either E or W and if 'dx' is negative then we need to go W, which is 2 and otherwise E which is 0. Likewise for N/S except we need to add 1 to get '3' for negative and otherwise '1'.

---------

Long winded why

`(x+2)&3 = x^2`. Given integers 'x' & 'y', then:

`x + y = ((x & y) + ( x | y)) = ((x ^ y) + ((x & y)<<1))`Taking the second, plug in the '2' and applying the mask:

`(x + 2) & 3 = ((x ^ 2) + ((x & 2)<<1)) & 3`Although AND doesn't generally distribute over addition, (x+y)&3 = ((x&3)+(y&3))&3 is always true, so:

`(x + 2) & 3 = ((x ^ 2)&3 + ((x & 2)<<1)&3) & 3`And since 'x' is limited to [0,3], then (x^2)&3 = (x^2) and ((x & 2)<<1)&3 = 0, therefore:

`(x + 2) & 3 = (x ^ 2)`Subtracting '2' is similar. Note that the 'xor' formulation of addition is why the black-magic averaging of two integers without over/under-flow works.

1 2 3 4
| public static final int signedAverage(int x, int y) { return (x & y) + (x ^ y) / 2; } |