类似快速幂,但是不知道原理,请求大佬指导

2022-02-22 19:59:44 +08:00
 ha2ha

下面是问题

这里是题目

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

示例 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;
}
756 次点击
所在节点    程序员
3 条回复
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 的操作就可以左移三位实现
imn1
2022-02-22 20:22:35 +08:00
你问什么?不是都写清楚了么?教程?

正整数的二进制从右向左第 n 位有 1 ,就表示 2^(n-1)
murmur
2022-02-22 20:27:17 +08:00
求问乘法搞这些东西真的有用么,有硬件乘法器是现在 cpu 的最基本要求吧

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/835752

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX