Это , а не ответ на точный вопрос.Он работает только в том случае, если 0 не является обязательным выходным сигналом, но более эффективен.
2 n + 1 - 1, вычислено без переполнения .то есть целое число с установленными младшими n битами, для n = 0 .. all_bits
Возможно, использование этого в троичной переменной для cmov могло бы быть более эффективным решением полной проблемы в вопросе.Возможно, на основе числа * с поворотом влево с набором MSB вместо сдвига влево 1, чтобы учесть разницу в подсчете для этого по сравнению с вопросом для pow2 Вычисление.
// defined for n=0 .. sizeof(unsigned long long)*CHAR_BIT
unsigned long long setbits_upto(unsigned n) {
unsigned long long pow2 = 1ULL << n;
return pow2*2 - 1; // one more shift, and subtract 1.
}
Вывод компилятора предлагает альтернативную версию, которая подходит для некоторых ISA, если вы не используете gcc / clang (который уже делает это): запекайте с дополнительным счетчиком смен, так что это возможно дляначальный сдвиг для смещения всех бит, оставляя 0 - 1 = все установленные биты.
unsigned long long setbits_upto2(unsigned n) {
unsigned long long pow2 = 2ULL << n; // bake in the extra shift count
return pow2 - 1;
}
Таблица входов / выходов для 32-битной версии этой функции:
n -> 1<<n -> *2 - 1
0 -> 1 -> 1 = 2 - 1
1 -> 2 -> 3 = 4 - 1
2 -> 4 -> 7 = 8 - 1
3 -> 8 -> 15 = 16 - 1
...
30 -> 0x40000000 -> 0x7FFFFFFF = 0x80000000 - 1
31 -> 0x80000000 -> 0xFFFFFFFF = 0 - 1
Вы можете добавить cmov после него или другим способом обработки ввода, который должен выдавать ноль.
На x86 мы можем эффективновычислите это с помощью 3 однопроцессных инструкций : (или 2 моп для BTS на Ryzen).
xor eax, eax
bts rax, rdi ; rax = 1<<(n&63)
lea rax, [rax + rax - 1] ; one more left shift, and subtract
(3-компонентный LEA имеет задержку в 3 цикла на Intel, но я считаю, что это оптимально дляЧисло мопов и, следовательно, пропускная способность во многих случаях.)
В C эта компиляцияК счастью, для всех 64-разрядных ISA, за исключением x86-семейства Intel SnB семейства x86
C, к сожалению, глупы и не могут использовать bts даже при настройке процессоров Intel без BMI2 (где shl reg,cl равно 3 моп).
например, gcc и clang оба делают это (с dec или add -1), на Godbolt
# gcc9.1 -O3 -mtune=haswell
setbits_upto(unsigned int):
mov ecx, edi
mov eax, 2 ; bake in the extra shift by 1.
sal rax, cl
dec rax
ret
MSVC начинается с nв ECX из-за соглашения о вызовах Windows x64, но по модулю он и ICC делают одно и то же:
# ICC19
setbits_upto(unsigned int):
mov eax, 1 #3.21
mov ecx, edi #2.39
shl rax, cl #2.39
lea rax, QWORD PTR [-1+rax+rax] #3.21
ret #3.21
С BMI2 (-march=haswell) мы получаем код, оптимальный для AMDиз gcc / clang с -march=haswell
mov eax, 2
shlx rax, rax, rdi
add rax, -1
ICC по-прежнему использует 3-компонентный LEA, поэтому, если вы нацелены на MSVC или ICC, используйте версию 2ULL << n в источнике, независимо от того, включаете ли вы BMI2, потому чтовы не получите БТС в любом случае.И это позволяет избежать худшего из обоих миров;slow-LEA и смещение с переменным счетом вместо BTS.
На ISA, отличных от x86 (где предположительно смещения с переменным счетом эффективны , поскольку у них нет x86налог на оставление флагов без изменений, если счетчик равен нулю и может использовать любой регистр в качестве счетчика), это прекрасно компилируется.
например, AArch64.И, конечно, это может поднять константу 2 для повторного использования с другими n, как, например, x86 может с BMI2 shlx.
setbits_upto(unsigned int):
mov x1, 2
lsl x0, x1, x0
sub x0, x0, #1
ret
В основном то же самое на PowerPC, RISC-V и т. Д.