[Solved] bits set by lookup table – Recursive macro [duplicate]

by


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
...

3

solved bits set by lookup table – Recursive macro [duplicate]