Arithmetically interleaving bits
I added
a technique to my bithacks page for interleaving the bits of two 8-bit bytes to form a 16-bit value. I had been meaning to create such a arithmetic interleaving technique ever since I made the
ontological tableau showing it to be a glaring hole, but I hadn't got around to it. Holger Bettag emailed me the suggestion.
// Return bits from x in even positions and bits from y in the odd
unsigned short
InterleaveBitsFromBytes(unsigned char const x, unsigned char const y)
{
return ((x * 0x0101010101010101ULL & 0x8040201008040201ULL) *
0x0102040810204081ULL >> 49) & 0x5555 |
((y * 0x0101010101010101ULL & 0x8040201008040201ULL) *
0x0102040810204081ULL >> 48) & 0xAAAA;
}
This technique works by using two instances of the same basic pattern transformation, which spreads the bits of x and y out, requiring only an OR operation. The spreading is described below.
We want bit pattern abcdefgh to become a0b0c0d0e0f0g0h
abcdefgh
* 0000000100000001000000010000000100000001000000010000000100000001 = 0x0101010101010101ULL
==================================================================
abcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefghabcdefgh
& 1000000001000000001000000001000000001000000001000000001000000001 = 0x8040201008040201ULL
==================================================================
a00000000b00000000c00000000d00000000e00000000f00000000g00000000h
* 0000000100000010000001000000100000010000001000000100000010000001 = 0x0102040810204081ULL
------------------------------------------------------------------
a00000000b00000000c00000000d00000000e00000000f00000000g00000000h
+ 00b00000000c00000000d00000000e00000000f00000000g00000000h0000000
+ 0000c00000000d00000000e00000000f00000000g00000000h00000000000000
+ 000000d00000000e00000000f00000000g00000000h000000000000000000000
+ 00000000e00000000f00000000g00000000h0000000000000000000000000000
+ 0e00000000f00000000g00000000h00000000000000000000000000000000000
+ 000f00000000g00000000h000000000000000000000000000000000000000000
+ 00000g00000000h0000000000000000000000000000000000000000000000000
+ 0000000h00000000000000000000000000000000000000000000000000000000
==================================================================
aebfcgdhebfcgdhe0fcgdhe0f00dhe0f0g0he0f0g0h00f0g0h0000g0h000000h
>>1001001 = 49
==================================================================
?????????????????????????????????????????????????aebfcgdhebfcgdh
& 0000000000000000000000000000000000000000000000000101010101010101 = 0x5555
==================================================================
0000000000000000000000000000000000000000000000000a0b0c0d0e0f0g0h
Posted by seander at October 28, 2004 03:27 PM