面试题65：不用加减乘除做加法

用异或生成不带进位的和、与运算左移生成进位，在固定宽度无符号位模式上迭代到进位为零。

学习目标

  • 能...
  • 能...
  • 能...
分步1 / 3

核心思路

理解问题的核心算法。

AddTwoNumbers核心算法示意图
算法核心步骤可视化

从“1 1 为什么要拆成两个”开始

十进制把“当前位写什么”和“向带多少”分开处理，二进制也一样。单个位0加1的本位是1、没有；1加1的本位是0、向左一位进1。只要能分别得到这两个部分，就能把多位加法改写成重复的位运算。

本题是“不用加减乘除做加法”，输入是两个普通整数，不是表示的十进制。旧页讲链表逐位加法、长度不等和尾进位，属于另一道题，与作者面试题65及其七组正负整数测试无关。

对单个位a与b，异或给出不考虑进位的本位结果，与运算标记两位同时为1的位置：

s=a⊕b,c=a∧bs=a\oplus b, \qquad c=a\land b

先预测5和7的第一轮：0101异或0111得到0010，按位与得到0101，左移一位后进位是1010。0010还不是答案，因为它与1010仍可能在相同位上再次产生进位。

异或得到不带进位的和

异或只在两个输入位不同的时候输出1，正好对应0加1或1加0的本位结果；两个位都是1时输出0，把需要进位的部分暂时留给另一个变量。因此可以把它称为。

原章概念“异或得到不带进位的和”不是类比，而是四行真值表的逐项等价。它一次同时处理机器字的全部位。

与运算后左移得到进位

按位与只在两个输入位都为1时输出1，这些位置各自产生一个二进制进位。进位属于左边更高一位，所以整体左移一位，得到。

x+y=(x⊕y)+((x∧y)≪1)x+y = (x\oplus y) + \bigl((x\land y)\ll1\bigr)

这个等式用于证明，受限函数体里并不写加号。它说明原来两个加数可以替换成“异或和”与“左移进位”，两者总和保持不变。

这就是“与运算后左移得到进位”。左移不能省略；不左移的与结果仍停在产生冲突的原位，相当于把1加1误记为当前位1。

为什么必须重复到进位归零

新进位可能与异或和中的1再次重叠。例如5加7第一轮得到0010与1010，两者在第二位仍同时为1，还会产生新的0100进位。每轮都把当前两个位向量重新拆成异或和与进位，直到第二个向量为0。

作者用do-while，因此即使第二个输入一开始为0，也会执行一次异或与按位与，再发现进位为0。改用普通while从进位非0时进入也能得到相同答案，只是零输入路径少执行一轮。

原章的“直到进位为0”给出终止条件。此时第二个加数为0，第一位向量就是最终和。

xt+1=xt⊕yt,yt+1=(xt∧yt)≪1,xt+yt≡x0+y0(mod2W)x_{t+1}=x_t\oplus y_t, \qquad y_{t+1}=(x_t\land y_t)\ll1, \qquad x_t+y_t\equiv x_0+y_0\pmod{2^W}

这里W是机器字位宽。每轮进位的最低有效1至少向左移动一位；到达最高位后再左移就被固定宽度丢弃，所以最多W轮后进位为0。

忠实还原作者循环

作者把两个int分别作为暂存和与进位，循环体不含四则运算符：

int Add(int num1, int num2) {
    int sum;
    int carry;
 
    do {
        sum = num1 ^ num2;
        carry = (num1 & num2) << 1;
 
        num1 = sum;
        num2 = carry;
    } while (num2 != 0);
 
    return num1;
}

时间可写为O(W)，额外空间O(1)；对固定32位int，W是常数，渐进上也常称O(1)。实际轮数取决于进位链长度，1加2只需一轮，而低位连续为1会让进位逐位传播。

这段源码在常见编译器与二进制补码机器上能通过作者负数测试，但标准C++层面存在风险：num1与num2是有符号int，按位与结果也为有符号int；对负值左移，或把正值左移到不可表示的符号位，行为未定义。

负数为何仍能用同一位循环

在固定宽度中，正负数都只是W位模式。XOR、AND和左移不需要识别符号，只实现模2的W次方加法；若真实数学和位于有符号范围内，最终位模式解释回有符号数就是正确结果。

例如32位的-1是全1，与2相加时进位会沿高位传播，最终得到00000001。-2与-8得到FFFFFFF6，按补码解释为-10。作者七组测试都没有让数学和超出int范围。

若真实和超过有符号最大值或小于最小值，普通C++有符号加法本来就没有定义；无符号位循环则会给出模2的W次方回绕结果。接口必须明确要拒绝溢出、返回更宽结果，还是接受模加法，不能混为一谈。

现代固定32位实现

把核心函数定义为uint32_t上的，所有位移都有定义。需要有符号输入输出时，再用bit_cast保留同一32位对象表示；这要求平台提供int32_t并采用预期的补码表示。

#include <bit>
#include <cstdint>
#include <limits>
 
