x86 имеет инструкцию BSR, которая возвращает битовый индекс (а не число ведущих нулей выше it).
Но, к сожалению, нет переносимого свойства, которое эффективно предоставляет его всем компиляторам. GNU C обеспечивает __builtin_clz, но unsigned bitidx = 31 - __builtin_clz(x); не оптимизирует обратно только до BSR с текущими GCC и ICC. (Это относится к clang, который доказывает, что выражение эквивалентно, поэтому может ).
Следующее определяет макросы или функции BSR32() и BSR64(), которые эффективно компилируются в просто a bsr инструкцию для x86. (Вывод результата «мусор», если входные данные были нулевыми. При использовании встроенных функций невозможно воспользоваться преимуществами поведения инструкции asm, не изменяя назначение для ввода = 0.)
Переносимость не-x86 потребует дополнительных #ifdef например. отступить к 31-__builtin_clz. Большинство не-x86 ISA, если у них вообще есть бит с нулем в начале, считают начальные нули вместо того, чтобы дать вам битовый индекс. Вот почему GNU C определяет __builtin_clz как портативный встроенный модуль. (Если в целевой системе нет поддержки HW, встроенная программа будет компилироваться в программную эмуляцию, обычно вызывая вспомогательную функцию libgcc.)
#include <stdint.h>
// define BSR32() and BSR64()
#if defined(_MSC_VER) || defined(__INTEL_COMPILER)
#ifdef __INTEL_COMPILER
typedef unsigned int bsr_idx_t;
#else
#include <intrin.h> // MSVC
typedef unsigned long bsr_idx_t;
#endif
static inline
unsigned BSR32(unsigned long x){
bsr_idx_t idx;
_BitScanReverse(&idx, x); // ignore bool retval
return idx;
}
static inline
unsigned BSR64(uint64_t x) {
bsr_idx_t idx;
_BitScanReverse64(&idx, x); // ignore bool retval
return idx;
}
#elif defined(__GNUC__)
#ifdef __clang__
static inline unsigned BSR64(uint64_t x) {
return 63-__builtin_clzll(x);
// gcc/ICC can't optimize this back to just BSR, but clang can and doesn't provide alternate intrinsics
}
#else
#define BSR64 __builtin_ia32_bsrdi
#endif
#include <x86intrin.h>
#define BSR32(x) _bit_scan_reverse(x)
#endif
bsf, вероятно, не требуется такой большой помощи для компиляторов, потому что встроенная функция соответствует поведению инструкции asm по возвращению битового индекса LSB, то есть количества завершающих нулей.
Вызывающий тест unsigned test32(unsigned x) { return BSR32(x); } указывает на 1 инструкцию для всех основных компиляторов x86, в проводнике компилятора Godbolt . BSR64 также встроен в версию с 64-битным операндом. См. Также Существует ли инструкция x86 / x86_64, которая обнуляет все биты ниже старшего значащего бита? для примеров использования.
;; x64 MSVC 19.16 -O2
unsigned int test32(unsigned int) PROC ; test32, COMDAT
bsr eax, ecx
ret 0
unsigned int test32(unsigned int) ENDP ; test32
# clang -O3 -march=haswell is too "smart?" for its own good:
test32(unsigned int):
lzcnt eax, edi
xor eax, 31
ret
# gcc8.2 -O3 -march=haswell
test32(unsigned int):
bsr eax, edi
ret
# ICC19 -O3 -march=haswell
test32(unsigned int):
bsr eax, edi #15.9
ret #41.12
Смысл этого состоит в том, чтобы избежать медленного кода из портативной (не MSVC) версии:
#ifdef __GNUC__
unsigned badgcc(uint64_t x) {
return 63 - __builtin_clzll(x);
}
#endif
Без -march=haswell мы получаем только BSR от Clang, но:
# gcc8.2 -O3
badgcc(unsigned long):
bsr rdi, rdi
mov eax, 63
xor rdi, 63
sub eax, edi
ret
# ICC19.0.1 -O3
badgcc(unsigned long):
mov rax, -1 #46.17
bsr rdx, rdi #46.17
cmove rdx, rax #46.17
neg rdx #46.17
add rdx, 63 #46.17
neg edx #46.17
add edx, 63 #46.17
mov eax, edx #46.17
ret #46.17
Это просто противно. (Интересно видеть, что ICC выполняет CMOV для получения -1, если вход равен нулю. BSR устанавливает ZF в соответствии со своим входом , в отличие от большинства инструкций, которые устанавливают флаги в соответствии с результатом.)
С -march=haswell (или другим способом, позволяющим использовать инструкции BMI1), это не так плохо, но все же не так хорошо, как просто BSR. Выходные зависимости по модулю, которые компиляторы в основном работают, чтобы избежать для lzcnt, но, как ни странно, не для BSR. (Где выходная зависимость является зависимостью true из-за поведения input = 0.) Почему нарушение «выходной зависимости» LZCNT имеет значение?