bits set by lookup table - Recursive macro [duplicate]

Question

This question already has an answer here:

Hint for lookup table set bit count algorithm (1 answer)

Closed 8 years ago.

static const unsigned char BitsSetTable256[256] = 
{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
    B6(0), B6(1), B6(1), B6(2)
};

This code is very famous in set bit problem.. I have understand how it will output a lookup table at compile time.

but I need more intuition for this .. means

What is meaning of B2(n),B4(n),B6(n) ??
and What is basic idea that boils down to this recursive macro ??

edited I mean what is idea behind recursion

Answer 1

The idea is "recursively defining the problem down to 2-bit values": 00, 01, 10, 11. They're not recursive macros, but does represent the technique of recursive decomposition of the problem. The arrangement of macros as a cascade attacks the problem of generating the table of 2^8 values by solving the problem for 2-bits (generating 4 values), then for 4-bits (using the 2-bit solution 4 times), then for 6-bits (using the 4-bit solution 4 times), then for the whole problem (using the 6-bit solution 4 times).

2 bits gives you four values: 0, 1, 2, 3. 0 has 0 bits set, 1 has 1 bit set, 2 also has just 1 bit set, and 3 has 2 bits set.

The values for 4 bit numbers use the same pattern and use the 2-bit pattern for the extra 2 bits of each value.

It could be "simplified" down to 1-bit per macro.

#define B1(n) n,     n+1
#define B2(n) B1(n), B1(n+1),
#define B3(n) B2(n), B2(n+1),
#define B4(n) B3(n), B3(n+1),
#define B5(n) B4(n), B4(n+1),
#define B6(n) B5(n), B5(n+1),
#define B7(n) B6(n), B6(n+1),
 B7(0), B7(1)

Remember the purpose of a lookup table is to replace a function call howmanybits(x) with a table-lookup howmanybits[x]. So each value in the table should represent the f(i) for that index i and the overall function f.

So to really get a handle on it, trace through the first few values. B6(0) starts with B4(0), which starts with B2(0), which goes 0, 1, 1, 2. f(0)=0, f(1)=1, f(2)=1, f(3)=2. B4(0) continues with B2(1) which goes 1, 2, 2, 3. f(4)=1, f(5)=2, f(6)=2, f(7)=3. If you look at these numbers in a binary representation, it should be clear that it's correct for these 8 results.

x  x_2  f(x)
0 0000  0 bits set
1 0001  1
2 0010  1
3 0011  2
4 0100  1
5 0101  2
6 0110  2
7 0111  3
...

Answer 2

"basic idea that boils down to this recursive macro"

B2(n) will generate : n, n+1, n+1, n+2

Check yourself:-

gcc -E file_name.c

Answer 3

Recall: A macro is processed by the pre-processor before your program is compiled. There are 3 steps that occur when you "compile" your code:

1. Preprocessing (handles all pre-processor directives).
2. Compiling your C source files into object files (translating into machine code).
3. Linking all of your object files and other library decencies into one executable.

B2(n) will do the following:

n, n + 1, n + 2

... where n is some number.

---

The whole point of the Bx macros are to recursively build the bit table.