4

从 MSDN 从最高有效位 (MSB) 到最低有效位 (LSB) 搜索掩码数据以查找设置位 (1)。

unsigned char _BitScanReverse ( unsigned long * Index, unsigned long Mask );

参数 [out] 索引 加载找到的第一个设置位 (1) 的位位置。

[in] Mask 要搜索的 32 位或 64 位值。

如果掩码为零，则返回值0；否则非零。

备注 如果找到设置位，则在第一个参数中返回找到的第一个设置位的位位置。如果没有找到设置位，则返回 0；否则，返回 1。


请告诉我如何在OS X上实现安全快速的_BitScanReverse()函数？我必须使用汇编还是有更简单的方法？

4

2 回答 2

5

GCC 有一些类似的内置函数：

— 内置函数：int __builtin_clz (unsigned int x)

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

— 内置函数：int __builtin_ctz (unsigned int x)

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

如果你有零的数量，你应该能够找出第一个 1 的位置。:-)

于 2011-05-30T09:57:59.623 回答
1

下面的代码是我不久前为 Linux 编写的 - 它找到了最高设置位，我认为这就是您所要求的。它不符合您的确切规格，但应该很容易适应。

进一步说明：

  • 返回 0 表示设置了第 0 位；如果没有找到位，则返回 64。
  • 该汇编程序是为 Linux 下 GCC 使用的调用约定编写的。我不知道这在 Mac OS X 下有何不同 - 你需要检查一下。
  • 输入是一个 64 位无符号整数。
  • 每个 CPU 架构都被写入一个单独的 .S 源文件，并根据正在构建的目标使用“gcc”选择性地编译。我不使用内联汇编程序。

x86:

/*
 * Find the highest set bit in a bitboard.
 *
 * %eax: &bb
 */
.globl x86_msb;
.type x86_msb,@function;
x86_msb:
    mov 4(%eax), %edx
    bsr %edx, %eax
    jz msb_z1
    add $32, %eax
    ret
msb_z1:
    mov (%eax), %edx
    bsr %edx, %eax
    jz msb_z2
    ret
msb_z2:
    mov $64, %eax
    ret

x86_64：

/*
 * Return the offset of the highest set bit in the bitmask
 *
 * %rdi: &bb
 */
.globl x64_msb;
.type x64_msb,@function;
x64_msb:
    movq (%rdi), %rdi
    bsrq %rdi, %rax
    jz msb_empty
    ret
msb_empty:
    mov $64, %eax
    ret

以下是 Windows 实现（.asm 文件）：

x86:

;;
;; Return the offset of the highest set bit in the bitmask
;;
;; ECX: &bb
;;
public @x86_msb@4
@x86_msb@4:
    mov edx, dword ptr [ecx + 4]    ; bb (high)
    bsr eax, edx
    jz msb_z1
    add eax, 32
    ret
msb_z1:
    mov edx, dword ptr [ecx]        ; bb (low)
    bsr eax, edx
    jz msb_z2
    ret
msb_z2:
    mov eax, 64
    ret                         ; bb is empty

x86_64：

;;
;; Return the offset of the highest set bit in the bitmask
;;
;; RCX: &bb
;;
x64_msb PROC
    mov r8, qword ptr [rcx] ; r8 = bb
    bsr rax, r8         ; rax = lsb(bb)
    jz msb_empty
    ret
msb_empty:
    mov eax, 64         ; bb was empty
    ret
x64_msb ENDP
于 2011-05-30T09:35:12.080 回答