JZ65不用加減乘除做加法

描述

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

數據範圍：兩個數都滿足 -10 \le n \le 1000−10≤n≤1000
進階：空間複雜度 O(1)O(1)，時間複雜度 O(1)O(1)

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

思路：

由於題目禁止我們使用+，-，*，/運算符，我們需要通過位運算來實現加法。我們需要通過迴圈迭代兩個變數實現，一個變數指代進位，一個變數指代非進位。

位運算中兩數進行異或運算可以提供兩數加和後二進位非進位信息，位運算中的兩數進行與運算的結果可以提供兩數加和後的二進位進位信息。因此我們將兩數與運算的結果進行迴圈左移一位，併在下一輪迴圈中繼續將移位後的進位結果和非進位結果求和，重覆此過程，直到不再產生進位為止。

具體做法：
  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;

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

思路：

在遞歸中我們讓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;
    }
}