快速乘算法简介

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

        以 $48 \times 58$ 为例:

$$ \require{cancel} \bcancel{48}\qquad\bcancel{58}\\ 96\qquad29\\ \bcancel{192}\qquad\bcancel{14}\\ 384\qquad7\\ 768\qquad3\\ 1536\qquad1\\ ————\\ 2784\qquad $$

        从而 $48 \times 58 = 2784$ 。
        运用这个原理,我们可以对二进制数进行计算,只需要将原来的规则调整下即可。对于二进制数 $A$ 和 $B$ ,如果要计算 $A \times 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}$ 计算连续自然数的和。