有人可以向我解释这段使用移位将两个变量相乘的代码吗？

Question

所以我有以下代码使用左移和右移将两个变量 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;

   }

我真的试图理解代码，但我一直无法理解算法。

Answer 1

我们这些在学校还记得如何将两个数字相乘的人，每个数字都有两个或多个数字，会记住算法：&nbsp; 23&nbsp;x45&nbsp;---&nbsp;115&nbsp;92x----1035对于底部因子中的每个数字，将其乘以顶部因子并将部分和相加。请注意我们如何用底部因子的每个数字“移动”部分和（将它们乘以 10）。这也适用于二进制数。这里要记住的是不需要乘法（乘以因子的数字），因为它要么是0（不加）要么是1（加）。&nbsp; 101&nbsp;x110-----&nbsp; 000&nbsp;101101-----11110这基本上就是这个算法所做的。检查最低有效位；如果是1，则添加另一个因素（移位），否则不添加。该行x >>>= 1;右移，使下一位成为最低有效位，以便可以在下一次循环迭代期间测试下一位。循环次数取决于最高有效位1的x位置。在最后1一位移出后x，x是0循环终止。该行y <<= 1;移动另一个因子（乘以 2）以准备在下一次循环迭代期间可能添加它。

Answer 2

总体而言，对于 x 在位置 n 处的每 1 位，它会将 2^n 乘以 y 加到总和上。它在不跟踪 n 的情况下执行此操作，而是在每次迭代中将 1 个位置的 x 位向右（除以 2）进行重新排列，并将 y 的位向左（乘以 2）重新排列。每次设置 0 位时，由 测试(x & 1) != 0，添加的量是 y 的当前值。这样做的另一个原因是这些等价：(a&nbsp;+&nbsp;b)&nbsp;*&nbsp;y&nbsp;==&nbsp;a*y&nbsp;+&nbsp;b*y x&nbsp;*&nbsp;y&nbsp;==&nbsp;(x/2)&nbsp;*&nbsp;(y*2)这是正在发生的事情的本质。第一个等效项允许逐位添加，第二个等效项允许相反的改组。