V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ha2ha
V2EX  ›  程序员

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

  •  
  •   ha2ha · 2022-02-22 19:59:44 +08:00 · 766 次点击
    这是一个创建于 1010 天前的主题,其中的信息可能已经有所发展或是发生改变。

    下面是问题

    • 为什么 13*12 可以转换为 13 位运算,就是 12 的二进制里面有多少个 1 ,然后 13 就向左移动几位

    这里是题目

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

    示例 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;
    }
    
    Juszoe
        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 的操作就可以左移三位实现
    imn1
        2
    imn1  
       2022-02-22 20:22:35 +08:00
    你问什么?不是都写清楚了么?教程?

    正整数的二进制从右向左第 n 位有 1 ,就表示 2^(n-1)
    murmur
        3
    murmur  
       2022-02-22 20:27:17 +08:00
    求问乘法搞这些东西真的有用么,有硬件乘法器是现在 cpu 的最基本要求吧
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3275 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 10:46 · PVG 18:46 · LAX 02:46 · JFK 05:46
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.