获取最左边位的位置

Question

我正在使用一个 5 位整数。 Objective-C 中有没有一个原生函数可以让我知道哪一位是最左边的？

即我有 01001，它会返回 8 或位置。

Answer 1

您可以构建一个查找表，包含 32 个元素：0、1、2、2、3 等。

Answer 2

这实际上与计算前导 0 的数量相同。有些 CPU 有这方面的指令，否则您可以使用诸如 Hacker's Delight 中找到的技巧。

它也相当于向下舍入到最接近的 2 次方，并且您可以在 Hacker's Delight 中找到有效的方法，例如

uint8_t flp2(uint8_t x)
{
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    return x - (x >> 1);
}

另请参阅：2 的前次幂

Answer 3

NSInteger value = 9;
NSInteger shift = 1;
for(NSInteger bit = value; bit > 1; bit = value >> ++shift);
NSInteger leftmostbit = 1 << shift;

适用于所有位数。

Answer 4

如果您不想使用表查找，我会使用

31 - __builtin_clz(yourNumber)

。

__builtin_clz( )

是 gcc、llvm-gcc 和 clang（也可能还有其他编译器）支持的编译器内在函数。它返回整数参数中前导零位的数量。从

31

中减去它就可以得到最高位设置位的位置。它应该在任何目标架构上生成相当快的代码。

Answer 5

Stanford Bit Twiddling Hacks 有很多如何实现这一点的示例。

Answer 6

如果您的意思是从右侧算起第五位（五位值的“最左边”）的任何位的值，则：

    int value = 17;
    int bit = (value >> 4) & 1; // bit is 1

如果你指的是最左边位1的位置：

    int value = 2;
    int position;
    for (position = 0; position < 5; position++) {
            int bit = (value >> position) & 1;
            if (bit == 1)
                    break;
    }
    // position is 1

最右边的位的位置为 0，五位值最左边的位为 4，如果所有位都为零，则位置为 5。

注意：就时钟周期而言，这不是最有效的解决方案。希望这是一篇相当清晰且具有教育意义的文章。 :)

Answer 7

要清除最高有效位以下的所有位：

while ( x & (x-1) ) x &= x - 1;
// 01001 => 01000

要清除最低有效位以上的所有位：

x &= -x;
// 01001 => 00001

获取字节中唯一设置位的位置：

position = ((0x56374210>>(((((x)&-(x))*0x17)>>3)&0x1C))&0x07);
// 01000 => 3

在 libkern.h 中定义了一个

clz

函数来计算 32 位 int 中的前导零。这是最接近原生 Objective-C 函数的东西。要获取 int 中最高有效位的位置：

position = 31 - clz( x );
// 01001 => 3

Answer 8

用VC++看看 _BitScanReverse/(64) in

Answer 9

我不知道 Objective C，但这就是我在 C 中的做法。

pow(2, int(log2(数字))

这应该为您提供最左边的 1 位值。

在使用此解决方案之前，请参阅下面斯蒂芬·佳能 (STEPHEN CANON) 的评论。