CODEWITHSUNDEEP
cbit-manipulationreverse
Eight
Eight

Reputation: 4284

How does this code work to reverse bits in number?

unsigned reverse_bits(unsigned input)
{  
     //works on 32-bit machine  
     input = (input & 0x55555555) <<  1 | (input & 0xAAAAAAAA) >>  1;
     input = (input & 0x33333333) <<  2 | (input & 0xCCCCCCCC) >>  2;
     input = (input & 0x0F0F0F0F) <<  4 | (input & 0xF0F0F0F0) >>  4;
     input = (input & 0x00FF00FF) <<  8 | (input & 0xFF00FF00) >>  8;
     input = (input & 0x0000FFFF) << 16 | (input & 0xFFFF0000) >> 16;

      return input;
}

how does this work?

Upvotes: 12

Views: 1888

Answers (5)

kapilddit
kapilddit

Reputation: 1769

unsigned reverse_bits(unsigned input)
{  
     //works on 32-bit machine  
     input = (input & 0x55555555) <<  1 | (input & 0xAAAAAAAA) >>  1;
     input = (input & 0x33333333) <<  2 | (input & 0xCCCCCCCC) >>  2;
     input = (input & 0x0F0F0F0F) <<  4 | (input & 0xF0F0F0F0) >>  4;
     input = (input & 0x00FF00FF) <<  8 | (input & 0xFF00FF00) >>  8;
     input = (input & 0x0000FFFF) << 16 | (input & 0xFFFF0000) >> 16;
     printf("\nvalue = %x",input);
     return input;
}

int _tmain()
{
    // TODO: Please replace the sample code below with your own.

    int value;
    signed int res,bit;
    signed int stPos, len;
    value = 0x12345678;

    reverse_bits(value);
    printf("\nvalue = %x",value);
    char buffer [33];
    itoa (value,buffer,2);
    printf ("\nbinary: %s\n",buffer);

    return 0;
}

Upvotes: 0

Kyle Jones
Kyle Jones

Reputation: 5532

The code first swaps single adjacent bits, then adjacent pairs of bits, and so on, doubling the size of the swap each time until chunks half the size of the integer are swapped at the end. The swapping is done by masking off the bits to be moved with AND, shifting them and then OR'ing the results together.

The animation below is helpful for visualizing what's going on, remembering that while the swap sizes increase sequentially, all the swaps at each size occur in parallel.

swapping

Upvotes: 9

Kaz
Kaz

Reputation: 58598

Suppose I have a hand of 8 cards:

7 8 9 10 J Q K A

How can we reverse them? One way is to swap adjacent pairs:

8 7 10 9 Q J A K

Then, swap adjacent groups of 2: exchange 8 7 and 10 9, etc:

10 9 8 7 A K Q J

Finally, exchange groups of four, which is half the size of 8:

A K Q J 10 9 8 7

Done.

You can do this in different orders. Why? Because the exchanges are stable with respect to each other. When we exchange the upper half of the cards with the lower half, for instance, the pairs stay in the same order. Or when we exchange pairs, the halves stay in the same order.

This is what the code is doing with the bit operations. For instance to swap pairs we can use the mask 01010101 to pick out the even bits, and 10101010 to pick out the odd bits, using the bitwise AND operation:

  ABCDEFGH     ABCDEFGH
& 01010101   & 10101010
----------   ----------
= 0B0D0F0H     A0C0E0G0

Remember, the rule for and is that given some bit value X, X & 1 = X and X & 0 = 0. The 1 bits in the mask preserve the value, and the 0 bits in the mask produce 0. This is called masking because it looks exactly like a mask used in spray-painting, etc. The 1 bits "cover" the places you don't want to "paint" with zero.

Next, the left result is shifted left one bit, and the right result shifted right. This brings about the swap:

  B0D0F0H0     0A0C0E0G

Finaly, the two are combined with logical OR. The rule for OR is that X or 0 is X. The two parts each have 0 where the other has nonzero, and so the bits simply merge:

  B0D0F0H0
| 0A0C0E0G
----------
= BADCFEHG

And now the pairs are swapped.

Upvotes: 18

Doug Currie
Doug Currie

Reputation: 41180

It can be understood by induction.

Start with the base case, a two bit number

input = (input & 0x1) <<  1 | (input & 0x2) >>  1;

Now progress to a four bit number

input = (input & 0x5) <<  1 | (input & 0xA) >>  1; // swap bits
input = (input & 0x3) <<  2 | (input & 0xc) >>  2; // swap bit pairs

Progress to an 8 bit number

input = (input & 0x55) <<  1 | (input & 0xAA) >>  1; // swap bits
input = (input & 0x33) <<  2 | (input & 0xCC) >>  2; // swap bit pairs
input = (input & 0x0F) <<  4 | (input & 0xF0) >>  4; // swap bit nibbles

and so on.

Upvotes: 8

vharavy
vharavy

Reputation: 4991

Let b[0], b[1], b[2], ..., b[31] are bits of input beginning from the least significant bit. Then b[1], b[0], b[3], b[2], ..., b[31], b[30] will be bits of

input = (input & 0x55555555) <<  1 | (input & 0xAAAAAAAA) >>  1;

Basically, it swaps neighboring bits of input. Similar, other 4 lines swaps neighboring pairs, groups of 4, groups of 8, and finally groups of 16 bits.

Upvotes: 3

Related Questions