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

Question

So I have the following code to multiply two variables x and y using left and right shifts.

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);
    }
}

But I dont understand the logic behind it, I understand that when you do

y<<=1

You are doubling y, but what does it mean that the number of iterations of the while loop depends on the number of bits x has?

while(x != 0) 

Also why do I only sum if the rightmost bit of x is a 1?

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

I've really tried to understand the code but I haven't been able to get my head around the algorithm.

Answer 1

Those of us who remember from school how to multiply two numbers, each with two or more digits, will remember the algorithm:

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

For every digit in the bottom factor, multiply it by the top factor and add the partial sums together. Note how we "shift" the partial sums (multiply them by 10) with each digit of the bottom factor.

This could apply to binary numbers as well. The thing to remember here is that no multiplication (by a factor's digit) is necessary, because it's either a 0 (don't add) or a 1 (add).

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

That's essentially what this algorithm does. Check the least significant bit; if it's a 1, add in the other factor (shifted), else don't add.

The line x >>>= 1; shifts right so that the next bit down becomes the least significant bit, so that the next bit can be tested during the next loop iteration. The number of loops depends on where the most significant bit 1 in x is. After the last 1 bit is shifted out of x, x is 0 and the loop terminates.

The line y <<= 1; shifts the other factor (multiplies by 2) in preparation for it be possibly added during the next loop iteration.