LeetCode 面试题 16.09. 运算
题目描述
题意分析
实现整数的减法、乘法和除法，只允许使用加法、比较与逻辑运算。可以写正负常数，但不能对变量直接使用减、乘、除或位运算；因此通常用移位实现的翻倍也要改成自身相加。
先实现相反数，减法就能写成加上相反数。乘法可以累加相同的数，除法可以累计取走了多少份除数，但逐份处理会随数值大小增长，所以用不断翻倍的块一次处理多份。
先把输入提升到 Java
long/ Goint64，再求绝对值。这样能够保存 32 位最小整数的正数绝对值，也能容纳翻倍过程的中间块，避免在int中先取绝对值就溢出。
解法：加法翻倍与贪心取块
核心思路
[!blue]
negate(value)把当前值向零移动，同时用result累计实际移动量。正数使用负步长，负数使用正步长，初始步长是对应的-1或1。每次成功移动后，value = 原值 + result都成立；当value变为零，result就必然是原值的相反数。为了少做移动，接受一次步长后就执行
delta += delta。若试探的next已越过零，则不修改value或result，只把步长恢复为正确方向的单位步长。下一次至少能向零移动一格，所以不会停住；恰好到零不算越过，应该接受并结束。减法直接使用这个辅助函数，计算a + negate(b)。乘法先记录两个输入是否异号，再对绝对值计算。令较大的数为
first，较小的数为待累加次数remaining。一次取块时，count从一开始，chunk从first开始；两者同步翻倍，始终表示“count份first的总量是chunk”。只要翻倍后的次数仍不超过remaining，就继续扩大。取走最大可用块后，把
chunk加入答案，并将remaining加上同步维护的negativeCount。它始终是count的相反数，所以不需要使用减号。整个过程中，已累加的答案加上剩余份数对应的总量，始终等于原始乘积；remaining归零时得到完整绝对值乘积。选最大二幂次数还让余下次数缩小到原来的一半以下。除法也先处理绝对值。
dividend保存剩余被除数，answer保存已经取走的除数份数。块中的value是count份divisor，negativeValue是该块的相反数；三个量同步翻倍，直到再翻倍就会超过dividend。随后把negativeValue加入剩余量，把count加入商，始终保持“原被除数绝对值 = 除数绝对值 × 当前商 + 剩余量”。这里的乘号只用于解释状态，代码通过同步加法维护它。当剩余量小于正的除数时，已经不能再取一份，当前商就是非负绝对值相除的整数部分。最后，乘除结果在输入异号时取相反数，除法由此得到向零截断的结果。零参与乘法或作为被除数时，循环自然不执行并返回零；题目保证输入有效，不会出现零除数。
解题步骤
minus(a, b)直接返回a + negate(b)。multiply(a, b)记录结果符号，把较小的绝对值作为剩余次数；不断找到能取的最大翻倍块并加入答案。divide(a, b)先取绝对值；每轮找到不超过dividend的最大divisor倍数，扣除该块并累加对应的商。- 乘除完成后按异号条件取反；除法在绝对值上取整数部分，再恢复符号，满足向零截断。
正块与负块从一开始就成对维护，翻倍时一起相加，取走块时直接使用负块即可。所有循环的退出条件都针对仍需处理的量：相反数处理到零，乘法处理到剩余次数为零，除法处理到余数小于除数。
代码实现
// 只使用加法和逻辑运算；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
}
复杂度分析
- 时间复杂度：用
w表示数值的二进制位数，最坏为 $O(w^2)$。乘除每轮取最大翻倍块后，剩余量至少减半，至多进行 $O(w)$ 轮，每轮寻找块又需 $O(w)$ 次翻倍；相反数在步长越界后重启翻倍，同样有这一上界。固定 32 位输入时，循环次数有常数上界。- 空间复杂度：$O(1)$，只使用若干数值变量。
关键点总结
[!green]
- 先把三种运算统一到“加法”和“相反数”，再用翻倍减少循环次数。
- 乘法中
chunk始终表示first * count；除法中value与count始终分别表示同一次翻倍后的数值和商贡献。- 乘除统一在非负绝对值上计算，最后一次处理符号，除法即可自然满足向零截断。
long/int64不是为了改变返回类型，而是为了安全表示 32 位最小整数的绝对值和中间块。
易错点总结
[!yellow]
- 用位运算模拟加法和乘除：即使结果正确，也违反本题明确的“不允许使用位运算”。
- 直接调用
Math.abs(a)：Math.abs(Integer.MIN_VALUE)仍是负数，后续循环和符号判断都会失效。- 逐次累加：循环次数会与乘数或商的数值大小成正比，翻倍分块才能把它缩减到与位数相关。
- 先带符号做除法：负数比较容易破坏“最大块不超过被除数”的不变量；应先取宽类型绝对值，最后恢复符号。
- 忘记整除语义：负商要向零截断，不能使用数学上的向下取整规则。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 29. 两数相除 | 中等 | 同样用翻倍块求整数商，但本题禁用位运算，翻倍必须写成自身相加。 |
| 371. 两整数之和 | 中等 | 原题禁加号而允许位运算，本题恰好相反，不能直接移植其加法实现。 |