有人能给我解释一下使用移位将两个变量相乘的代码吗？
所以我有下面的代码，用左移和右移将两个变量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;
}我真的试图理解代码，但我还不能理解算法。
回答 3
Stack Overflow用户
发布于 2018-08-02 07:58:20
我们中那些在学校里记得如何将两个数字相乘的人，每个数字都有两位或更多位，都会记住这个算法：
23
x45
---
115
92x
----
1035对于底部因子中的每个数字，将其乘以顶部因子，然后将部分和相加在一起。注意我们如何用底部因子的每个数字来“移位”部分和(乘以10)。
这也适用于二进制数。这里要记住的是，不需要乘法(乘以一个因子的数字)，因为它要么是一个加法( 0 )(不加)，要么是一个加法( 1 )。
101
x110
-----
000
101
101
-----
11110这基本上就是这个算法所做的。检查最低有效位；如果是1，则添加其他因子(移位)，否则不要添加。
行x >>>= 1;向右移位，使得下一位变为最低有效位，从而可以在下一次循环迭代期间测试下一位。循环的数量取决于x中最高有效位1的位置。最后一个1位移出x后，x为0，循环终止。
行y <<= 1;移位另一个因子(乘以2)，为它可能在下一次循环迭代中被添加做好准备。
Stack Overflow用户
发布于 2018-08-02 07:50:09
总体而言，对于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)这就是所发生的事情的本质。第一个等价物允许逐位加法，第二个等价物允许相反的混洗。
Stack Overflow用户
发布于 2018-08-02 07:51:09
>>>是一个无符号右移位，它基本上填充0，而不考虑数字的符号。
因此，对于示例7中的值x (二进制为111)，当您第一次执行x >>>= 1;时，您将最左边的位设为0，因此它从111更改为011，从而得到3。
现在011 to 001给了你1，你再做一次
再一次，001到000的结果是0
所以基本上就是在你的数字变成零之前给你多少个iterations。(基本上是将你的数字减半，这是整数除法)
现在，对于y值(5)，将其添加到sum中，然后将y的值加倍
所以你会得到：
Y=5和=5
Y= 10 sum = 15
Y= 20 sum = 35
因为x只需要移动3次，所以只需要3次迭代。
现在你有你的结果了！35
https://stackoverflow.com/questions/51643663
复制相似问题