Как реализовать функцию _BitScanReverse() для MS?

Question

От MSDN Поиск данных маски от старшего значащего бита (MSB) до младшего значащего бита (LSB) для установленного бита (1).

знак без знака _BitScanReverse (длинная беззнаковая * индекс, длинная маска без знака);

Параметры[out] Index Загружается с позицией бита первого найденного установленного бита (1).

[in] Mask 32-битное или 64-битное значение для поиска.

Возвращаемое значение0, если маска равна нулю; ненулевое в противном случае.

Заметки Если найден установленный бит, позиция бита первого найденного установленного бита возвращается в первом параметре. Если установленный бит не найден, возвращается 0; в противном случае возвращается 1.

Скажите, пожалуйста, как реализовать безопасную и быструю функцию _BitScanReverse() в OS X? Нужно ли использовать сборку или есть более простой способ?

Answer 1

GCC имеет несколько подобных встроенных модулей:

- Встроенная функция: int __builtin_clz (без знака int x)

Возвращает количество начальных 0-битов в x, начиная с самой старшей позиции бита. Если х равен 0, результат не определен.

- Встроенная функция: int __builtin_ctz (без знака int x)

Возвращает количество завершающих 0 битов в x, начиная с позиции младшего разряда. Если х равен 0, результат не определен

Если у вас есть количество нулей, вы должны быть в состоянии выяснить, где находится первая 1.:-)

Answer 2

Приведенный ниже код - это то, что я написал некоторое время назад для Linux - он находит старший бит, который, я думаю, и есть то, о чем вы просите. Он не соответствует вашим точным спецификациям, но должен легко адаптироваться.

Дальнейшие заметки:

• Возвращение 0 означает, что бит 0 был установлен; если биты не найдены, возвращается 64.
• Этот ассемблер написан для соглашения о вызовах, используемого GCC под Linux. Я не знаю, как это отличается в Mac OS X - вам нужно проверить.
• Ввод 64-битного без знака int.
• Каждая архитектура ЦП записывается в отдельный исходный файл.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