Fastest sum of absolute values of 32 differences

A long should be treated as a list of 32 unsigned numbers, each of them just two bit long. So 0x1234F... represents

{0, 1, 0, 2, 0, 3, 1, 0, 3, 3, ...}

and 0x55AA0... represents

{1, 1, 1, 1, 2, 2, 2, 2, 0, 0, ...}

Given two such lists, I need to compute the absolute values of the pairwise differences and sum them up. To continue the example, the difference list would be

{-1, 0, -1, 1, -2, 1, -1, -2, 3, 3, ...}

Now just drop the sign and sum it up. What I did is

static int funnySum(long x, long y) {
    int result = 0;
    for (int i=0; i>= 2;
        y >>= 2;
    }
    return result;
}

It's the taxicab-distance computing algorithm used in this question of mine. It occurred to me that it can be done without any loop, however I haven't figured the details out yet.

We can try to optimize the subtraction by looking at the result table and finding a bit level hack that gives us the right result after which a modified bitcount will produce the result.

The table when viewed for each bit pair is:

00 01 10 11
        0  1  2  3 

00 0    0  1  2  3
01 1    1  0  1  2
10 2    2  1  0  1
11 3    3  2  1  0

a^b is almost the right result, only for a=1 and b=2 does this give the wrong result (3 instead of 1).

So that need to be detected and dealt with.

That means that if a&b == 0 and a^b == 3 and both a and b are not 0 then the result should be 1 which we can do by xoring the high bit of the result.

long result = a^b;
long is3 = result & result << 1; //high bit per pair will contain whether the pair is 3
is3 &= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
long is0 = a&b;
is0 = ~(is0 | is0 << 1);//high bit per pair will contain whether the pair is 0
is0 &= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
long notBoth0 = (a|a<<1) & (b|b<<1);
notBoth0 &= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
result ^= is3 & is0 & notBoth0; // only invert the bits set in is3, is0 and notBoth0

The other selection possibility is when the bits in a are not equal:

long result = a^b;
long is3 = result & result << 1; //high bit per pair will contain whether the pair is 3
is3 &= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
long isEq = a^(a<<1);
isEq &= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
result ^= is3 & isEq0; // only invert the bits set in is3 and isEq0

The modified bitcount would be something like:

result = (result & 0x3333_3333_3333_3333l) + ((result >>  2) & 0x3333_3333_3333_3333l);
result = (result & 0x0f0f_0f0f_0f0f_0f0fl) + ((result >>  4) & 0x0f0f_0f0f_0f0f_0f0fl);
result = (result & 0x00ff_00ff_00ff_00ffl) + ((result >>  8) & 0x00ff_00ff_00ff_00ffl);
result = (result & 0x0000_ffff_0000_ffffl) + ((result >> 16) & 0x0000_ffff_0000_ffffl);
result = (result & 0x0000_0000_ffff_ffffl) + ((result >> 32) & 0x0000_0000_ffff_ffffl);

note: I use underscores in the hexadecimal literals to make it clearer (they are legal in java 7 I believe) however in java 6 you will need to remove them.

StackExchange Code Review Q#86867, answer score: 5