查表法是将一些事先计算好的结果，存储在常量数组中，运行时节省计算开销。例如，
计算字节中位1的个数，
int countBits( unsigned char dat )
{
static char nBitTab[256] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, ...... };
return nBitTab[dat];
}
或将字节按位逆序，
unsigned char reverse( unsigned char dat )
{
static char revTab[256] = { 0x0, 0x80, 0x40, ......};
return nBitTab[dat];
}
或计算0~360度的正弦值，
int sin( int ang )
{
static const int sinV[] = {
/*sin00=*/0, 1144,2287,3430,4572,5712,6850,7987,9121,10252,
/*sin10=*/11380,12505,13626,14742,15855,16962,18064,19161,20252,21336,
/*sin20=*/22415,23486,24550,25607,26656,27697,28729,29753,30767,31772,
/*sin30=*/32768,33754,34729,35693,36647,37590,38521,39441,40348,41243,
/*sin40=*/42126,42995,43852,44695,45525,46341,47143,47930,48703,49461,
/*sin50=*/50203,50931,51643,52339,53020,53684,54332,54963,55578,56175,
/*sin60=*/56756,57319,57865,58393,58903,59396,59870,60326,60764,61183,
/*sin70=*/61584,61966,62328,62672,62997,63303,63589,63856,64104,64332,
/*sin80=*/64540,64729,64898,65048,65177,65287,65376,65446,65496,65526,
/*sin90=*/65536,
};
if ( 0 <= ang && ang <= 90 )
{
return sinV[ang];
}
if ( 90 < ang && ang <= 180 )
{
return sinV[180-ang];
}
if ( 180 < ang && ang <= 270 )
{
return -sinV[ang-180];
}
if ( 270 < ang && ang < 360 )
{
return -sinV[360-ang];
}
return 0;
}
理论上，y=f(x),x的取值范围为有限种状态，且f(x)有一定运算量时，都可以考虑查表法。
如，前两个例子中x的范围是字节的256个值，第三个例子是0~90度。
运算量方面，sin的运算量大很多，因此更适合查表。另外，自定义查表法还可用定点数代替浮点数，且一般四则运算也不会溢出（定点数范围0~65535），所以进一步节省了浮点的运算量。
有些情况，x取值状态很多，无法直接用查表法，也可基于其中的公共子集进行扩展。
如要计算32位数中位1的个数，可将其拆成4个字节分别计算并求和。
如要计算0.0~90.0的sin值，可再建立一个sin0.1~0.9的常量表，然后用sin(x+y)的公式，如sin50.5=sin(50+0.5)=sin50*cos0.5+cos50+sin0.5。
另外，查表法还用于简化switch/case语句，还可将数据与代码分离。 |
