c - 在 C 中的整数中找到最高设置位 (msb) 的最快/最有效的方法是什么？

Question

如果我有一些整数 n ，我想知道最高有效位的位置(也就是说，如果最低有效位在右边，我想知道最左边的位是 1 的位置)，最快的是什么/找出最有效的方法？

我知道 POSIX 支持 ffs() <strings.h> 中的方法找到第一个设置位，但似乎没有相应的 fls()方法。

是否有一些我缺少的非常明显的方法？

在无法使用 POSIX 函数实现可移植性的情况下怎么办？

编辑:关于同时适用于 32 位和 64 位架构的解决方案怎么样(许多代码 list 似乎只适用于 32 位整数)。

Answer 1

GCC has :

 -- Built-in Function: int __builtin_clz (unsigned int x)     Returns the number of leading 0-bits in X, starting at the most     significant bit position.  If X is 0, the result is undefined. -- Built-in Function: int __builtin_clzl (unsigned long)     Similar to `__builtin_clz', except the argument type is `unsigned     long'. -- Built-in Function: int __builtin_clzll (unsigned long long)     Similar to `__builtin_clz', except the argument type is `unsigned     long long'.

我希望它们能够转化为适合您当前平台的合理有效的东西，无论它是那些奇特的位旋转算法之一，还是一条指令。

---

如果您的输入可以为零，一个有用的技巧是__builtin_clz(x | 1):无条件设置低位而不修改任何其他位使得输出31 对于 x=0，不改变任何其他输入的输出。

为避免需要这样做，您的另一个选择是特定于平台的内在函数，例如 ARM GCC 的 __clz(不需要 header )，或支持 CPU 的 x86 的 _lzcnt_u32 lzcnt 指令。 (注意 lzcnt 在较旧的 CPU 上解码为 bsr 而不是错误，这为非零输入提供 31-lzcnt。)

不幸的是，没有办法在非 x86 平台上可移植地利用各种 CLZ 指令，这些指令将 input=0 的结果定义为 32 或 64(根据操作数宽度)。 x86 的 lzcnt 也这样做，而 bsr 生成一个位索引，编译器必须翻转该位索引，除非您使用 31-__builtin_clz(x) .

(“未定义结果”不是 C 未定义行为，只是一个未定义的值。它实际上是指令运行时目标寄存器中的任何内容。AMD 记录了这一点，英特尔没有，但英特尔的 CPU 有实现该行为。但它不是之前在您分配给的 C 变量中的任何内容，这通常不是 gcc 将 C 转换为 asm 时的工作方式。另请参见 Why does breaking the "output dependency" of LZCNT matter? )