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&lt;32; ++i) {
        int xNum = (int) (x &amp; 3);
        int yNum = (int) (y &amp; 3);
        result += Math.abs(xNum - yNum);

        x &gt;&gt;= 2;
        y &gt;&gt;= 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&amp;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 &amp; result &lt;&lt; 1; //high bit per pair will contain whether the pair is 3
is3 &amp;= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
long is0 = a&amp;b;
is0 = ~(is0 | is0 &lt;&lt; 1);//high bit per pair will contain whether the pair is 0
is0 &amp;= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
long notBoth0 = (a|a&lt;&lt;1) &amp; (b|b&lt;&lt;1);
notBoth0 &amp;= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
result ^= is3 &amp; is0 &amp; 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 &amp; result &lt;&lt; 1; //high bit per pair will contain whether the pair is 3
is3 &amp;= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
long isEq = a^(a&lt;&lt;1);
isEq &amp;= 0xaaaa_aaaa_aaaa_aaaal; //extract the high bit per pair
result ^= is3 &amp; isEq0; // only invert the bits set in is3 and isEq0


The modified bitcount would be something like:

result = (result &amp; 0x3333_3333_3333_3333l) + ((result &gt;&gt;  2) &amp; 0x3333_3333_3333_3333l);
result = (result &amp; 0x0f0f_0f0f_0f0f_0f0fl) + ((result &gt;&gt;  4) &amp; 0x0f0f_0f0f_0f0f_0f0fl);
result = (result &amp; 0x00ff_00ff_00ff_00ffl) + ((result &gt;&gt;  8) &amp; 0x00ff_00ff_00ff_00ffl);
result = (result &amp; 0x0000_ffff_0000_ffffl) + ((result &gt;&gt; 16) &amp; 0x0000_ffff_0000_ffffl);
result = (result &amp; 0x0000_0000_ffff_ffffl) + ((result &gt;&gt; 32) &amp; 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.