Leetcode递归乘法

1.题目

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

示例1:

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

示例2:

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

2.解法

递归最重要的还是找到关系式,可以将结果表达出来的关系式,那么A*B可以表示为A个B相加

class Solution {
    public int multiply(int A, int B) {
        if(B == 0)
            return 0;
        return A + multiply(A,B-1);
    }
}

这里还有一种非递归解法,要对位运算比较熟悉,需要直到13*8可以表示为13左移3位

​ 举个例子,13 * 12 = 13 * (8 + 4) = 13 * 8 + 13 * 4 = (13 << 3) + (13 << 2)

class Solution {
    public int multiply(int A, int B) {
        int min = Math.min(A,B);
        int max = Math.max(A,B);
        int ans = 0;
        for(int i = 0;min != 0;i++){
            if((min & 1) == 1)
                ans += max << i;
            
            min = min >> 1;
        
        }
        return ans;
    }
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/leetcode递归乘法md