每日算法之不用加减乘除做加法

描述

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

数据范围：两个数都满足 -10 \le n \le 1000−10≤n≤1000
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(1)O(1)

相关问答

Q1: 方法一：位运算非递归（推荐使用）

思路：

由于题目禁止我们使用+，-，*，/运算符，我们需要通过位运算来实现加法。我们需要通过循环迭代两个变量实现，一个变量指代进位，一个变量指代非进位。

位运算中两数进行异或运算可以提供两数加和后二进制非进位信息，位运算中的两数进行与运算的结果可以提供两数加和后的二进制进位信息。因此我们将两数与运算的结果进行循环左移一位，并在下一轮循环中继续将移位后的进位结果和非进位结果求和，重复此过程，直到不再产生进位为止。

具体做法：
  step 1：两数进行与运算可以产生进位的信息
  step 2：运算后执行左移1位就是每轮需要进位的方案
  step 3：两数进行异或运算可以产生非进位的加和结果
  step 4：将移位后的进位结果与非进位结果继续重复 step 1 - step 3 的步骤，直到不再产生进位为止

代码

int add = num2;
        int sum = num1;

        while (add != 0) {
            int temp = sum ^ add;
            add = (sum & add) << 1;
            sum = temp;
        }
        return sum;

Q2: 方法二：位运算递归（扩展思路）

思路：

在递归中我们让num2承载进位信息，让num1承载加和信息，进行递归。

具体做法：
  step 1：以num2承接是否有进位的工作，num1作为加和的结果
  step 2：首先判断num2是否有进位
  step 3：如果有进位则递归调用函数，并将num1更新为或运算的结果，num2更新为与运算左移一位的结果
  step 4：如果无进位则返回num1，因为num1一直在记录加和结果

代码

package esay.JZ65不用加减乘除做加法;

public class Solution {
    public int Add(int num1,int num2) {
        //1、方法1
        /*int add = num2;
        int sum = num1;

        while (add != 0) {
            int temp = sum ^ add;
            add = (sum & add) << 1;
            sum = temp;
        }
        return sum;*/
        //2、方法2
        return num2 != 0 ? Add(num1 ^ num2, (num1 & num2) << 1) : num1;
    }
}