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

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

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

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

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

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

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


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


gcc c++ visual-c++ bits
person Ryan    schedule 30.05.2011    source источник
comment
Из вышесказанного неясно, что возвращается в индексе - что подразумевается под битовой позицией? Не могли бы вы привести пример того, как вы хотите использовать функцию.   -  person    schedule 30.05.2011
comment
Связанный stackoverflow.com/a/20468180/61505   -  person KindDragon    schedule 11.05.2018

Ответы (2)


arrow_upward
4
arrow_downward

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

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

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

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

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

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

person Bo Persson    schedule 30.05.2011

arrow_upward
1
arrow_downward

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

Дополнительные примечания:

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