LeetCode 面试题 16.09. 运算

约 9 分钟
文章信息 3 个分类 2 个标签
分类
LeetCode 中等 程序员面试金典（第 6 版）
标签
数学 设计
目录

题目描述

✅ 面试题 16.09. 运算

题意分析

题目目标：实现整数的减法、乘法和除法，程序中只能使用加法与逻辑运算；可以出现正负常数，但不能使用减、乘、除以及位运算。
核心拆分：减法是“加上相反数”；乘法是若干个相同加数的累加；除法是不断从被除数中取走成倍的除数。
性能约束：每次只加或减 $1$ 虽然直观，但时间复杂度与数值大小成正比。用“不断翻倍、尽量取最大块”的方式，循环次数只与整数位数有关。
数值边界：32 位最小值 -2147483648 的正数绝对值无法放入 int。中间过程使用 Java long / Go int64，再按方法签名转回整数。

解法：加法翻倍与贪心取块

核心思路

negate(value) 只用加法求相反数：若 value > 0 就从 -1 开始，反之从 1 开始；每次把步长翻倍。若下一步会越过 $0$，就把步长恢复为单位步长。所有实际移动量累加起来，正好是原数的相反数。

乘法先处理符号，再对绝对值做分块累加。若剩余次数允许，就把 count 和对应的 chunk 同时翻倍；每轮取不超过剩余次数的最大块。除法同理：在不超过当前被除数的前提下，把除数及其代表的商同时翻倍，然后一次取走最大块。

全程只出现 +、比较和布尔逻辑；翻倍写成“自身加自身”，取走一块写成“加上该块的相反数”。

解题步骤

  • minus(a, b) 直接返回 a + negate(b)。
  • multiply(a, b) 记录结果符号，把较小的绝对值作为剩余次数；不断找到能取的最大翻倍块并加入答案。
  • divide(a, b) 先取绝对值；每轮找到不超过 dividend 的最大 divisor 倍数，扣除该块并累加对应的商。
  • 乘除完成后按异号条件取反。除法先处理绝对值，因此自然向零截断，例如 5 / -2 得到 -2。

以 -6 * 5 为例：先取绝对值，最大块依次翻倍为 6×1、12×2、24×4，先取 24 后还剩 $1$ 次，再取 6 得 $30$，最后恢复负号得到 $-30$。43 / 5 则一次取走 5 翻倍得到的最大块 $40$，其对应商为 $8$，余数 $3<5$，所以结果是 $8$。

代码实现

// 只使用加法和逻辑运算；long 用来容纳 Integer.MIN_VALUE 的绝对值。
class Operations {
    public Operations() {
    }

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

    public int multiply(int a, int b) {
        boolean negative = (a < 0) != (b < 0);
        long first = magnitude(a);
        long second = magnitude(b);
        if (first < second) {
            long temp = first;
            first = second;
            second = temp;
        }

        long answer = 0;
        long remaining = second;
        while (remaining > 0) {
            long count = 1;
            long negativeCount = -1;
            long chunk = first;
            while (count + count <= remaining) {
                count += count;
                negativeCount += negativeCount;
                chunk += chunk;
            }
            answer += chunk;
            remaining += negativeCount;
        }

        if (negative) {
            answer = negate(answer);
        }
        return (int) answer;
    }

    public int divide(int a, int b) {
        boolean negative = (a < 0) != (b < 0);
        long dividend = magnitude(a);
        long divisor = magnitude(b);
        long negativeDivisor = negate(divisor);
        long answer = 0;

        while (dividend >= divisor) {
            long value = divisor;
            long negativeValue = negativeDivisor;
            long count = 1;
            while (value + value <= dividend) {
                value += value;
                negativeValue += negativeValue;
                count += count;
            }
            dividend += negativeValue;
            answer += count;
        }

        if (negative) {
            answer = negate(answer);
        }
        return (int) answer;
    }

    private long magnitude(int value) {
        long wideValue = value;
        return wideValue < 0 ? negate(wideValue) : wideValue;
    }

