Может ли кто-нибудь объяснить мне этот код умножения двух переменных с помощью сдвигов?

Итак, у меня есть следующий код для умножения двух переменных x и y с помощью сдвига влево и вправо.

class Multiply {

    public static long multiply(long x,long  y) {
        long sum = 0;
        while(x != 0) {
            if((x & 1) != 0) {
                sum = sum+y;
            }
            x >>>= 1;
            y <<= 1;
        }
        return sum;
    }

    public static void main(String args[]) {
        long x = 7;
        long y = 5;
        long z = multiply(x,y);
    }
}

Но я не понимаю логики, стоящей за этим, я понимаю, что когда вы понимаете

y<<=1

Вы удваиваете y, но что это означает, что количество итераций цикла while зависит от количества битов x?

while(x != 0)

Также почему я суммирую только в том случае, если крайний правый бит x равен 1?

   if((x & 1) != 0) {
      sum = sum+y;
   }

Я действительно пытался понять код, но так и не смог разобраться в алгоритме.


java algorithm multiplication
person ravelinx    schedule 01.08.2018    source источник

Ответы (3)


arrow_upward
4
arrow_downward

Те из нас, кто со школы помнит, как умножать два числа, каждое из которых состоит из двух или более цифр, запомнят алгоритм:

  23
 x45
 ---
 115
 92x
----
1035

Каждую цифру в нижнем множителе умножьте на верхний множитель и сложите частичные суммы. Обратите внимание, как мы «сдвигаем» частичные суммы (умножаем их на 10) с каждой цифрой нижнего множителя.

Это может относиться и к двоичным числам. Здесь следует помнить, что умножение (на цифру множителя) не требуется, потому что это либо 0 (не складывать), либо 1 (добавлять).

  101
 x110
-----
  000
 101
101
-----
11110

По сути, это то, что делает этот алгоритм. Проверить младший значащий бит; если это 1, добавьте другой множитель (сдвинутый), иначе не добавляйте.

Строка x >>>= 1; сдвигается вправо, так что следующий бит становится младшим битом, так что следующий бит может быть протестирован во время следующей итерации цикла. Количество циклов зависит от того, где находится самый старший бит 1 в x. После того, как последний бит 1 сдвигается из x, x становится 0, и цикл завершается.

Строка y <<= 1; сдвигает другой множитель (умножается на 2), готовясь к его возможному добавлению во время следующей итерации цикла.

person rgettman    schedule 01.08.2018

arrow_upward
2
arrow_downward

В целом, для каждого 1 бита в x в позиции n он добавляет 2 ^ n раз y к сумме.

Он делает это без отслеживания n, а вместо этого перетасовывает биты x из 1 позиции вправо (деление на 2) на каждой итерации и перетасовывает биты y влево (умножая на 2).

Каждый раз, когда устанавливается бит 0, который проверяется (x & 1) != 0, добавляемая сумма является текущим значением y.

Другой причиной, по которой это работает, являются эти эквивалентности:

(a + b) * y == a*y + b*y
x * y == (x/2) * (y*2)

в чем суть происходящего. Первый эквивалент допускает побитовое сложение, а второй допускает обратное перемешивание.

person Bohemian♦    schedule 01.08.2018

arrow_upward
1
arrow_downward

>>> - это беззнаковый сдвиг вправо, который в основном заполняет 0 независимо от знака числа.

Итак, для значения x в примере 7 (в двоичном формате 111) при первом выполнении x >>>= 1; вы устанавливаете самый левый бит равным нулю, поэтому оно изменяется с 111 на 011, что дает вам 3.

Сделайте это снова, теперь у вас есть от 011 до 001, что дает вам 1

Еще раз, и у вас есть от 001 до 000, что дает вам 0

По сути, это дает вам, сколько iterations, прежде чем ваше число станет равным нулю. (В основном это деление вашего числа пополам, и это целочисленное деление)

Теперь для значения y (5) вы добавляете его к своему sum, а затем удваиваете значение y.

так что вы получите:

y = 5 сумма = 5

y = 10 сумма = 15

y = 20 сумма = 35

Всего 3 итерации с x, потребовалось всего 3 сдвига.

Теперь у вас есть результат! 35

person gtgaxiola    schedule 01.08.2018