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!
Given a byte, swap the two nibbles in it. For example 100 is be represented as 01100100 in a byte (or 8 bits). The two nibbles are (0110) and (0100). If we swap the two nibbles, we get 01000110 which is 70 in decimal.
The idea is to first find the bits, then use XOR based swapping concept, i..e., to swap two numbers 'x' and 'y', we do x = x ^ y, y = y ^ x, and x = x ^ y.
Swap all odd and even bits using macro: We use the << (left shift), >> (right shift) and & (And) operators to swap the even and odd bits.
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)
.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With