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

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

总的来说，对于位置 n 处 x 中的每 1 位，它会将 2^n 乘以 y 添加到总和中。

它在不跟踪 n 的情况下执行此操作，而是在每次迭代中将 x 的位向右移动（除以 2），并将 y 的位向左移动（乘以 2）。

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

这个有效的另一个原因是这些等价物：

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

这就是正在发生的事情的本质。第一个等价允许逐位加法，第二个等价允许相反的混洗。

Answer 2

>>>是一个无符号右移，无论数字的符号如何，基本上都填充0。

因此对于示例 7 中的值 x（二进制 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

Answer 3

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

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

对于底部因子中的每个数字，将其乘以顶部因子并将部分和加在一起。请注意我们如何 "shift" 部分和（将它们乘以 10）与底部因子的每个数字。

这也适用于二进制数。这里要记住的是，不需要乘法（乘以一个因数的数字），因为它要么是 0（不加），要么是 1（加）。

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

这基本上就是该算法的作用。检查最低有效位；如果是 1，则添加另一个因素（移位），否则不添加。

行x >>>= 1;向右移动，使下一位成为最低有效位，以便在下一次循环迭代时可以测试下一位。循环次数取决于 x 中最高有效位 1 的位置。在最后一个 1 位从 x 移出后，x 是 0 并且循环终止。

行 y <<= 1; 移动了另一个因子（乘以 2）以准备在下一次循环迭代中可能添加它。

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

Can someone explain to me this code of multiplying two variables using shifts?

java

algorithm

multiplication