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

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

我们这些在学校还记得如何将两个数字相乘的人，每个数字都有两个或多个数字，会记住算法：

  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）以准备在下一次循环迭代期间可能添加它。

Answer 2

总体而言，对于 x 在位置 n 处的每 1 位，它会将 2^n 乘以 y 加到总和上。

它在不跟踪 n 的情况下执行此操作，而是在每次迭代中将 1 个位置的 x 位向右（除以 2）进行重新排列，并将 y 的位向左（乘以 2）重新排列。

每次设置 0 位时，由 测试(x & 1) != 0，添加的量是 y 的当前值。

这样做的另一个原因是这些等价：

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

这是正在发生的事情的本质。第一个等效项允许逐位添加，第二个等效项允许相反的改组。