Understanding the given snippet on bit reversal

Question

I found this snippet on 'codefights' submitted by a programmer. My solution to the problem was 30 lines, whereas this is just a beauty. But I am not able to understand the logic. Can anyone explain this.

int mirrorBits(int a) {
 int r = 0;

 for (; a; a >>= 1) 
    r = r << 1 | a & 1;  
 return r;
}

input a = 8; output : 1

As long as `a != 0`, you left shift `r` by `1` and add the least significant bit of `a`. Then you right shift `a` by `1` to deal with the next bit, if any. — Sid S, Apr 22 '18 at 05:23
This is a wrong code, it does not do what it names. The mirror of 8 is not 1. — 273K, Apr 22 '18 at 05:25
@S.M.: Doesn’t it? Take a binary representation with no leading zeros and reverse it. — Ry-, Apr 22 '18 at 05:26
@Ry why you want to remove leading zeroes? Mirroring of mirror should give in result an initial value. 8 -> 1 -> 1 is not correct. — 273K, Apr 22 '18 at 05:30
@S.M. It goes like this: 8 in binary is 1000, mirror it, it will become 0001, which is anyways 1 only. — elessar, Apr 22 '18 at 05:45

score 3 · Answer 1 · answered Apr 22 '18 at 06:00

First of all, there is a very good StackOverflow answer here: Most Efficient Algorithm for Bit Reversal ( from MSB->LSB to LSB->MSB) in C

The algorithm makes use of

>> ... binary shift right (100b >> 1 == 10b)
<< ... binary shift left (100b << 1 == 1000b
| .... binary or (100b | 10b == 110b)
& .... binary and (111b & 100b == 100b)

The for loop shifts a to the right until all bits have fallen out of a.

Imagine you start with a = 101101 then a >>= 1 does the following:

At the end of loop 1:  a == 10110
At the end of loop 2:  a == 01011
At the end of loop 3:  a == 00101
At the end of loop 4:  a == 00010
At the end of loop 5:  a == 00001
At the end of loop 6:  a == 00000 (condition fails -> loop ends)

The body of the loop shifts b one bit right, uses & to mask the last bit of a and adds it as last digit to b. The or can be used to add the last digit because << inserts 0 for all "new" bits.

Imagine you start with a = 101101

loop 1: a = 101101, r = 0 => 01
loop 2: a = 010110, r = 01 => 010
loop 3: a = 001011, r = 010 => 0101
loop 4: a = 000101, r = 0101 => 01011
loop 5: a = 000010, r = 01011 => 010110
loop 6: a = 000001, r = 010110 => 0101101

In detail the inner loop #3 does the following: (a is 001011 and r is 010)

r << 1 changes r from 010 to 0100. The last digit is the inserted 0. a & 1 masks the current last bit from a (the 1 in 001011) now we have (0100 | 1) which has the result 0101.

Warning: This algorithm is not really mirroring the bits, because you do not get the original value if you apply the algorithm to the result.

If you need a mirrored 32-bit unsigned integer you have to loop 32 times independently of the value of a:

unsigned int r = 0;
unsigned int a = 12345;

for(int i = 0; i < 32; ++i)
{
   r = (r << 1) | (a & 1);
   a >>= 1;
}

If you apply this algorithm twice, you should get the original value.

Understanding the given snippet on bit reversal

1 Answers1