Перемножение чисел без умножения
Перемножение чисел без использования инструкций умножения мало кому покажется интересным, но я попробую предложить свою версию:
Нужно сказать, что в корне данной задачи лежит сдвиг числа на индексы установленных бит. Более того, чем меньше установленных бит у нас будет в регистре RBX, тем меньшее количество циклов будет затрачено для вычисления произведения, с этой целью в начале кода идут команды POPCNT и XCHG, т.е. если нужно, программа обменяет значениями регистры RAX - RBX и пойдёт считать по наименьшему сопротивлению.
К примеру для перемножения чисел 65535*65535 уйдёт 16 циклов, а вот для перемножения 65535*65536 - всего один цикл.
Но даже за этот один цикл в этом коде процессор тратит (по приблизительным подсчётам) 72 тика, в то время как инструкция IMUL перемножит за 36 тиков. На 16 циклов уйдёт 516 тиков.
В результате недолгого мозгового штурма получился следующий ниже код, в регистре rsi получаем произведение rax * rbx.
mov rax, 32768 ;
mov rbx, 12345 ;
popcnt rdx, rax ; подсчитаем количество установленных бит
popcnt rcx, rbx ;
cmp rdx, rcx ;
ja @F ;
xchg rax, rbx ; выбор наименьшего множителя
@@: xor rsi, rsi ; обнулим мусор
@@: mov rdx, rax ; сохраним число для сдвигов
bsf rcx, rbx ; находим установленный бит
btc rbx, rcx ; удалим найденный ранее установленный бит
shl rdx, cl ; сдвигаем число на индекс найденого бита
add rsi, rdx ; складываем полученные в результате сдвигов числа
or rbx, rbx ; проверяем есть ли ещё установленные биты
jnz @B ; если есть, поработаем ещё
ret ; иначе - выходим