查找第一个＆QUOT; 1＆QUOT;在二进制数 [英] Find first "1" in binary number

问题描述

可能重复：
  <一href="http://stackoverflow.com/questions/9093323/efficient-bitwise-operations-for-counting-bits-or-find-the-rightleft-most-ones">Efficient位运算计数位或找到合适|最左边的人

有没有一种快速的方法来找到一个（32位）二进制数第1？

Is there a fast way to find the first 1 in a (32 bit) binary number?

例如。如果我有一些00000000 00000000 00000000千万

e.g. if I have the number 00000000 00000000 00000000 10000000

我要计算的值7（或24，从另一面，如果读），因为在该号码的第一零被存储在从右侧的第7位。

I want to calculate the value "7" (or "24", if read from the other side) since the first zero in the number is stored in the 7th bit from the right.

有一个更快的方法比做到这一点

Is there a faster way to do this than

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

也许一个特定的x86汇编指令？

Perhaps a specific x86 assembler instruction?

推荐答案

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

You are looking for the bit scan instructions of x86

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

如果使用内联汇编确保两个 POS 和输入是相同的存储类（2，4，或8字节的整数类型）。这个内联函数应该是没有问题的。

If using inline asm make sure that both pos and input are the same storage class (2, 4, or 8 byte integer types). This inline function should be no problem.

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

Most compilers have intrinsics that use this instruction, but MSVC is the only one i know that has the direct one.

有关的最高阶位设置使用 BSR 指令来代替，一样的语法。

For the highest order bit set use bsr instruction instead, same syntax.

注意：如果输入为0（无位设置），那么结果是不确定的。

NOTE: if input is 0 (no bits set) then the result is undefined!

下面是一个版本，将放在一个predefined恒进 POS 如果输入为0：

Here is a version that will put a predefined constant into pos if the input is 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供（符号的大小类型）

Define BIT_SCAN_IFZERO to whatever you like. If you want a negative number there then change size_t to ssize_t (signed size type)

这篇关于查找第一个＆QUOT; 1＆QUOT;在二进制数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！