下面是问题

为什么 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;
}

int

min

二进制

ans

3 条回复