面试题 08.05：递归乘法

• 题目
• 解题
• • 方法一：快速幂的思想（非递归）
  • 方法二：快速幂的思想(递归)

题目连接
递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

示例1:

 输入：A = 1, B = 10
 输出：10

示例2:

 输入：A = 3, B = 4
 输出：12

参考链接

class Solution {
public:
    int multiply(int A, int B) {
        return quickMul(A,B);
    }
    int quickMul(int A,int B){
        int res=0;
        while(B){
            if(B&1){
                res+=A;
            }
            B>>=1;
            if(B){
                A+=A;
            }
        }
        return res;
    }
};

快速幂无非是，A为底数，B为指数。 if(B) A*=A;

class Solution {
public:
    int multiply(int A, int B) {
        return (B&1?A:0)+(B>1?multiply(A+A,B>>1):0);
    }
};