Lua源码笔记(1)--对数计算

平时对于以2的多少次方求解相当方便但是以2为底的对数计算用算法实现还真没认真想过,Lua源码中有一个函数详细计算了以2为底的数的近似值的方法,用来计算Lua表中哈希部分的长度值，这个值使用以2为底的对数值来保存的.

//lobject.c #54
// 这个函数是求2^result = x;返回result
int luaO_log2 (unsigned int x) {
  static const lu_byte log_2[256] = {
    0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
    6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,
    8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8
  };
  int l = -1;
  while (x >= 256) { l += 8; x >>= 8; }
  return l + log_2[x];

}

• x小于256查表方法
  数组log_2的值表示数组索引以2为底的对数近似值
  比如
  2^0 = 1 //索引0的x近似值为1,数组值填写0
  2^1 = 2 //索引1的x近似值为2,数组值填写1
  2^2 = 4 //索引2,3的x近似值为4,数组值填写2
  2^3 = 8 //索引4,5,6,7的x近似值为8,数组值填写3
  以下依次类推2^7 = 128,2^8 = 256;

• x大于256

  while (x >= 256) { l += 8; x >>= 8; }

  当x大于256时就除以256,对数值加8,x仍然可以落在256区域以内

• 结论
  luaO_log2函数的使用

  #define ceillog2(x)	(luaO_log2((x)-1) + 1)

  x为非负数,当然也不能为0
  当x=1时;result = l + log_2[0] => result = -1 + 0 = -1,修正结果为0
  当x=256时,result = l + log_2[255] => result = -1 + 8 = 7,修正结果为8
  具体参看使用