如何生成查找表来计算前导零（clzlut）？

Question

我找到了这个函数，但是没有解释

clzlut

查找表来自哪里（我在网上搜索了很多小时，找不到任何东西）：

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;
}

如何生成这个查找表？用于生成此查找表的算法是什么（C 或 JavaScript 等）？我将使用它来实现“计数前导零”(clz)。我知道有

clz

的内置函数，我只是想知道如何生成后备，并且出于好奇/学习的目的。

Answer 1

如何生成这个查找表？
...为了好奇/学习，了解如何生成后备。

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

Answer 2

这是一个通用的

clz32()

函数，可以处理组合的有符号 32 和无符号 32 位范围

[-2^31, 2^32)

，它会跳过预制表，同时 完全 消除所有位掩码、位移位、除法、或模运算。

相反，它通过向上“拉”值直到其高于 32 位来计算前导零。

• if (...)

  语句可快速处理 (1)

  n < 2^6, including all negatives

  和 (2)

  n >= 2^29

  。

• 否则，以 8 位间隔进行的无除二分搜索会提供初步的

  clz

  估计，然后由

  do { ... } while (...)

  循环每次 2 位进行微调。

• 最后一位精度是在

  return

  语句中计算的。

---

function clz32(__, ___, ____, _____, ______, _) {

    if ((__ = int(__)) < (_____ = (____ = (___ = (_ += _ = __  ||
                               !__) + _) + ___) * ___) + _____ ||
        _____ * (_____ = (______ = (___ ^= ___) * ___) * ___) <= __)

        return ___ < ____ \
               ? (__ < !__ ? _____ * !__  : _____ - (__ <= ___ ||
                   ! (_ = _____) ? __ - (_ < __) : --_ >= __ + __ \
                   ?    ___ - (__ < ____) : ++___ + (_ <  __)))   \
               : (__ < (____ *= ____ * _____)) + (__ < ____ + ____)

    else if ((______ =  __ < ______ ? ____  *  ((__ < ___ && (__ *= _____) ||
                     ! (__ *= ______)) + _) : _^(__ < _____ && (__ *= ___) ||
                     ! (__ *= ____ + ____)) * (_ + _))        &&
                                     __ < (___ ^= _ += ____ = _))
           do   ______ += ____
        while ((__ *= _) < ___)

    return --______ - (___ + ___ <= __)
}

---

0   32   23   27   46    26         4095    20
1   31   24   27   47    26         8191    19
2   30   25   27   48    26        16383    18
3   30   26   27   49    26        32767    17

4   29   27   27   50    26        65535    16
5   29   28   27   51    26       131071    15
6   29   29   27   52    26       262143    14
7   29   30   27   53    26       524287    13
  
8   28   31   27   54    26      1048575    12
9   28   32   26   55    26      2097151    11
10  28   33   26   56    26      4194303    10
11  28   34   26   57    26      8388607     9

12  28   35   26   58    26     16777215     8
13  28   36   26   59    26     33554431     7
14  28   37   26   60    26     67108863     6
15  28   38   26   61    26    134217727     5

16  27   39   26   62    26    268435455     4
17  27   40   26   63    26    536870911     3
18  27   41   26  127    25   1073741823     2
19  27   42   26  255    24   2147483647     1

20  27   43   26  511    23   4294967295     0
21  27   44   26 1023    22
22  27   45   26 2047    21