Optimizing the BitReverse

Well well well, seems finally a way emerged to do the reversing without the need of a loop. And here is the trick:

Figure this simple starting value (16 bit for demo, works the same with 64 of course):
1010000010100000
Now let’s do a little bit math:
1) We just flip all odd and even bits using a 0101010101010101 mask. For this we use the original value twice, one time shifted left by 1 bit, one time shifted right, then ANDed with the mask and back ORed together. Here is the code:
i=((i>>1) & 0x5555) | ((i & 0x5555)<<1);
What does that do? Let’s break it up:
i>>1 translates to: 0101000001010000. Now do the AND 0x5555:
0101000001010000
0101010101010101
result:
0101000001010000.
The original ANDed with 0x5555 means:
1010000010100000
0101010101010101
result:
0000000000000000
Now OR those together and you get 0101000001010000

2) Now we use 0011001100110011 as bit mask and do it again, basically flipping pairs:
i=((i>>2) & 0x3333) | ((i & 0x3333)<<2)
First half:
0101000001010000 >>2 –> 0001010000010100
AND 0011001100110011
result: 0001000000010000
Second half:
0101000001010000 AND
0011001100110011
result: 0001000000010000 << 2 : 0100000001000000
Now OR those:
0001000000010000
0100000001000000
result: 0101000001010000

3) Now we swap nibbles, but I think you got the point…
0101000001010000 –> 0000010100000101

4) Last we swap the bytes. (Which in this case results in no change.)

Voila, the bits are flipped…

Here is the sample code for 64 bit in C#:

[SqlFunction]
public static Int64 Reverse(Int64 inVal)
{
    ulong Result=(ulong) inVal;
    // odd and even
    Result=((Result>>1)& 0x5555555555555555)|((Result & 0x5555555555555555)<<1);
    // pairs
    Result=((Result>>2)& 0x3333333333333333)|((Result & 0x3333333333333333)<<2);
    // nibbles
    Result=((Result>>4)& 0x0F0F0F0F0F0F0F0F)|((Result & 0x0F0F0F0F0F0F0F0F)<<4);
    // bytes
    Result=((Result>>8)& 0x00FF00FF00FF00FF)|((Result & 0x00FF00FF00FF00FF)<<8);
    // words
    Result=((Result>>16)& 0x0000FFFF0000FFFF)|((Result & 0x0000FFFF0000FFFF)<<16);
    // double words
    Result=(Result>>32)|(Result<<32);

    return (Int64) Result;
}

One thing: If you (like me) want to flip only 63 bits (to keep the value positive) just add Result=Result<<1; before the even/odd flip.

Thanks very much to the anonymous poster that brought up the idea.