[NC]258. 不用加减乘除做加法

🚩传送门：牛客题目
力扣题目

题目

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

示例:

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

解题思路：模拟

利用自增、自减运算符完成

public class Solution {
    public int Add(int num1,int num2) {
        // num1 正数
        if(num1>0)
            while(num1--!=0) num2++;
        else
            while(num1++!=0) num2--;
        return num2;
    }
}

解题思路：位运算

设两数字的二进制形式 ，其求和 ， 代表 的二进制第 位，则分为以下四种情况：

观察发现，无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）。

因此，无进位和 与进位 的计算公式如下：

🚩将 转化为 ：

循环求 和 ，直至进位 ；此时 ，返回 即可。

在计算机系统中，数值一律用 补码 来表示和存储。

补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法同时适用于正数和负数的加法 。

复杂度分析

时间复杂度：，最差情况下（例如 , 时），需循环 32 次

空间复杂度：, 使用常数大小的额外空间。

官方代码

class Solution {
    public int add(int a, int b) {
        // b 为进位,当进位为 0 时跳出
        while(b != 0) { 
            int tempb = (a & b) << 1;  // 临时进位
            a ^= b;                    // a 无进位和
            b = tempb;                 // b 新的进位
        }
        return a;
    }
}