0371. Sum of Two Integers

题目信息

题号:

0371

难度:

Medium

主题:

有符号整数、算术和、运算符限制、位级语义

原题:

LeetCode 0371

重点:

返回两个整数的算术和、实现中不能使用 + 或 -、输入可以为负数或零

题目重述

给定两个整数 a 和 b,返回它们的算术和。实现过程中不能使用加法运算符 + 或减法运算符 -。

a 和 b 均位于 [-1000, 1000],结果能够由常见的 32 位有符号整数表示。输入可能同号、异号或包含零;题目只要求返回最终整数结果。

自建示例

正负数相加:

输入:a = 12,b = -5
输出:7
解释:两个整数的算术和为 7,虽然实现不能直接使用加减运算符。

两个负数相加:

输入:a = -8,b = -9
输出:-17
解释:结果仍按有符号整数语义计算,负号不代表可以忽略进位或符号位。

异或保留无进位结果,与运算生成进位

对两个二进制数,a ^ b 在每一位上给出不考虑进位的和;a & b 找出同时为 1 的位,左移一位后就是需要加到更高位的进位。先把 a、b 更新为“无进位和”和“进位”,再重复同样过程,直到没有进位。

把整数视为固定宽度的二进制补码时,异或和移位对负数同样成立;使用无符号临时变量进行左移,避免对有符号位移的实现细节产生依赖。

C++ 实现

class Solution {
public:
    int getSum(int a, int b) {
        unsigned int first = static_cast<unsigned int>(a);
        unsigned int second = static_cast<unsigned int>(b);
        while (second != 0) {
            unsigned int carry = (first & second) << 1;
            first ^= second;
            second = carry;
        }
        return static_cast<int>(first);
    }
};

代码分析

每轮都把至少一位进位向更高位移动,固定宽度整数下有限轮后进位消失;此时 first 就是完整补码和。实现正文没有使用 + 或 -,时间复杂度为 O(w),其中 w 是整数位宽,额外空间为 O(1)。