运算

Problem：面试题 16.09. 运算

基本思路

由于程序中只允许出现加法运算符，而减法、除法或乘法运算中都可能出现取反操作，故首先应当实现数的取反功能。

设取反函数的输入值为。只利用加法实现取反，最简单的解法就是一直对加（）或（）直至，此时有。该过程可以利用倍增法进行加速，即从开始，每次与相加的数增大一倍，与异号（回退一个操作，继续从开始加起）或（结束运算）。

在实现取反函数后，减法运算便可以很方便地实现。

考虑乘法运算：对于，实际上就是个相加，故可以同样利用倍增法进行加速。

考虑除法运算：对于，实际上是计算最多能被减多少次，同样可用倍增法进行加速。

代码

Java


class Operations {

    public Operations() {

    }

    public int minus(int a, int b) {
        return a + negate(b);
    }

    public int multiply(int a, int b) {
        int mul = 0;
        int initialDelta = b > 0 ? -1 : 1;
        int initialMultiplyDelta = b < 0 ? negate(a) : a;
        int multiplyDelta = initialMultiplyDelta, delta = initialDelta;
        while (b != 0) {
            if (isOverflow(b, b + delta)) {
                delta = initialDelta;
                multiplyDelta = initialMultiplyDelta;
            }
            b += delta;
            mul += multiplyDelta;
            delta += delta;
            multiplyDelta += multiplyDelta;
        }
        return mul;
    }

    public int divide(int a, int b) {
        int div = 0;
        int initialDelta = a > 0 == b > 0 ? 1 : -1;
        int initialDivideDelta = a > 0 == b > 0 ? negate(b) : b;
        int delta = initialDelta, divideDelta = initialDivideDelta;
        while (a != 0) {
            if (isOverflow(divideDelta, initialDivideDelta)
                || isOverflow(a, a + divideDelta)) {
                if (isOverflow(a, a + initialDivideDelta)) {
                    break;
                }
                delta = initialDelta;
                divideDelta = initialDivideDelta;
            }
            div += delta;
            a += divideDelta;
            delta += delta;
            divideDelta += divideDelta;
        }
        return div;
    }

    private int negate(int x) {
        int negation = 0;
        int initialDelta = x > 0 ? 1 : -1;
        int delta = initialDelta;
        while (x != 0) {
            if (isOverflow(x, x + delta)) {
                delta = initialDelta;
            }
            x += delta;
            negation += delta;
            delta += delta;
        }
        return negation;
    }

    private boolean isOverflow(int source, int target) {
        return target != 0 && target > 0 != source > 0;
    }
}

复杂度分析

空间复杂度：Operations 构造函数的时间复杂度为；minus 函数的时间复杂度为；multiply 函数的时间复杂度为；divide 函数的时间复杂度为。

时间复杂度：，只需要常数级的变量空间。

进一步优化

对于给定的范围，此处倍增过程的所有值实际上可以实现利用数组提前保存下来，并从大值向小值方向进行匹配，将时间复杂度优化到，其中为给定整数的最大范围。