LeetCode 面试题 17.01. 不用加号的加法

约 3 分钟
文章信息 3 个分类 2 个标签
分类
LeetCode 简单 程序员面试金典（第 6 版）
标签
数学 位运算

题目描述

✅ 面试题 17.01. 不用加号的加法

image-20260929010437068

题意分析

不使用加号或其他算术运算符，计算两个整数的和。输入可以为负数或零，题目保证结果不超出 32 位整数范围。可以直接在固定宽度的补码表示上处理每一位，无需分开模拟正数和负数。

解法：无进位和与进位分开计算

核心思路

[!blue]

一位二进制相加时，两位不同则本位为 1、没有进位；两位都是 1 则本位为 0、向高一位进 1。因此 a ^ b 恰好给出忽略进位的各位和，a & b 找出需要进位的位置，再左移一位得到 (a & b) << 1。

将这两个结果分别记为 sum、carry，它们合成的位模式与原来的和相同。令 a = sum、b = carry，就把原问题变成继续合并无进位结果与进位；新进位还可能引发连锁进位，因此需要重复计算，不能只做一轮。

每轮 carry 的有效位都来自旧 b 中为 1 的位，并至少向高位移动一位。在有限字宽内，进位最终会消失。此时 b = 0，所有进位都已合并到 a，直接返回 a。

负数同样使用补码位模式。中间状态可能越过有符号数范围，但固定字宽的位运算仍保留对应低位；题目保证最终结果可表示，所以进位消失后的位模式就是正确的有符号结果。

解题步骤

  1. 当 b != 0 时，用本轮原来的 a、b 计算 sum = a ^ b 和 carry = (a & b) << 1。
  2. 两个结果都算完后，再分别赋回 a、b。
  3. 当进位为零时结束并返回 a。若最初 b = 0，无需循环就可返回。

代码实现

class Solution {
    public int add(int a, int b) {
        while (b != 0) {
            int sum = a ^ b;
            int carry = (a & b) << 1;

            a = sum;
            b = carry;
        }

        return a;
    }
}

func add(a int, b int) int {
    for b != 0 {
        sum := a ^ b
        carry := (a & b) << 1
        a = sum
        b = carry
    }
    return a
}

复杂度分析

  • 时间复杂度：$O(W)$，W 为实际整数位宽，进位至多向高位传播 W 次。Java int 为 32 位，Go 原生 int 随平台为 32 或 64 位；固定机器字长下可记为 $O(1)$。
  • 空间复杂度：$O(1)$。只保存固定数量的整数状态。

关键点总结

[!green]

  • 异或保留无进位的和，与运算后左移产生需要继续合并的进位。
  • 每轮都保持目标和的位模式不变，只把未解决的进位推向更高位。
  • 结束条件是进位为零，而不是无进位结果为零。

易错点总结

[!yellow]

  • 先覆盖 a 再计算进位，会让 carry 使用本轮新值，破坏同一对输入的拆分关系。
  • 进位必须左移一位，直接使用 a & b 仍停留在原来的位上。
  • 不能因输入为负数就改用绝对值或额外加减，补码位运算本身已覆盖负数。
  • Go 使用原生 int 时不要把循环上界一概写成 32 位，应以实际机器字宽说明复杂度。

相似题目

题目 难度 关联与区别
67. 二进制求和 简单 同样逐位处理和与进位，原题是任意长度二进制字符串，本题直接操作机器整数位。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/24068630
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！