std::uint32_t addModulo32(
    std::uint32_t left,
    std::uint32_t right) {
    while (right != 0U) {
        const std::uint32_t sum =
            left ^ right;
        const std::uint32_t carry =
            (left & right) << 1U;
        left = sum;
        right = carry;
    }
    return left;
}
 
std::int32_t addInt32(
    std::int32_t left,
    std::int32_t right) {
    const auto leftBits =
        std::bit_cast<std::uint32_t>(left);
    const auto rightBits =
        std::bit_cast<std::uint32_t>(right);
    const auto resultBits =
        addModulo32(leftBits, rightBits);
    return std::bit_cast<std::int32_t>(
        resultBits);
}

若业务只接受数学和仍处于int32范围的输入，应在外层用更宽类型检测溢出；检测代码可以使用普通算术，因为题目限制的是核心Add函数体。若连验证也禁止加减，可用符号位规则检测：两个同号输入得到异号结果时发生有符号溢出。

固定宽度是契约的一部分。把代码从32位int直接复制到64位类型，最大循环轮数和溢出边界都会改变。

循环不变式与终止证明

每轮开始时，left与right的模和等于原输入模和。XOR和左移AND只是把同一列的本位与进位重新分组，所以更新后不变量仍成立。循环结束时right为0，不变量化为left等于原和的位模式。

设right最低1位的位置为p。left与right的按位与只可能保留right已有的1，再左移使最低可能位置至少成为p加1；若没有公共1则carry直接为0。因此非零carry的最低1位严格向高位移动，有限W位内必然终止。

yt≠0⟹lsb⁡(yt+1)>lsb⁡(yt)oryt+1=0y_t\ne0 \quad\Longrightarrow\quad \operatorname{lsb}(y_{t+1}) \gt \operatorname{lsb}(y_t) \quad\text{or}\quad y_{t+1}=0

这个证明比“看起来进位会消失”更强，也解释了最坏W轮上界。最高位进位被无符号左移按模丢弃，正是模加法的一部分。

最坏进位链怎样形成

当一个数的低位连续为1、另一个数只在最低位为1时，进位会一轮只向左推进一位。例如32位无符号的0x7FFFFFFF与1相加，第一轮把最低位冲突变成进位，之后它依次穿过其余30个连续1，最终得到0x80000000。循环轮数接近机器字宽度，而不是由十进制数值大小决定。

0xFFFFFFFF与1更能展示模语义：进位一路穿过全部32位，最高位再左移后被截掉，结果为0。对uint32_t这是定义明确的回绕；若把同一位模式解释成有符号-1再与1相加，数学结果0仍可表示，所以也应得到0。

相反，0x7FFFFFFF与1的位结果0x80000000在int32_t中解释为最小负数，但真实有符号数学和超过最大值。核心位循环没有失败，它正确完成了模加法；错误在于调用方若把回绕结果宣称为未溢出的有符号和。测试必须按接口分别断言“模结果”或“溢出错误”，不能只比较同一串比特。

七组官方测试覆盖什么

作者依次测试1与2、111与899、-1与2、1与-2、3与0、0与-4、-2与-8。它们覆盖无长进位、多位连续进位、两个跨符号方向、零操作数和两个负数。

111加899得到1010能检查多轮进位；3加0验证do-while至少执行一次仍保持原值；负数用例则暴露有符号左移的可移植性问题。

还应增加最高位附近测试：无符号0xFFFFFFFF与1应模回0；有符号最大值与0保持不变；若接口拒绝有符号溢出，则最大值加1必须走错误通道，而不是把最小值当作正常数学和。

#include <cassert>
#include <cstdint>
#include <limits>
 
void testBitAddition() {
    assert(addInt32(1, 2) == 3);
    assert(addInt32(111, 899) == 1010);
    assert(addInt32(-1, 2) == 1);
    assert(addInt32(1, -2) == -1);
    assert(addInt32(3, 0) == 3);
    assert(addInt32(0, -4) == -4);
    assert(addInt32(-2, -8) == -10);
 
    assert(addModulo32(
        UINT32_C(0xFFFFFFFF), 1U) == 0U);
    assert(addModulo32(0U, 0U) == 0U);
}

随机对拍应在uint32_t上与标准无符号加法比较，因为两者都定义为模2的32次方；有符号对拍只选择数学和不溢出的输入，或先明确采用回绕契约。

本章练习

（）

练习

问题 1： 请说明...

问题 2： 请说明...

问题 3： 请说明...

概念说明

本章核心概念包括：直到进位为0。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

  1. 不用加减乘除做加法的输入是两个整数，不是十进制链表。
  2. 异或得到不带进位的和，与运算后左移得到进位。
  3. 新的暂存和与进位继续执行同样拆分，直到进位为0。
  4. 循环保持两个位向量的模和不变，最多经过机器字位宽轮。
  5. 作者signed int版本能通过常见补码机器测试，但负数或符号位左移不具标准可移植性。
  6. 现代核心应在uint32_t等无符号固定宽度上运行，再明确有符号解释。
  7. 数学和溢出与模回绕是两种不同接口契约。
  8. 作者七组测试覆盖正负和零，但还需补最高位、回绕及溢出错误通道。

名词解释

复习本章（5 题）

讨论

评论区加载中…