c - bits set by lookup table - Recursive macro -
this question has answer here:
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 famous in set bit problem.. have understand how output lookup table @ compile time.
but need more intuition .. means
what meaning of b2(n),b4(n),b6(n) ??
, basic idea boils down recursive macro ??
edited mean idea behind recursion
the idea "recursively defining problem down 2-bit values": 00, 01, 10, 11. they're not recursive macros, represent technique of recursive decomposition of problem. arrangement of macros cascade attacks problem of generating table of 2^8 values solving problem 2-bits (generating 4 values), 4-bits (using 2-bit solution 4 times), 6-bits (using 4-bit solution 4 times), whole problem (using 6-bit solution 4 times).
2 bits gives 4 values: 0, 1, 2, 3. 0 has 0 bits set, 1 has 1 bit set, 2 has 1 bit set, , 3 has 2 bits set.
the values 4 bit numbers use same pattern , use 2-bit pattern 2 bits of each value.
it "simplified" down 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 purpose of lookup table replace function call howmanybits(x) table-lookup howmanybits[x]. each value in table should represent f(i) index , overall function f.
so handle on it, trace through first few values. b6(0) starts b4(0), starts b2(0), goes 0, 1, 1, 2. f(0)=0, f(1)=1, f(2)=1, f(3)=2. b4(0) continues b2(1) goes 1, 2, 2, 3. f(4)=1, f(5)=2, f(6)=2, f(7)=3. if @ these numbers in binary representation, should clear it's correct 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 ...
Comments
Post a Comment