微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 65. 不用加减乘除做加法

剑指offer 65. 不用加减乘除做加法

题目描述

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

输入: a = 1, b = 1
输出: 2

提示：

  • a, b 均可能是负数或 0
  • 结果不会溢出 32 位整数

题解

(位运算) O(logn)

  1. 首先我们可以将 num1 + num2 = A + B，A 是 num1 + num2 做不进位加法的结果，B 是 num1 + num2 产生的进位结果，两部分加起来就是 num1 + num2
  2. 不进位加法可以用异或 ^，计算进位可以用与 &，对每一位进行这两种操作
  3. 因为不能用加法，所以 A + B 可以用 whlie 循环代替 循环终止条件：由于每次计算进位的结果 carry 会左移 1 位，后面补 0，再计算新的进位做 & 运算时后面的 0 还是 0 不会出现 1，所以在不断的移位后 carry 必然会变成 0，循环可以结束 循环内部：每次 num1 和 num2 / carry 做不进位加法，计算新产生的进位（为什么会有新的进位，因为 sum 的结果和进位结果做不进位加法后可能还会出现新的进位），直到没有进位为止计算结束，num1 中存的就是 num1 + num2 的结果
  4. !注意：此做法只能做正数加法

时间复杂度

进位 carry 每次左移 1 位相当于除以 2，logn 次 carry 为 0，所以时间复杂度为 O(logn)

空间复杂度

O(1)

C++代码

class Solution {
public:
    int add(int a, int b) {
        while (b) {
            int sum = a ^ b;
            int carry = (unsigned int) (a & b) << 1;
            a = sum;
            b = carry;
        }
        return a;
    }
};

Java 代码

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;
    }
}

Python 代码

class Solution:
    def add(self, a: int, b: int) -> int:
        MASK = 0xFFFFFFFF  # 32 位掩码，用于处理溢出
        while b:
            # 1. 计算不考虑进位的相加结果
            sum = (a ^ b) & MASK
            # 2. 计算进位，注意要使用无符号右移操作
            carry = ((a & b) << 1) & MASK
            # 3. 更新 a 为相加结果，更新 b 为进位
            a, b = sum, carry

        # 处理溢出情况，如果结果超过了 32 位整数范围，则需要进行补码变换
        if a <= 0x7FFFFFFF:
            return a
        else:
            return ~(a ^ MASK)

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer