Swap every pair of bits in byte

This was a question asked by an NVIDIA representative at a career fair:

Write small, efficient code to swap every pair of bits inside a byte; for example, 10 11 01 10 should become 01 11 10 01.

Is there any more "efficient" way to do this than by doing a for loop through every other index? My code was small, but I can't think of how much more "efficient" this could possibly get than a loop... I'm guessing there might be a way to use XOR to avoid a loop开发者_运维技巧, but I can't figure it out.

Thanks!

Something like this should work

(i >> 1) & 01010101 + (i << 1) & 10101010

i >> 1 shifts everything by 1 bit to the right, and & 01010101 leaves only bits at even position.
Second part deals with odd bit positions in the same fasion.

Not sure how efficient it, though.

You could use a 256-entry lookup table.

Alternatively, ((x & 0x55) << 1) | ((x & 0xAA) >> 1).

Without lookup table (or to generate the thing in the first place) you can also:

• shift left and AND with left-bit mask (10101010)
• shift right and AND with right-bit mask (01010101)
• OR results together.

10 11 01 10

shifted left is 01 10 11 00 masked with 10101010 gives us 00 10 10 00

shifted right (original) is 01 01 10 11 masked with 01010101 gives us 01 01 00 01

OR our results together

01 11 10 01

So in C or C++ you could do

unsigned char bitswap( unsigned char uch )
{
   return ((uch<<1) & 0xAA) | (uch>>1) & 0x55 );
}

Just run that for all values from 0x00 to 0xff (ensure your loop terminates!) to generate your "table".

Table lookup (unless there's some particular NVIDA-specific solution he was looking for).

For 32-bit interger in java..

public int swapOddEvenbits(int x)
{
   return (  ((x & 0xaaaaaaaa) >> 1 | ((x & 0X55555555) << 1) );

}

If you are working with 64-bit, you would need to change mask..

Since there are only 256 possible combinations in a byte, this seems like a good candidate for using a lookup table based solution for any time when continuous execution speed is more important than the inital precompute and/or total memory utilisation.

For example:

lookupTable[00000000] = 00000000
lookupTable[00000001] = 00000010
lookupTable[00000010] = 00000001
...