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

Question

大多数 clz()（软件实现）是 optimized for 32 bit unsigned integer。

更新。目标特征：

CHAR_BIT                 24
sizeof(int)              1
sizeof(long int)         2
sizeof(long long int)    3

Answer 1

将 24 位整数转换为 32 位整数（通过类型双关或明确地围绕这些位进行改组），然后转换为 32 位 clz，然后减去 8。

为什么要这样做？因为在这个时代，您将很难找到一台能够处理 24 位类型的机器，首先是原生的。

Answer 2

我会寻找适用于您的平台和编译器的内置函数或内在函数。这些函数通常实现查找最高有效位数的最有效方法。例如，gcc 有 __builtin_clz 函数。

如果 24 位整数存储在字节数组中（例如从传感器接收）

#define BITS(x)  (CHAR_BIT * sizeof(x) - 24)
int unaligned24clz(const void * restrict val)
{
    unsigned u = 0;
    memcpy(&u, val, 3);

    #if defined(__GNUC__)
    return __builtin_clz(u) - BITS(u);
    #elif defined(__ICCARM__)
    return __CLZ(u) - BITS(u);
    #elif defined(__arm__)
    return __clz(u) - BITS(u);
    #else 
    return clz(u) - BITS(u); //portable version using standard C features
    #endif
}

如果以有效整数形式存储

int clz24(const unsigned u)
{
    #if defined(__GNUC__)
    return __builtin_clz(u) - BITS(u);
    #elif defined(__ICCARM__)
    return __CLZ(u) - BITS(u);
    #elif defined(__arm__)
    return __clz(u) - BITS(u);
    #else 
    return clz(u) - BITS(u); //portable version using standard C features
    #endif
}

https://godbolt.org/z/z6n1rKjba

如果需要，您可以添加更多编译器支持。

请记住，如果值为 0，则 __builtin_clz 的值未定义，因此您需要添加另一项检查。

Answer 3

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

假设您假设的目标机器能够正确实现无符号 24 位乘法（必须 return 乘积的低 24 位），您可以使用与回答你link。（但您可能不想这样做。请参阅 [注 1]。）值得尝试了解 linked 答案中发生的事情。

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

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

现在，要将 x 转换为 clz，我们需要一个好的哈希函数。我们不一定期望 hash(x)==clz，但我们希望 25 个可能的 x 值散列为不同的数字，最好是在一个小范围内。与您提供的 link 一样，我们将选择的散列函数是乘以一个精心选择的被乘数，然后屏蔽掉一些位。使用掩码意味着我们需要选择五位；理论上，我们可以在24位字的任何地方使用5位掩码，但为了不用考虑太多，我只选择了高5位，与32位方案相同。与 32 位解决方案不同，我没有加 1，我希望所有 25 个可能的输入都有不同的值。使用五位掩码和 33 个可能的 clz 值（如在 32 位情况下）是不可能的，因此如果原始输入为 0，它们必须跳过一个额外的环。

由于哈希函数不直接产生 clz 值，而是一个介于 0 和 31 之间的数字，我们需要将结果转换为 clz 值，它使用 32 字节查找 table ，在 32 位算法中称为 debruijn，原因我不打算讨论。
一个有趣的问题是如何 select 具有所需特性的乘法器。一种可能性是做一堆数论来优雅地发现解决方案。几十年前它就是这样做的，但现在我可以编写一个快速而肮脏的 Python 程序来对所有可能的乘数进行强力搜索。毕竟，在 24 位的情况下，只有大约 1600 万种可能性，而且其中很多都是可行的。我实际使用的 Python 代码是：
```
# Compute the 25 target values
targ=[2**i - 1 for i in range(25)]
# For each possible multiplier, compute 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)))
```
在生成器表达式上调用 next returns 第一个生成的值，在本例中为 0x8CB4F，或 576335。由于搜索从 0x80000 开始（这是最小的乘数hash(1) 不为 0)，立即打印结果。然后我又花了几毫秒来生成2¹⁹和2²⁰之间所有可能的乘数，其中有90个，[=79个=]ed 0xCAE8F (831119) 纯粹出于个人审美原因。最后一步是根据计算的哈希函数创建查找 table。（并不是说这很好 [=73=]。我只是从我的命令历史记录中提取它；我可能会稍后回来清理它。但为了完整性，我将它包括在内。）：
```
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.
```

那么接下来就是汇编C代码的问题了：

// 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。由于我手边没有 24 位机器，我只是假设算法在 OP 中假设的 24 位机器上的工作方式相同。

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

备注：

如果目标机器没有在硬件中实现 24 位无符号乘法——即，它依赖于软件仿真——那么几乎可以肯定的是，通过循环初始值来执行 clz 会更快位，特别是如果您通过查找 table 一次扫描多个位来折叠循环。即使机器确实进行了高效的硬件乘法运算，那也可能会更快。例如，您可以使用 32 项 table:
一次扫描六位
```
// Assumes that `unsigned int` has 24 value bits.
int clz(unsigned int x) {
  static const char lut[] = {
    5, 4, 3, 3, 2, 2, 2, 2,
    1, 1, 1, 1, 1, 1, 1, 1,
    0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0
  };
  /* Six bits at a time makes octal easier */
  if (x & 077000000u) return lut[x >> 19];
  if (x &   0770000u) return lut[x >> 13] + 6;
  if (x &     07700u) return lut[x >>  7] + 12;
  if (x             ) return lut[x >>  1] + 18;
  return 24;
}
```
table 可以减少到 48 位，但额外的代码可能会耗尽节省的空间。

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

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

How to efficiently count leading zeros in a 24 bit unsigned integer?

c

counting

unsigned-integer

leading-zero

备注：