快速乘算法简介

        快速乘算法的原理是俄罗斯农民乘法，这种乘法规则很简单：

• 将要相乘的两个数字写在两列；
• 将第一列乘以二，第二列除以二并写在下一行；
• 如果这一行中第二列数字为偶数，删去这一行；
• 在下一行重复上述二至三步直至第二列数字为 $1$ ；
• 将第一列未被删除的数字求和即为结果

        以 $48 \times 58$ 为例：

        从而 $48 \times 58 = 2784$ 。
        运用这个原理，我们可以对二进制数进行计算，只需要将原来的规则调整下即可。对于二进制数 $A$ 和 $B$ ，如果要计算 $A \times B$ ，那么可以：

• 如果 $B$ 末位为 $1$ ，将 $A$ 加到结果上；
• 将 $A$ 左移一位，$B$ 右移一位；
• 重复上述两步直至 $B$ 为零。

        将上述步骤用代码实现如下：

class QuickMulti {
    public int quickMulti(int A, int B) {
        int res = 0;
        while (B != 0) {
            if (B & 1 == 1) res += A;
            A <<= 1;
            B >>= 1;
        }
        return res;
    }
}

        在这里举一道题为例演示快速乘算法的使用：求1+2+…+n 。
        题目描述很简单，但要注意不能使用循环，即迭代，因此可以使用递归代替。不能使用条件判断语句，因此需要借助 $\And\And$ 逻辑运算符近似实现 $if$ 。而在Java中并不能直接在一条语句中使用 $\And\And$ ，因此可以先声明一个 $boolean$ 变量。实现代码如下：

class Solution {
    public int sumNums(int n) {
        return recurse(n, n + 1, 0) >> 1;
    }

    private int recurse(int A, int B, int res) {
        int res = 0;
        boolean b = B != 0 && (B & 1) == 1 && (res = A) > 0;
        b = B != 0 && (res += recurse(A << 1, B >> 1)) > 0;
        return res;
    }
}

        这里使用快速乘算法计算 $n \times (n + 1)$ 的值，再最后返回的时候再将结果除以 $2$ ，即利用了公式 $\large\frac{n(n + 1)}{2}$ 计算连续自然数的和。