c - 如何找到从 msb 开始的第一个非零位

Question

我有一个存储 160 位数字的 20 个字/字节的数组。如何找到从 msb 开始的第一个非零位。我需要找到位的位置，然后相应地从第一个“1”位置开始我需要做一些操作。

Answer 1

如果您使用 gcc，则有内置函数可以做到这一点（以及许多其他事情）

http://gcc.gnu.org/onlinedocs/gcc-4.5.4/gcc/Other-Builtins.html

您正在寻找的可能是__builtin_clz（对于 unsigned int）、__builtin_clzl（对于 unsigned long）或__builtin_clzll对于 unsigned long long。

从文档中：

返回 x 中前导 0 位的数量，从最高有效位位置开始。如果 x 为 0，则结​​果未定义

所以从最重要的开始检查你的整数（longs？longlongs？），直到你找到第一个不为零的整数。然后使用适当__builtin_clz的找出它有多少个前导零，32（64）减去那个数字就是1你的数字中最高位的位置！

当然__builtin_clz，如果你想与其他编译器兼容，你总是可以自己实现（你应该这样做！）

Answer 2

您可以对每个字节进行迭代，直到找到第一个 != 0 为止。对于每个等于 0 的字节，将计数器增加 8。

然后使用该字节，执行右移操作 (>> 1)，直到该值等于 0。在每个班次中，将前一个计数器加 1。