Нет единой инструкции, которая может это сделать. BMI1 blsi dst,src может изолировать младший установленный бит, а не старший.то есть x & -x.Если бы у x86 была немного измененная версия blsi, мы могли бы использовать это, но это не так.
Но вы можете сделать намного лучше, чем вы предлагали ,Вход с нулем всегда будет частным случаем для битового сканирования и сдвига.В противном случае наш вывод имеет ровно 1 бит.Это 1 << bsr(input).
;; input: x in RDI
;; output: result in RAX
isolate_msb:
xor eax, eax ; tmp = 0
bsr rdi, rdi ; edi = bit index of MSB in input
jz .input_was_zero
bts rax, rdi ; rax |= 1<<edi
.input_was_zero: ; return 0 for input=0
ret
Очевидно, что для 32-битных входов используйте только 32-битные регистры.И если ноль невозможен, опустите JZ.Использование BSR вместо LZCNT дает нам битовый индекс, а не 31-битный, поэтому мы можем использовать его напрямую.Но LZCNT значительно быстрее на AMD.
Обнуление по xor находится вне критического пути, чтобы подготовить ввод для BTS.xor-zero + BTS - наиболее эффективный способ реализации 1<<n на процессорах Intel.Это 2 мопа с задержкой 2c на AMD, так что mov rax,1 / shl rax,cl было бы лучше там.Но хуже для Intel, потому что сдвиги с переменным счетом составляют 3 мопа, если только вы не используете BMI2 shlx.
В любом случае, настоящая работа здесь - BSR + BTS, так что для Intel SnB- это задержка 3 цикла + 1 циклсемьи.(https://agner.org/optimize/)
В C / C ++ вы бы написали это как
unsigned isolate_msb32(unsigned x) {
unsigned bitidx = BSR32(x);
//return 1ULL << bitidx; // if x is definitely non-zero
return x ? 1U << bitidx : x;
}
unsigned isolate_msb64(uint64_t x) {
unsigned bitidx = BSR64(x);
return x ? 1ULL << bitidx : x;
}
, где BSR32 определяется с точки зрения встроенной функции, поддерживаемой вашим компилятором. Этогде все становится сложно, особенно если вам нужна 64-битная версия. Единой переносимой встроенной функции не существует. GNU C предоставляет встроенные функции с нулями, ведущими счетчики, но GCC и ICC отстают в оптимизации 63-__builtin_clzll(x) обратно только в BSR. Вместо этого они отрицают дважды являются встроенными специально для BSR, но они даже более специфичны для компилятора, чем просто MSVC, по сравнению с компиляторами, которые поддерживают расширения GNU (gcc / clang / ICC).
#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
В проводнике компилятора Godbolt , clang и ICC компилируют это без ветвления, даже когда они не знают, что x не ноль.
Все 4 компилятора не могут использовать bts длявнедрить 1<<bit. :( Это очень дешево для Intel.
# clang7.0 -O3 -march=ivybridge (for x86-64 System V)
# with -march=haswell and later it uses lzcnt and has to negate. /sigh.
isolate_msb32(unsigned int):
bsr ecx, edi
mov eax, 1
shl rax, cl
test edi, edi
cmove eax, edi # return 1<<bsr(x) or x (0) if x was zero
ret
GCC и MSVC делают разветвленный код. Например,
# gcc8.2 -O3 -march=haswell
mov eax, edi
test edi, edi
je .L6
bsr eax, edi
mov edi, 1
shlx rax, rdi, rax # BMI2: 1 uop instead of 3 for shl rax,cl
.L6:
ret