查找表设置的位-递归宏 [英] bits set by lookup table - Recursive macro

问题描述

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

B2(n)，B4(n)，B6(n)的含义是什么?
归结为这个递归宏的基本思想是什么?

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

推荐答案

该想法是将问题递归定义为2位值":00、01、10、11.它们不是递归宏，但确实表示问题的递归分解技术.将宏排列为 cascade 可以解决以下问题:生成2 ^ 8值的表格，方法是先解决2位(生成4个值)，然后解决4位(使用2位)位解决方案4次)，然后是6位(使用4位解决方案4次)，然后是整个问题(使用6位解决方案4次).

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位为您提供四个值:0、1、2、3.0设置了0位，1设置了1位， 2也只设置了1位，而3则设置了2位.

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.

4位数字的值使用相同的模式，每个值的额外2位使用2位模式.

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

每个宏可以简化"到1位.

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)

请记住，查找表的目的是用表查找howmanybits[x]代替函数调用howmanybits(x).因此，表中的每个值都应代表该索引i的f(i)和整体函数f.

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.

因此，要真正掌握它，请追溯前几个值. B6(0)以B4(0)开头，以B2(0)开头，依次为0、1、1、2.f(0)= 0，f(1)= 1，f(2)= 1，f(3 )= 2. B4(0)继续执行B2(1)，它变为1、2、2、3.f(4)= 1，f(5)= 2，f(6)= 2，f(7)= 3.如果以二进制表示形式查看这些数字，则应该清楚这对于这8个结果是正确的.

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

这篇关于查找表设置的位-递归宏的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！