algorithm behind the generation of the reverse bits lookup table(8 bit)

Question

I found the lookup table here. The table is generated as a reverse bits table of 8 bits.

I can not figure out why it works. Please explain the theory behind it. Thanks

static const unsigned char BitReverseTable256[256] = 
{
 #   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
 #   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
 #   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
     R6(0), R6(2), R6(1), R6(3)
};

Answer 1

First off a comment: This kind of thing is normally only done in the IOCCC. Code like this should not be used in production-environments because it is non-obvious. The reason why i mention this is to remove the false impression that this has any performance- or space benefit, the compiled code will contain the same (number of) bytes you would get if writing the 256 numbers directly into the array.

Ok, now to how it works. It works recursively of course, defining two bits at a top level R6, then two more at the next... But how in detail? Ok:

The first clue you get is the interesting 0->2->1->3 sequence. You should ask yourself "why?". This is the building block that is required for the construction. The numbers 0 1 2 3 in binary are 00 01 10 11 and if you reverse each: 00 10 01 11 which is 0 2 1 3!

Now lets take a look at what we want the table to do: It should become something like this:

00000000 10000000 01000000 11000000 
00100000 10100000 01100000 11100000 
00010000 10010000 01010000 11010000
00110000 10110000 01110000 11110000 ...

because you want it to map index 0 to 0, index 00000001 to 10000000 and so on.

Notice that the most significant (leftmost) 2 bits of each number: 00 10 01 11 for every line!

Now notice that the second most significant 2 bits of each number increase the same way (00 10 01 11) but for the "columns".

The reason why i chose to order the array in rows of length 4 is, that we found out that 2 bits are written at a time and 2 bits can create 4 patterns.

If you then continue observing the remaining numbers of the table (256 entries total) you will see that the 3rd 2 bits can be found having the 00 10 01 11 sequence if you order the table in columns of 16 and the last 2 bits when you order it in columns of 64.

Now i implicitly told you where the numbers 16 and 64 in the original macro-expansion came from.

That are the details, and to generalize: The highest level of the recursion generates the least significant 2 bits, the middle two levels do their thing and the lowest level generates the most significant 2 bits.