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

Question

我有一个 20 个字/字节的数组，存储一个 160 位数。如何找到从 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)很长很长。

来自文档:

Returns the number of leading 0-bits in x, starting at the most significant bit position. If x is 0, the result is undefined

因此，从最重要的开始遍历您的整数(长整数？longlongs？)，直到找到第一个不为零的整数。然后使用适当的 __builtin_clz 找出它有多少个前导零，32 (64) 减去该数字就是您数字中最高 1 位的位置!

当然，如果您想与其他编译器兼容(您应该这样做!)，您始终可以自己实现 __builtin_clz