Умножьте с отрицательным целым, просто сдвинув

Question

Я пытаюсь найти способ умножения целочисленного значения на отрицательное значение только с помощью сдвига битов.

Обычно я делаю это, сдвигаясь со степенью 2, которая ближе всего к моему коэффициенту, и просто добавляя / вычитая остальные, например. x * 7 = ((x << 3) - x)

Допустим, я бы хотел вычислить x * -112. Единственный способ, которым я могу представить, - это -((x << 7) - (x << 4), так что вычислить x * 112 и затем отрицать его.

Есть ли "более красивый" способ сделать это?

Answer 1

Отрицание положительного числа в дополнении 2 выполняется путем отмены всех битов и последующего добавления 1 к результату. Например, чтобы получить -4 из 4, вы должны сделать:

4 = 000...0100 in binary. ~4 = 111...1011. -4 = 111...1100.

То же самое, чтобы поменять знак.

Чтобы вы могли сделать это:

(~((x << 7) - (x << 4))) + 1.

Не обязательно красивее, но быстрее, если мы рассмотрим побитовые операции быстрее, чем арифметические операции (особенно умножение) и игнорируем оптимизацию компилятора.

Не то чтобы я говорил, что вы должны это делать, потому что вы не должны. Хотя об этом полезно знать.

Answer 2

Заставьте компилятор сделать это, затем проверьте произведенную сборку.

Answer 3

Компьютеры внутренне представляют отрицательные целые числа в форме комплимента для двух . Одним из приятных свойств арифметики двух комплиментов является то, что умножение отрицательных чисел подобно умножению положительных чисел. Следовательно, найдите дополнение к двум и используйте ваш обычный подход.

Вот простой пример. Для простоты изложения я собираюсь использовать 8-битные целые числа и умножить на -15.

15 в шестнадцатеричном виде - это 0x0f. Комплимент двоих 0x0f - 0xf1.

Поскольку это 8-битные целые числа, вся арифметика имеет мод 0xff. В частности, обратите внимание, что 0x100 * что угодно = 0.

x * 0xf1
= x * (0x100 - 0x10 + 0x01)
= -(x * 0x10) + x
= -(x << 4) + x