    private long negate(long value) {
        long result = 0;
        long delta = value < 0 ? 1 : -1;
        while (value != 0) {
            long next = value + delta;
            boolean crossesZero = (value > 0 && next < 0) || (value < 0 && next > 0);
            if (crossesZero) {
                delta = value < 0 ? 1 : -1;
                continue;
            }
            value = next;
            result += delta;
            delta += delta;
        }
        return result;
    }
}

// 只使用加法和逻辑运算；int64 用来容纳 32 位最小整数的绝对值。
type Operations struct {
}

func Constructor() Operations {
    return Operations{}
}

func (operations *Operations) Minus(a int, b int) int {
    return int(int64(a) + negate64(int64(b)))
}

func (operations *Operations) Multiply(a int, b int) int {
    negative := (a < 0) != (b < 0)
    first := magnitude64(a)
    second := magnitude64(b)
    if first < second {
        first, second = second, first
    }

    answer := int64(0)
    remaining := second
    for remaining > 0 {
        count := int64(1)
        negativeCount := int64(-1)
        chunk := first
        for count+count <= remaining {
            count += count
            negativeCount += negativeCount
            chunk += chunk
        }
        answer += chunk
        remaining += negativeCount
    }

    if negative {
        answer = negate64(answer)
    }
    return int(answer)
}

func (operations *Operations) Divide(a int, b int) int {
    negative := (a < 0) != (b < 0)
    dividend := magnitude64(a)
    divisor := magnitude64(b)
    negativeDivisor := negate64(divisor)
    answer := int64(0)

    for dividend >= divisor {
        value := divisor
        negativeValue := negativeDivisor
        count := int64(1)
        for value+value <= dividend {
            value += value
            negativeValue += negativeValue
            count += count
        }
        dividend += negativeValue
        answer += count
    }

    if negative {
        answer = negate64(answer)
    }
    return int(answer)
}

func magnitude64(value int) int64 {
    wideValue := int64(value)
    if wideValue < 0 {
        return negate64(wideValue)
    }
    return wideValue
}

func negate64(value int64) int64 {
    result := int64(0)
    delta := int64(-1)
    if value < 0 {
        delta = 1
    }
    for value != 0 {
        next := value + delta
        crossesZero := (value > 0 && next < 0) || (value < 0 && next > 0)
        if crossesZero {
            if value < 0 {
                delta = 1
            } else {
                delta = -1
            }
            continue
        }
        value = next
        result += delta
        delta += delta
    }
    return result
}

复杂度分析

  • 时间复杂度：对固定的 32 位整数，循环次数有常数上界；若用 $w$ 表示数值的二进制位数，翻倍取块及相反数计算的最坏时间为 $O(w^2)$。
  • 空间复杂度：$O(1)$，只使用若干数值变量。

关键点总结

  • 先把三种运算统一到“加法”和“相反数”，再用翻倍减少循环次数。
  • 乘法中 chunk 始终表示 first * count；除法中 value 与 count 始终分别表示同一次翻倍后的数值和商贡献。
  • 乘除统一在非负绝对值上计算，最后一次处理符号，除法即可自然满足向零截断。
  • long / int64 不是为了改变返回类型，而是为了安全表示 32 位最小整数的绝对值和中间块。

易错点总结

  • 用位运算模拟加法和乘除：即使结果正确，也违反本题明确的“不允许使用位运算”。
  • 直接调用 Math.abs(a)：Math.abs(Integer.MIN_VALUE) 仍是负数，后续循环和符号判断都会失效。
  • 逐次累加：计算 1 * 2,000,000,000 需要二十亿轮；翻倍分块只需要与整数位数相关的循环。
  • 先带符号做除法：负数比较容易破坏“最大块不超过被除数”的不变量；应先取宽类型绝对值，最后恢复符号。
  • 忘记整除语义：5 / -2 应向零截断为 -2，不能按数学下取整得到 -3。题目保证输入有效，因此无需自行定义除数为零的行为。

相似题目

题目 难度 考察点
29. 两数相除 中等 翻倍除法与溢出
371. 两整数之和 中等 位运算加法（对比约束）
面试题 17.01. 不用加号的加法 简单 运算符限制