0371. Sum of Two Integers ========================= 题目信息 -------- :题号: 0371 :难度: Medium :主题: 有符号整数、算术和、运算符限制、位级语义 :原题: `LeetCode 0371 `_ :重点: 返回两个整数的算术和、实现中不能使用 ``+`` 或 ``-``、输入可以为负数或零 题目重述 -------- 给定两个整数 ``a`` 和 ``b``,返回它们的算术和。实现过程中不能使用加法运算符 ``+`` 或减法运算符 ``-``。 ``a`` 和 ``b`` 均位于 ``[-1000, 1000]``,结果能够由常见的 32 位有符号整数表示。输入可能同号、异号或包含零;题目只要求返回最终整数结果。 自建示例 -------- 正负数相加: .. code-block:: text 输入:a = 12,b = -5 输出:7 解释:两个整数的算术和为 7,虽然实现不能直接使用加减运算符。 两个负数相加: .. code-block:: text 输入:a = -8,b = -9 输出:-17 解释:结果仍按有符号整数语义计算,负号不代表可以忽略进位或符号位。 异或保留无进位结果,与运算生成进位 ------------------------------------ 对两个二进制数,``a ^ b`` 在每一位上给出不考虑进位的和;``a & b`` 找出同时为 1 的位,左移一位后就是需要加到更高位的进位。先把 ``a``、``b`` 更新为“无进位和”和“进位”,再重复同样过程,直到没有进位。 把整数视为固定宽度的二进制补码时,异或和移位对负数同样成立;使用无符号临时变量进行左移,避免对有符号位移的实现细节产生依赖。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int getSum(int a, int b) { unsigned int first = static_cast(a); unsigned int second = static_cast(b); while (second != 0) { unsigned int carry = (first & second) << 1; first ^= second; second = carry; } return static_cast(first); } }; 代码分析 -------- 每轮都把至少一位进位向更高位移动,固定宽度整数下有限轮后进位消失;此时 ``first`` 就是完整补码和。实现正文没有使用 ``+`` 或 ``-``,时间复杂度为 ``O(w)``,其中 ``w`` 是整数位宽,额外空间为 ``O(1)``。