题解 | 另类加法

class UnusualAdd {
public:
    int addAB(int A, int B) {
        // write code here
        if(B == 0)
        return A;
        return (addAB(A^B,(A&B)<<1 ));
    }
};

解题思路全解析

这段代码是用递归 + 位运算模拟二进制加法的经典实现，核心是复刻计算机底层的加法逻辑（无进位相加 + 进位处理），全程不使用算术运算符（+/-等），完全符合“非常规加法”的题目要求。以下分4层拆解思路：

一、核心原理：二进制加法的本质

计算机做加法时，二进制层面只分两步，这也是代码的核心逻辑根基：

算法核心逻辑：

把“无进位和”和“进位值”重新作为新的两个数继续相加，直到进位值为0（没有需要处理的进位），此时的“无进位和”就是最终结果。

二、递归逻辑拆解（代码逐行解读）

class UnusualAdd {
public:
    int addAB(int A, int B) {
        // 终止条件：进位B为0，说明所有进位处理完毕，当前A就是最终和
        if(B == 0)
            return A;
        // 递归调用：新的加数是“无进位和”和“进位值”，继续相加
        return (addAB(A^B,(A&B)<<1 ));
    }
};

1. 终止条件：if(B == 0) return A

• B 的含义：递归过程中，B 始终代表“当前需要处理的进位值”；
• 当 B=0 时，说明没有任何进位需要处理了，此时的 A 是“所有位无进位相加 + 所有进位处理完成”的最终结果，直接返回即可。

2. 递归调用：addAB(A^B, (A&B)<<1)

递归的核心是“更新两个加数”，让加法持续进行直到无进位：

• 第一个参数 A^B：把本轮“无进位相加的结果”作为下一轮的新 A；
• 第二个参数 (A&B)<<1：把本轮“计算出的进位值”作为下一轮的新 B；
• 每一轮递归都是在“处理上一轮的进位”，直到进位为0。

三、具体例子验证（直观理解递归过程）

以 A=3（二进制 11） + B=1（二进制 01） 为例，逐轮拆解递归步骤：

最终结果 4（3+1=4），完全正确。

四、关键细节（新手避坑）

1. 递归的本质是“循环处理进位”： 递归没有新增逻辑，只是把“重复计算无进位和 + 进位”的过程用递归代替了循环，终止条件就是“无进位可处理”。
2. 补码的自动处理： C++ 中 int 是补码存储，位运算会自动处理负数加法（比如 A=-1 + B=2），无需额外判断符号位，递归逻辑对正负值都生效。
3. 左移1位的必要性： 比如 A=1（01） + B=1（01），A&B=01 表示第0位有进位，左移1位后变成 10（2），代表“进位要加到第1位”，这是进位的核心规则。

核心思路总结

1. 底层逻辑：用位运算复刻二进制加法的两步法（无进位相加 ^ + 进位计算 &<<1）；
2. 递归设计：以“进位值B”为终止条件，每轮递归更新“无进位和”和“进位值”，直到无进位；
3. 效率特点：时间复杂度 O(log n)（n为数值大小，进位最多左移log₂(n)次），空间复杂度 O(log n)（递归调用栈深度），是“无算术运算符加法”的最优解法之一。

这个思路的核心是“跳出十进制思维，回归二进制加法本质”，也是面试中考察位运算的高频考点。