c - 如何计算 32 位无符号整数中的前导零

Question

<分区>

Answer 1

此讨论假定您的编译器不支持该操作，或者它不能产生足够好的汇编。请注意，现在这两种情况都不太可能发生，所以我建议只使用 __builtin_clz对于 gcc 或编译器上的等效项。

请注意，确定哪个是“最佳”clz 算法只能由您来完成。现代处理器是复杂的野兽，这些算法的性能在很大程度上取决于你运行它的平台、你扔给它的数据以及使用它的代码。唯一可以确定的方法是测量、测量和测量更多。如果您无法分辨出差异，那么您可能没有在寻找瓶颈，您的时间最好花在其他地方。

现在无聊的免责声明已经被排除在外，让我们看看Hacker's Delight是什么不得不说的问题。快速调查表明，所有算法都依赖于某些描述的二分搜索。这是一个简单的例子:

int n = 32;
unsigned y;

y = x >>16; if (y != 0) { n = n -16; x = y; }
y = x >> 8; if (y != 0) { n = n - 8; x = y; }
y = x >> 4; if (y != 0) { n = n - 4; x = y; }
y = x >> 2; if (y != 0) { n = n - 2; x = y; }
y = x >> 1; if (y != 0) return n - 2;
return n - x;

请注意，这适用于 32 位整数，并且如果需要，它也可以转换为迭代版本。不幸的是，该解决方案没有大量的指令级并行性，并且有相当多的分支不能构成一个非常好的位旋转算法。请注意，存在上述代码的无分支版本，但它更加冗长，因此我不会在此处重现。

那么让我们通过使用 pop 指令(计算位数)来改进解决方案:

x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >>16);
return pop(~x);

那么这是如何工作的呢？关键是末尾的 pop(~x) 指令，它计算了 x 中零的个数。为了使零的数量有意义，我们首先需要摆脱所有不领先的 0。我们通过使用二进制算法向右传播 1 来做到这一点。虽然我们仍然没有太多的指令级并行性，但我们确实摆脱了所有分支，并且它比以前的解决方案使用更少的周期。好多了。

那么那个pop指令呢，那不是作弊吗？大多数架构都有一个 1 周期弹出指令，可以通过编译器内置指令访问(例如 gcc 的 __builtin_pop)。否则存在基于表的解决方案，但在权衡缓存访问的周期时必须小心，即使表完全保存在 L1 缓存中也是如此。

最后，就像黑客的喜悦一样，我们开始在陌生的领域游荡。让我们用 float 来计算一些前导零:

union {
    unsigned asInt[2];
    double asDouble;
};
asDouble = (double)k + 0.5;
return 1054 - (asInt[LE] >> 20);

首先，一个小警告:不要使用这个算法。就标准而言，这会触发未定义的行为。与任何实际用途相比，这是为了娱乐因素而重现的。使用后果自负。

既然免责声明已经过时，它是如何运作的？它首先将 int 转换为 double，然后继续提取 double 的指数部分。整洁的东西。如果在小端机器上执行，LE 常量应为 1，在大端机器上应为 0。

这应该让您简要了解解决此问题的各种位旋转算法。请注意，本书有这些内容的多种变体，需要进行各种权衡，但我会让您自己发现这些内容。