首先找到二进制数"1"

Question

可能重复:
有效的按位运算,用于计数位或查找右侧|最左侧的位

有没有一种快速的方法来找到(32位)二进制数中的前1？

例如,如果我的号码是00000000 00000000 00000000 10000000

我想计算值"7"(或"24",如果从另一侧读取),因为数字中的第一个零存储在右起第7位.

有没有比这更快的方法

int pos=0;
int number = 127; //binary from above
while ((number>>pos) > 0) { pos++; }

？

也许是特定的x86汇编指令？

Answer 1

使用gcc,你可以使用__builtin_ctz和__builtin_clz. ctz给出0位的尾随数,并clz给出前导0位的数量.

Answer 2

您正在寻找 x86 的位扫描指令

__inline__ size_t bsf(size_t input) {
    size_t pos;
    __asm__ ("bsf %1, %0" : "=r" (pos) : "rm" (input));
    return pos;
}

如果使用内联 asm，请确保 和pos是input相同的存储类（2、4 或 8 字节整数类型）。这个内联函数应该没有问题。

大多数编译器都有使用此指令的内在函数，但 MSVC 是我所知道的唯一具有直接指令的编译器。

对于最高位设置，请改用bsr指令，语法相同。

注意：如果输入为 0（未设置位），则结果未定义！

pos这是一个版本，如果输入为 0，则会将预定义常量放入其中：

#define BIT_SCAN_IFZERO 0

__inline__ size_t bsf(size_t input) {
    size_t pos, ifzero = BIT_SCAN_IFZERO;
    __asm__ ( "bsf %1, %0\n\t"
              "cmovz %2, %0"
            : "=r" (pos)
            : "rm" (input)
            , "rm" (ifzero));
    return pos;
}

定义BIT_SCAN_IFZERO为您喜欢的任何内容。如果您想要负数，则更改为size_t（ssize_t有符号大小类型）