递归乘法。 写一个递归函数,不使用 *
运算符, 实现两个正整数
的相乘。
可以使用加号、减号、位移,但要吝啬一些。
示例1:
输入:A = 1, B = 10
输出:10
示例2:
输入:A = 3, B = 4
输出:12
提示:
保证乘法范围不会溢出
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/recursive-mulitply-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int multiply(int A, int B) {
if(A < B)
A^=B^=A^=B;//swap大的在前,少递归几次
if(B==1)
return A;
if((B&1)==0)//B是偶数
return multiply(A,B>>1)<<1;
else
return A + (multiply(A,B>>1)<<1);
}
};
class Solution {
public:
int multiply(int A, int B) {
int i = 0, ans = 0;
if(A < B)
A^=B^=A^=B;//swap大的在前
while(B)//把B分解成2进制数,对每一位乘以A
{
if((B&1)==1)//该位为1(1,2,4,8,16)
ans += A<<i;//移动0,1,2,3,4位
B >>= 1;//B的每位移到最右 & 1来判断
i++;
}
return ans;
}
};