371 两整数之和

• • 题目
  • • • 给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。
  • 题解思路
  • 魔鬼细节
  • • • 细节一
      • • 解析
      • 细节二
      • • 解析
      • 细节三
      • • 解析
      • 细节四
      • • 解析
  • 代码
  • • • 循环写法
      • 递归写法
  • 参考题解

题目

给你两个整数 a 和 b ，不使用 运算符 + 和 - ​​​​​​​，计算并返回两整数之和。

示例 1：

输入：a = 1, b = 2
输出：3
示例 2：

输入：a = 2, b = 3
输出：5

提示：

-1000 <= a, b <= 1000

来源：力扣（LeetCode）
链接: link.

题解思路

利用位运算来解决

魔鬼细节

细节一

a ^ b 表示无进位的求和部分
(a & b) << 1 表示只保留进位部分
所以可以用两部分加起来代替加法,但是不能用"+"实现,转用循环或递归,直到进位 (a & b) << 1 为 0 为止

解析

位运算: & | ^

二进制中: ① 1 + 1 = 10 用 (1 & 1) << 1 or (1 | 1) << 1;
② 1 + 0 = 1 用 1 | 0 or 1 ^ 0
③ 0 + 0 = 0 用 0 & 0 or 0 | 0 or 0 ^ 0

从这里发现 a | b 、 a ^ b 除了不能实现进位,其他都能实现,
但是 a | b 在①中会产生一个小尾巴 1,而 a ^ b 则不会,所以表示无进位的求和
又因为 0 & 上任何数都是 0,所以 (a & b) << 1 才能表示单纯地进位,而 (a | b) << 1 就不行

细节二

用循环或递归,直到进位 (a & b) << 1 为 0 为止

解析

(a & b) << 1 表示的是进位部分,那么随着不断拆分,这部分会变成 0 ,此时 a ^ b 部分就真正表示 a + b 的和了

细节三

可以使用无符号类型来防止溢出。

解析

在 C++ 的实现中，当我们赋给带符号类型一个超出它表示范围的值时，结果是 undefined；而当我们赋给无符号类型一个超出它表示范围的值时，结果是初始值对无符号类型表示数值总数取模的余数。

细节四

循环写法中,对于语句顺序要把握好

解析

如果先写 a = a ^ b,再写 temp = …,这样就把初始的 a 改变了

代码

循环写法

class Solution {
public:int getSum(int a, int b) {while (b) {unsigned int temp = (unsigned int)(a & b) << 1;a = a ^ b;b =temp;}return a;}
};

递归写法

class Solution {
public:int getSum(int a, int b) {if(!a) return b;int sum = a ^ b, carry = (unsigned int)(a & b) << 1;return getSum(carry, sum);    }
};

参考题解

官方循环参考
https://leetcode.cn/problems/sum-of-two-integers/solution/liang-zheng-shu-zhi-he-by-leetcode-solut-c1s3/

递归参考
https://leetcode.cn/problems/sum-of-two-integers/solution/liang-zheng-shu-zhi-he-wei-yun-suan-qing-7095/

思路参考
https://leetcode.cn/problems/sum-of-two-integers/solution/javashi-pin-jiang-jie-xi-lie-sum-of-two-integers-b/