4

MSDN から マスク データを最上位ビット (MSB) から最下位ビット (LSB) まで検索して、設定されたビット (1) を探します。

unsigned char _BitScanReverse ( unsigned long * インデックス, 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 ビットの unsigned int です。
  • 各 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 に答える