Multiply Two Integers

题目描述

Multiply two integers without using multiplication, division

解题方法

不能使用bit wise operator, no loops

这种情况下不能使用任何loop, bit operation, 那只能采用recursion的方法。

int multiply(int x, int y)
{
   /* 0  multiplied with anything gives 0 */
   if(y == 0)
     return 0;

   /* Add x one by one */
   if(y > 0 )
     return (x + multiply(x, y-1));

  /* the case where y is negative */
   if(y < 0 )
     return -multiply(x, -y);
}

可以使用bit operation, loop

这里就可以采取和divide类似的方法，相当于用n除以1的二分法，在过程中也计算结果

class Solution(object):

    def multiply(self, m, n):
        if m == 0 or n == 0:
            return 0

        sign = 1
        if (m < 0) ^ (n < 0):
            sign = -1

        divisor = 2
        result = 0
        while n >= divisor:
            i = 1
            a = 2
            while a <= n:
                a = a << 1
                i += 1

            result += m * ( 1 << (i-1) )
            n -= (1 << (i-1))

        if n:
            result += m

        return result * sign