如何生成查找 table 以计算前导零 (clzlut)？

Question

我找到了 this function，但是没有解释 clzlut 查找 table 的来源（我在网上搜索了很多小时，找不到找到任何东西）：

static uint8_t clzlut[256] = {
  8,7,6,6,5,5,5,5,
  4,4,4,4,4,4,4,4,
  3,3,3,3,3,3,3,3,
  3,3,3,3,3,3,3,3,
  2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,
  2,2,2,2,2,2,2,2,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  1,1,1,1,1,1,1,1,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0,
  0,0,0,0,0,0,0,0
};

uint32_t clz(uint32_t val)
{
  uint32_t accum = 0;

  accum += clzlut[val >> 24];
  accum += (accum == 8 ) ? clzlut[(val >> 16) & 0xFF] : 0;
  accum += (accum == 16) ? clzlut[(val >>  8) & 0xFF] : 0;
  accum += (accum == 24) ? clzlut[ val        & 0xFF] : 0;

  return accum;
}

如何生成此查找 table？用于生成此查找 table 的算法是什么（在 C 或 JavaScript 或类似语言中）？我将把它用于“计数前导零”(clz) 实现。我知道 clz 有内置函数，我只是想知道如何生成回退，为了 curiosity/learning 的缘故。

Answer 1

How do you generate this lookup table?
...to know how to generate a fallback, and for curiosity/learning's sake.

For each index 0 to 255: 
  Start at count = 8. (Bit width of uint8_t)
  Copy index to i.
  while i > 0: 
    Divide i by 2.
    Decrement count.
  clzlut[index] = count

如何生成查找 table 以计算前导零 (clzlut)？

How to generate lookup table for counting leading zeroes (clzlut)?

algorithm

bit-manipulation