JZ65不用加減乘除做加法

描述

寫一個函數(shù)，求兩個整數(shù)之和，要求在函數(shù)體內(nèi)不得使用+、-、*、/四則運算符號。

數(shù)據(jù)范圍：兩個數(shù)都滿足 -10 \le n \le 1000?10≤n≤1000
進階：空間復(fù)雜度 O(1)O(1)，時間復(fù)雜度 O(1)O(1)

方法一：位運算非遞歸（推薦使用）

思路：

由于題目禁止我們使用+，-，*，/運算符，我們需要通過位運算來實現(xiàn)加法。我們需要通過循環(huán)迭代兩個變量實現(xiàn)，一個變量指代進位，一個變量指代非進位。

位運算中兩數(shù)進行異或運算可以提供兩數(shù)加和后二進制非進位信息，位運算中的兩數(shù)進行與運算的結(jié)果可以提供兩數(shù)加和后的二進制進位信息。因此我們將兩數(shù)與運算的結(jié)果進行循環(huán)左移一位，并在下一輪循環(huán)中繼續(xù)將移位后的進位結(jié)果和非進位結(jié)果求和，重復(fù)此過程，直到不再產(chǎn)生進位為止。

具體做法：
  step 1：兩數(shù)進行與運算可以產(chǎn)生進位的信息
  step 2：運算后執(zhí)行左移1位就是每輪需要進位的方案
  step 3：兩數(shù)進行異或運算可以產(chǎn)生非進位的加和結(jié)果
  step 4：將移位后的進位結(jié)果與非進位結(jié)果繼續(xù)重復(fù) step 1 - step 3 的步驟，直到不再產(chǎn)生進位為止

代碼

int add = num2;
        int sum = num1;

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

方法二：位運算遞歸（擴展思路）

思路：

在遞歸中我們讓num2承載進位信息，讓num1承載加和信息，進行遞歸。

具體做法：
  step 1：以num2承接是否有進位的工作，num1作為加和的結(jié)果
  step 2：首先判斷num2是否有進位
  step 3：如果有進位則遞歸調(diào)用函數(shù)，并將num1更新為或運算的結(jié)果，num2更新為與運算左移一位的結(jié)果
  step 4：如果無進位則返回num1，因為num1一直在記錄加和結(jié)果

代碼

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