剑指offer 48. 不用加减乘除做加法 & leetcode 剑指 Offer 65. 不用加减乘除做加法

48. 不用加减乘除做加法

题目描述

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

思路：

数字逻辑中全加器可以用一个异或门和一个与门实现，异或门计算本位，与门记录经过移位后的进位，
要考虑到进位可能不止一位，
如 7 + 7 = 14，而二进制位计算过程为：
111　　　　 111　　　　　　　     000    000　　　　　　　　　
^111　　　　&111       ^1110                            &1110　　　　　　　　
——　　       ———　　　　　　　                ————               ————　　　　　　　　
000　　　　   111　--> 移位之后 1110    1110 = 14                0000 --> 0000　　　　
需要循环两次，才能得到结

 1 public class Solution {
 2     public int Add(int num1,int num2) {
 3         // 数字逻辑中全加器可以用一个异或门和一个与门实现
 4         int carry = 0;    // 进位初识为0
 5         int result = 0;    // 本位结果
 6         do{
 7             result = num1 ^ num2;     // 异或门计算本位
 8             carry = (num1 & num2) << 1; // 与门结果经过移位后为进位
 9             num1 = result;    // 可能存在循环进位
10             num2 = carry;
11         }while(carry != 0);
12         
13         return result;
14     }
15 }

更加简洁的写法

 1 class Solution {
 2     public int add(int a, int b) {
 3         while(b != 0){
 4             int sum = a ^ b;        // 未带进位的和
 5             b = (a & b) << 1;     // 进位
 6             a = sum;
 7         }
 8         return a;
 9     }
10 }

leetcode运行时间为0ms, 空间为35.8MB

复杂度分析：

时间复杂度：最多移位32次，属于产量级，所以时间复杂度为O(1)

空间复杂度：O(1)