递归乘法。 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。
示例 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;
}
这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。
V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。
V2EX is a community of developers, designers and creative people.