递归乘法。 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。
示例 1:
输入:A = 1, B = 10 输出:10 示例 2:
输入:A = 3, B = 4 输出:12
来源:力扣( LeetCode ) 链接: https://leetcode-cn.com/problems/recursive-mulitply-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路 首先,求得 A 和 B 的最小值和最大值; 然后,可以对其中的最小值当做乘数(为什么选最小值,因为选最小值当乘数,可以算的少),将其拆分成 2 的幂的和,即 min = a_0 * 2^0 + a_1 * 2^1 + ... + a_i * 2^i + ...min=a
取 0 或者 1 。其实就是用二进制的视角去看待 min ,比如 12 用二进制表示就是 1100 ,即 1000+0100 。举个例子,13 * 12 = 13 * (8 + 4) = 13 * 8 + 13 * 4 = (13 << 3) + (13 << 2); 具体详见如下代码:
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 >>= 1;
}
return ans;
}
1
Juszoe 2022-02-22 20:22:25 +08:00
左移一位相当于*2 ,12=2^3 + 2^2
13*12=13*(2^3 + 2^2)=13*2^3 + 13*2^2 这里*2^3 的操作就可以左移三位实现 |
2
imn1 2022-02-22 20:22:35 +08:00
你问什么?不是都写清楚了么?教程?
正整数的二进制从右向左第 n 位有 1 ,就表示 2^(n-1) |
3
murmur 2022-02-22 20:27:17 +08:00
求问乘法搞这些东西真的有用么,有硬件乘法器是现在 cpu 的最基本要求吧
|