Java版LeetCode

Appearance

面试题 08.05. 递归乘法 ​

题目 ​

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

示例1:

 输入：A = 1, B = 10
 输出：10
 输入：A = 1, B = 10
 输出：10

示例2:

 输入：A = 3, B = 4
 输出：12
 输入：A = 3, B = 4
 输出：12

提示:

  1. 保证乘法范围不会溢出

题解 ​

java
public int multiply(int A, int B) {
    // 递归出点
    if (A == 0 || B == 0) {
        return 0;
    }


    // 以3*4为例 拆分成 2*4 + 1*4 + 0
    // 若是25*4 拆分成 16*4 + 8*4 + 1*4 + 0
    int i = 31;
    // 找到最高位的1
    while ((A & 1 << i) == 0) {
        i--;
    }

    // 递归拆分
    return (B << i) + this.multiply(A - (1 << i), B);
}
public int multiply(int A, int B) {
    // 递归出点
    if (A == 0 || B == 0) {
        return 0;
    }


    // 以3*4为例 拆分成 2*4 + 1*4 + 0
    // 若是25*4 拆分成 16*4 + 8*4 + 1*4 + 0
    int i = 31;
    // 找到最高位的1
    while ((A & 1 << i) == 0) {
        i--;
    }

    // 递归拆分
    return (B << i) + this.multiply(A - (1 << i), B);
}