如何有效地计算 24 位无符号整数中的前导零？

ric*_*ici 6

TL;DR：请参阅下面的第 4 点了解 C 程序。

假设您假设的目标机器能够正确实现无符号 24 位乘法（必须返回乘积的低 24 位），您可以使用与您链接的答案中显示的相同的技巧。（但您可能不想。请参阅 [注 1]。）值得尝试了解链接答案中发生的情况。

输入减少为一小组值，其中具有相同数量前导零的所有整数映射到相同的值。这样做的简单方法是淹没每个位以覆盖其右侧的所有位位置：

    x |= x>>1;
    x |= x>>2;
    x |= x>>4;
    x |= x>>8;
    x |= x>>16;

这将适用于 17 到 32 位；如果您的目标数据类型有 9 到 16 位，您可以省略最后一个移位和或，因为在任何位的右侧没有 16 位的位位置。等等。但是对于 24 位，您将需要所有五个移位和或。

这样，您已将 x 转换为 25 个值之一（对于 24 位整数）：

    x |= x>>1;
    x |= x>>2;
    x |= x>>4;
    x |= x>>8;
    x |= x>>16;

现在，要将 x 转换为 clz，我们需要一个好的散列函数。我们不一定期望 hash(x)==clz，但我们希望 25 个可能的 x 值散列为不同的数字，理想情况下在一个小范围内。与您提供的链接一样，我们将选择的散列函数是乘以精心选择的被乘数，然后屏蔽掉一些位。使用掩码意味着我们需要选择五个位；理论上，我们可以在 24 位字的任意位置使用 5 位掩码，但为了不用想太多，我只选择了高位 5 位，与 32 位方案相同。与 32 位解决方案不同，我没有费心加 1，并且我希望为所有 25 个可能的输入区分不同的值。使用 5 位掩码和 33 个可能的 clz 值（如在 32 位情况下）无法实现等效，

由于散列函数不直接产生 clz 值，而是 0 到 31 之间的数字，我们需要将结果转换为 clz 值，该值使用 32 字节查找表，debruijn在 32 位算法中调用我不打算讨论的原因。

一个有趣的问题是如何选择具有所需特性的乘数。一种可能性是做一堆数论来优雅地发现一个解决方案。几十年前就是这样做的，但现在我可以编写一个快速而简单的 Python 程序来对所有可能的乘数进行暴力搜索。毕竟，在 24 位的情况下，只有大约 1600 万种可能性，而且其中很多都有效。我使用的实际 Python 代码是：

       x clz         x clz         x clz         x clz         x clz
-------- ---  -------- ---  -------- ---  -------- ---  -------- ---
0x000000  24  0x00001f  19  0x0003ff  14  0x007fff   9  0x0fffff   4
0x000001  23  0x00003f  18  0x0007ff  13  0x00ffff   8  0x1fffff   3
0x000003  22  0x00007f  17  0x000fff  12  0x01ffff   7  0x3fffff   2
0x000007  21  0x0000ff  16  0x001fff  11  0x03ffff   6  0x7fffff   1
0x00000f  20  0x0001ff  15  0x003fff  10  0x07ffff   5  0xffffff   0

调用next生成器表达式会返回第一个生成的值，在本例中为 0x8CB4F 或 576335。由于搜索从 0x80000 开始（这是 hash(1) 不为 0 的最小乘数），因此会立即打印结果。然后我又花了几毫秒来生成 2 19和 2 20之间所有可能的乘数，其中有 90 个，并且出于纯粹的个人审美原因选择了 0xCAE8F (831119)。最后一步是从计算的哈希函数创建查找表。（并不是说这是好的 Python。我只是从我的命令历史记录中获取它；我可能稍后会回来清理它。但为了完整起见，我将它包括在内。）：

# Compute the 25 target values
targ=[2**i - 1 for i in range(25)]
# For each possible multiplier, pute all 25 hashes, and see if they
# are all different (that is, the set of results has size 25):
next(i for i in range(2**19, 2**24)
       if len(targ)==len(set(((i * t) >> 19) & 0x1f
                              for t in targ)))

那么这只是组装C代码的问题：

lut = dict((i,-1) for i in range(32))
lut.update((((v * 0xcae8f) >> 19) & 0x1f, 24 - i)
           for i, v in enumerate(targ))
print("  static const char lut[] = {\n    " +
      ",\n    ".join(', '.join(f"{lut[i]:2}" for i in range(j, j+8))
                     for j in range(0, 32, 8)) +
      "\n  };\n")
# The result is pasted into the C code below.

测试代码依次调用clz每个 24 位整数。由于我手边没有 24 位机器，我只是假设算术在 OP 中假设的 24 位机器上的工作原理相同。

// Assumes that `unsigned int` has 24 value bits.
int clz(unsigned x) {
  static const char lut[] = {
    24, 23,  7, 18, 22,  6, -1,  9,
    -1, 17, 15, 21, 13,  5,  1, -1,
     8, 19, 10, -1, 16, 14,  2, 20,
    11, -1,  3, 12,  4, -1,  0, -1
  };
  x |= x>>1;
  x |= x>>2;
  x |= x>>4;
  x |= x>>8;
  x |= x>>16;
  return lut[((x * 0xcae8f) >> 19) & 0x1f];
}

笔记：

如果目标机器没有在硬件中实现 24 位无符号乘法——也就是说，它依赖于软件仿真——那么通过循环初始位来执行 clz 几乎肯定会更快，特别是如果你通过扫描折叠循环使用查找表一次几个位。即使机器确实进行了高效的硬件倍增，这也可能会更快。例如，您可以使用 32 项表一次扫描 6 位：

#include <stdio.h>

# For each 24-bit integer in turn (from 0 to 2**24-1), if
# clz(i) is different from clz(i-1), print clz(i) and i.
#
# Expected output is 0 and the powers of 2 up to 2**23, with
# descending clz values from 24 to 0.
int main(void) {
  int prev = -1;
  for (unsigned i = 0; i < 1<<24; ++i) {
    int pfxlen = clz(i);
    if (pfxlen != prev) {
      printf("%2d 0x%06X\n", pfxlen, i);
      prev = pfxlen;
    }
  }
  return 0;
}

该表可以减少到 48 位，但额外的代码可能会消耗掉节省的空间。

这里似乎需要进行一些澄清。首先，虽然我们一次扫描六位，但我们只使用其中五位来索引表。那是因为我们之前已经验证了所讨论的六个位并非全为零。在这种情况下，低位要么不相关（如果设置了其他位），要么为 1。此外，我们通过不加掩码的移位获得表索引；x屏蔽是不必要的，因为我们从屏蔽测试中知道所有高阶位都是 0。（但是，如果超过 24 位，这将失败。）