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;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/533482.html
標籤：Java