Побит
Я думаю, что лучшее, что вы можете здесь сделать, это (x3 & x1) | (~x3 & x2).В булевой алгебре это будет выражаться как AC + (!A)B. * Ни одно из обычных правил для упрощения выражений булевой алгебры, кажется, не применимо здесь, и некоторые упрощающие выражения онлайн-булевой алгебры, похоже, согласны.
* (второй A обычно пишется с чертой над ним, но я не знаю, как это сделать при уценке).
Так что вы получите что-товот так (используя uchar в качестве сокращения для unsigned char):
uchar f_bitwise(uchar x3, uchar x2, uchar x1)
{
return (x3 & x1) | (~x3 & x2);
}
Сборка, создаваемая этим (с -O0 и отбрасыванием накладных расходов на вызов функции), выглядит следующим образом:
movzx eax, BYTE PTR [rbp-4] # move x3 into register eax
and al, BYTE PTR [rbp-12] # bitwise AND the lower half of eax with x1
mov ecx, eax # store the result in ecx
cmp BYTE PTR [rbp-4], 0 # compare x3 with 0
sete al # set lower half of eax to 1 if x3 was equal to 0
mov edx, eax # store the result in edx (this now equals ~x3)
movzx eax, BYTE PTR [rbp-8] # move x2 into eax
and eax, edx # bitwise AND ~x3 (in edx) with x2 (in eax)
or eax, ecx # finally, bitwise OR eax and ecx
Результат сохраняется в eax.
Логический
Глядя на биты значений 0-7 и пытаясь различить простой шаблон для исключения, вы замечаете, что для значений 0-3,число является простым тогда и только тогда, когда x2 равно 1. Аналогично, для значений 4-7 число является простым, если и только если x1 равно 1. Это наблюдение дает простое выражение: x3 ? x1 : x2.
У меня нет доказательств того, что это самое короткое из возможных выражений с использованием логических операторов, поэтому, если у кого-то есть более короткая версия, обязательно опубликуйте ее в комментарии.Тем не менее, кажется маловероятным, что существует более короткая версия, учитывая, что это по сути один логический оператор, как вы можете видеть, если вы расширите троичный оператор в правильный if / else:
uchar f_logical(uchar x3, uchar x2, uchar x1)
{
if (x3 != 0)
return x1;
else
return x2;
}
Сборка, созданная этим, выглядит следующим образом (снова с -O0 и не считая накладных расходов на вызов функции):
cmp BYTE PTR [rbp-4], 0 # compare x3 with 0
je .L2 # if equal, jump to label L2
movzx eax, BYTE PTR [rbp-12] # move x1 into register eax
jmp .L4 # jump to label L4 (i.e., return from function)
.L2:
movzx eax, BYTE PTR [rbp-8] # move x2 into register eax
.L4:
# Function return. Result is once again stored in eax.
Я не проверял производительность ни одной из этих функций, но только изГлядя на сборку, кажется почти наверняка, что f_logical будет работать быстрее, чем f_bitwise.Он использует значительно меньше инструкций, и хотя меньшее количество инструкций не всегда соответствует быстродействию, ни одна из этих инструкций не выглядит особенно дорогой с точки зрения циклов ЦП.
Если вы отмените общие для обеих функций инструкции и сравните то, что осталось, вы получите:
f_logical: je, jmp
f_bitwise: and (2), mov (2), sete, or
Что касается , почему логическая версия короче, я думаю, что ответветвления.Только с побитовыми операциями и без ветвления вы должны учитывать все возможности в одном выражении.
Например, в (x3 & x1) | (~x3 & x2) было бы неплохо избавиться от ~x3 с правой стороны, учитывая, что вы уже знаете, x3 равен нулю,учитывая, что правая часть представляет тест для значений 0-3.Но у компьютера нет возможности узнать это, и вы не можете выразить это в более простом выражении.
С возможностью ветвления вы можете разбить проблему на две подзадачи, используя один оператор сравнения.Опять же, это работает, потому что для значений 0-3 бит x2 по существу является битом "простого числа", а для значений 4-7 бит x1 является битом "простого числа".
Кроме того, alinsoar правильно, что таблица поиска будет быстрее, но только если значение не разделено на отдельные биты.С битовыми значениями в отдельных переменных вам нужно либо восстановить число, используя что-то вроде x3<<2 | x2<<1 | x1, либо вы должны определить свою таблицу поиска как трехмерный массив, и в этом случае компилятор генерирует кучу дополнительных инструкций для выполнения адресаарифметика, необходимая для индексации трехмерного массива.