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

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

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

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

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

当前位置: 算法 > 剑指offer > 剑指offer 65. 不用加减乘除做加法
本文链接:https://www.mianshi.online/2814.html

题目描述

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

示例:

输入: 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完整版