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

Question

谁能告诉我，在 C 编程中计算 32 位无符号整数中前导零的数量的有效算法是什么？

Answer 1

此讨论假定您的编译器不支持该操作，或者它不能生成足够好的程序集。请注意，现在这两种情况都不太可能，因此我建议您只__builtin_clz在编译器上使用 for 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 来做到这一点。虽然我们仍然没有太多的指令级并行性，但我们确实摆脱了所有分支，并且它使用的周期比之前的解决方案更少。好多了。

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

最后，像通常让黑客高兴的那样，我们开始在陌生的领域徘徊。让我们使用浮点数计算一些前导零：

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

首先，一点警告：不要使用这个算法。就标准而言，这会触发未定义的行为。这是为了有趣的因素而复制的，而不是任何实际用途。使用后果自负。

既然免责声明已经消失，它是如何工作的？它首先将 int 转换为 double 并继续提取 double 的指数分量。整洁的东西。如果在 little-endian 机器上执行，LE 常量应该为 1，在 big-endian 机器上执行 0。

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

Answer 2

这可能是在纯 C 中执行此操作的最佳方式：

int clz(uint32_t x)
{
    static const char debruijn32[32] = {
        0, 31, 9, 30, 3, 8, 13, 29, 2, 5, 7, 21, 12, 24, 28, 19,
        1, 10, 4, 14, 6, 22, 25, 20, 11, 15, 23, 26, 16, 27, 17, 18
    };
    x |= x>>1;
    x |= x>>2;
    x |= x>>4;
    x |= x>>8;
    x |= x>>16;
    x++;
    return debruijn32[x*0x076be629>>27];
}

一个限制：如所写，它不支持零输入（结果应为 32）。如果您的所有输入都小于0x80000000，您可以通过将表中的第一个值更改为 32 来支持零而无需额外成本。否则，只需在开头添加一行：

    if (!x) return 32;

Answer 3

让我们计算不是前导零的位数。之后我们只做 (32 - n)。首先，如果数字为零，则 n 为零。否则：

n = 1 + floor(log2(x))

也就是说，我们使用以二为底的对数来找出最重要的非零位在哪个位置。我们可以使用计算 log2 的 FYL2X 指令在 x86 上有效地做到这一点。

但是现在我们谈论的是 x86 指令，我们不妨看看真正可用的指令。这里是！http://en.wikipedia.org/wiki/Find_first_set - 你可以看到有很多指令可以直接做你想做的事——如果你愿意编写汇编或者至少确认你的优化编译器会生成这些指令为您提供了一些精心编写的 C 代码。