Как я могу умножиться и разделиться, использование только укусило смещение и добавление?
Как я могу умножиться и разделиться, использование только укусило смещение и добавление?
5 ответов
Для умножения в терминах сложения и сдвига вы хотите разложить одно из чисел на степени двойки, например:
21 * 5 = 10101_2 * 101_2 (Initial step)
= 10101_2 * (1 * 2^2 + 0 * 2^1 + 1 * 2^0)
= 10101_2 * 2^2 + 10101_2 * 2^0
= 10101_2 << 2 + 10101_2 << 0 (Decomposed)
= 10101_2 * 4 + 10101_2 * 1
= 10101_2 * 5
= 21 * 5 (Same as initial expression)
( _2 означает основание 2)
Как видите, умножение можно разложить на сложение, сдвиг и обратно. По этой же причине умножение занимает больше времени, чем битовый сдвиг или сложение - это O (n ^ 2), а не O (n) в количестве битов. Реальные компьютерные системы (в отличие от теоретических компьютерных систем) имеют конечное число битов, поэтому умножение занимает постоянное количество времени по сравнению со сложением и сдвигом. Если я правильно помню, современные процессоры, при правильной конвейерной обработке, могут выполнять умножение почти так же быстро, как сложение, за счет неправильного использования ALU (арифметических устройств) в процессоре.
x << k == x, умноженное на 2 в степени k
x >> k == x, деленное на 2 в степени k
Вы можете использовать эти сдвиги для выполнения любых операций умножения. Например:
x * 14 == x * 16 - x * 2 == (x << 4) - (x << 1)
x * 12 == x * 8 + x * 4 == (x << 3) + (x << 2)
Чтобы разделить число на не степень двойки, я не знаю простого способа, если вы не хотите реализовать некоторую низкоуровневую логику, используйте другие бинарные операции и использовать какую-либо итерацию.
Возьмите два числа, допустим, 9 и 10, запишите их в двоичном виде - 1001 и 1010.
Начните с результата, R, равного 0.
Возьмите одно из чисел, 1010 в данном случае, назовем его A, и сдвиньте его вправо на один бит, если вы сдвинули единицу, добавьте первое число, назовем его B, к R.
Теперь сдвиньте B влево на один бит и повторяйте, пока все биты не будут сдвинуты из A.
Легче понять, что происходит, если увидеть это в записи, вот пример:
0
0000 0
10010 1
000000 0
1001000 1
------
1011010
- Сдвиг влево на 1 позицию аналогичен умножению на 2. Сдвиг вправо аналогичен делению на 2.
- Вы можете складывать в цикле чтобы умножить. Правильно выбрав переменную цикла и переменную сложения, вы можете ограничить производительность. Как только вы это изучите, вам следует использовать Крестьянское умножение
X * 2 = сдвиг на 1 бит влево
X / 2 = сдвиг на 1 бит вправо
X * 3 = сдвиг влево на 1 бит, а затем прибавление X