在 C 中的整数中找到最高设置位 (msb) 的最快/最有效方法是什么? [英] What is the fastest/most efficient way to find the highest set bit (msb) in an integer in C?
问题描述
如果我有一个整数 n，我想知道最高位的位置(也就是说，如果最低有效位在右边，我想知道最左边的位是 a1)、最快/最有效的查找方法是什么?
If I have some integer n, and I want to know the position of the most significant bit (that is, if the least significant bit is on the right, I want to know the position of the furthest left bit that is a 1), what is the quickest/most efficient method of finding out?
我知道POSIX支持strings.h中的ffs()方法来查找第一个设置位，但是好像没有对应的fls() 方法.
I know that POSIX supports a ffs() method in strings.h to find the first set bit, but there doesn't seem to be a corresponding fls() method.
是否有一些我遗漏的非常明显的方法?
Is there some really obvious way of doing this that I'm missing?
如果您不能使用 POSIX 函数来实现可移植性怎么办?
What about in cases where you can't use POSIX functions for portability?
适用于 32 位和 64 位架构的解决方案怎么样(许多代码清单似乎只适用于 32 位整数).
What about a solution that works on both 32 and 64 bit architectures (many of the code listings seem like they'd only work on 32 bit ints).
推荐答案
-- 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'.我希望它们能够被翻译成对您当前的平台相当有效的东西，无论是那些花哨的位处理算法之一，还是一条指令.
I'd expect them to be translated into something reasonably efficient for your current platform, whether it be one of those fancy bit-twiddling algorithms, or a single instruction.
如果您的输入可以为零，一个有用的技巧是__builtin_clz(x | 1):无条件地设置低位而不修改任何其他使输出31 for x=0，不改变任何其他输入的输出.
A useful trick if your input can be zero is __builtin_clz(x | 1): unconditionally setting the low bit without modifying any others makes the output 31 for x=0, without changing the output for any other input.
为了避免这样做，您的另一个选择是特定于平台的内在函数，例如 ARM GCC 的 __clz(不需要头文件)或 x86 的 _lzcnt_u32 在支持lzcnt 指令.(请注意，lzcnt 在较旧的 CPU 上解码为 bsr 而不是错误，这为非零输入提供了 31-lzcnt.)
To avoid needing to do that, your other option is platform-specific intrinsics like ARM GCC's __clz (no header needed), or x86's _lzcnt_u32 on CPUs that support the lzcnt instruction. (Beware that lzcnt decodes as bsr on older CPUs instead of faulting, which gives 31-lzcnt for non-zero inputs.)
不幸的是，没有办法在非 x86 平台上可移植地利用各种 CLZ 指令，这些指令将 input=0 的结果定义为 32 或 64(根据操作数宽度).x86 的 lzcnt 也这样做，而 bsr 生成一个位索引，编译器必须翻转该索引，除非您使用 31-__builtin_clz(x).
There's unfortunately no way to portably take advantage of the various CLZ instructions on non-x86 platforms that do define the result for input=0 as 32 or 64 (according to the operand width). x86's lzcnt does that, too, while bsr produces a bit-index that the compiler has to flip unless you use 31-__builtin_clz(x).
(未定义结果"不是 C 未定义行为，只是一个未定义的值.它实际上是指令运行时目标寄存器中的任何内容.AMD 记录了这一点，Intel 没有记录，但 Intel 的 CPU 做了记录实现该行为.但它不是之前在您分配给的 C 变量中的任何内容，这通常不是当 gcc 将 C 转换为 asm 时的工作方式.另见 为什么打破 LZCNT 的输出依赖"很重要?)
(The "undefined result" is not C Undefined Behavior, just a value that isn't defined. It's actually whatever was in the destination register when the instruction ran. AMD documents this, Intel doesn't, but Intel's CPUs do implement that behaviour. But it's not whatever was previously in the C variable you're assigning to, that's not usually how things work when gcc turns C into asm. See also Why does breaking the "output dependency" of LZCNT matter?)
这篇关于在 C 中的整数中找到最高设置位 (msb) 的最快/最有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
