Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Swap every pair of bits in byte

Tags:

byte

swap

bits

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!

like image 825
user541686 Avatar asked Jan 25 '11 00:01

user541686


People also ask

How do you do a byte swap?

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.

How do you swap two bits in a number?

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.

Which macro is used to swap all odd and even bits?

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.


2 Answers

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.

like image 189
Nikita Rybak Avatar answered Sep 22 '22 12:09

Nikita Rybak


You could use a 256-entry lookup table.

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

like image 35
Oliver Charlesworth Avatar answered Sep 22 '22 12:09

Oliver Charlesworth