CODEWITHSUNDEEP
c++algorithmloopsmathmultiplication
Raeven
Raeven

Reputation: 623

Need clarification about this loop performing multiplication

int x, y; // x is a non-negative integer 
p = 0;
while (x > 0)
{
    if ( x % 2 == 1 )
       p = p + y;
    y = y*2;
    x = x/2;
}
// p == a*b here

I understand that this loop finds the product of 'a' and 'b' using the algebra:

a * b = (1/2)a * 2b

but I don't understand the code:

if ( x % 2 == 1 )
    p = p + y;

I was hoping someone could explain why 'p' is assigned 'p + y' on odd values of x.

Upvotes: 1

Views: 195

Answers (6)

Jerry Coffin
Jerry Coffin

Reputation: 490108

This works by observing that (for example) y * 10 = y * 8 + y * 2.

It's pretty much like doing multiplication on paper in school. For example, to multiply 14 x 21, we multiply one digit at a time (and shift left a place where needed) so we add 1x14 + 2 x 14 (shifted left one digit).

    14
  x 21
  ----
    14
   280

Here, we're doing pretty much the same thing, but working in binary instead of decimal. The right shifting has nothing to do with the numbers being odd, and everything to do with simply finding which bits in the number are set.

As we shift one operand right to find whether a bit is set, we also shift the other operand left, just like we add zeros to shift numbers left when doing arithmetic on paper in decimal.

So, viewing things in binary, we end up with something like:

      101101
    x  11010
    --------
     1011010
+  101101000
+ 1011010000

If we wanted to, instead of shifting the operand right, we could just shift the mask left so instead of repeatedly anding with 1, we'd and with 1, then with 2, then with 4, and so on (in fact, it would probably make a lot more sense that way). For better or worse, however, in assembly language (where this sort of thing is normally done) it's usually a little easier to shift the operand and use a constant for the mask than load the mask in a register and shift it when needed.

Upvotes: 1

Camille
Camille

Reputation: 1690

You should rewrite x as 2*b+1 (assuming x is odd). Then 

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

where (x/2) is meant to be the integer division. With the operation rewritten this way, you see the x/2, the 2y and the +y appear.

Upvotes: 0

LihO
LihO

Reputation: 42083

while (x > 0) {
    if (x % 2 == 1)
        p = p + y;
    y = y*2;
    x = x/2;
}

imagine x = 4, y = 5

iterations:

  1. x is even, y = 10, x = 2 (i.e. x can be divided, y should be doubled)
  2. x is even, y = 20, x = 1
  3. x is odd, p = 20, y = 40, x = 0 (i.e. x can not be divided anymore, y should be added to p)
  4. x > 0 is false, loop ends

p = 4 * y

now imagine x is odd at the beginning, let's say x = 5, y = 2:

  1. x is odd, p = 2, y = 4, x = 2
    (5/2 = 2.5, new value of x will be rounded down, y should be added BEFORE it is doubled)
  2. x is even, y = 8, x = 1
  3. x is odd, p = 10, y = 16, x = 0

p = y + 4*y

that first y is the reason, adding it to the result before it is doubled (1 * y) is in this case equivalent to 0.5 * (2 * y)

Upvotes: 1

Kevin Hopps
Kevin Hopps

Reputation: 727

Think of multiplication as repeated addition, x*y is adding y together x times. It is also the same as adding 2*y together x/2 times. Conceptually it is somewhat unclear what it means if x is odd. For example, if x=5 and y=3, what does it mean to add 2.5 times? The code notices when x is odd, adds y in, then does the y=y*2 and x=x/2. When x is odd, this throws away the .5 part. So in this example, you add y one time, then x becomes 2 (not 2.5) because integer division throws away the fraction.

At the end of each loop, you will see that the product of the original x and y is equal to p + x*y for the current values of p, x, and y. The loop iterates until x is 0, and the result is entirely in p.

It also helps to see what is going on if you make a table and update it each time through the loop. These are the values at the start of each iteration:

x | y  | p
----------
5 | 3  | 0
2 | 6  | 3
1 | 12 | 3
0 | 24 | 15

Upvotes: 1

Alan Stokes
Alan Stokes

Reputation: 18964

If x is odd, x = x/2 will set x to 0.5 less than x/2 (because integer division rounds it down). p needs to be adjusted to allow for that.

Upvotes: 1

Ry-
Ry-

Reputation: 224904

Because these are integers, a / 2 will be an integer. If a is odd, that integer has been rounded down, and you’re missing one-half b in the next iteration of the loop, i.e. one whole b in the current iteration of the loop (since b [y] is doubled each time).

Upvotes: 1

Related Questions