两整数之和
难度:
标签:
题目描述
给你两个整数 a 和 b ，不使用 运算符 + 和 - ，计算并返回两整数之和。
示例 1：
输入：a = 1, b = 2 输出：3
示例 2：
输入：a = 2, b = 3 输出：5
提示：
-1000 <= a, b <= 1000
代码结果
运行时间: 19 ms, 内存: 15.9 MB
/*
* 思路：
* 使用位操作实现两个整数的加法。
* 使用异或操作（^）计算不带进位的加法结果。
* 使用与操作（&）并左移一位（<<）计算进位。
* 循环上述步骤直到没有进位为止。
* 虽然Java Stream不适用于此类问题，但我们可以将核心逻辑包装在stream的操作中。
*/
import java.util.stream.IntStream;
public class Solution {
public int getSum(int a, int b) {
return IntStream.iterate(new int[]{a, b}, arr -> arr[1] != 0, arr -> new int[]{arr[0] ^ arr[1], (arr[0] & arr[1]) << 1})
.findFirst()
.get()[0];
}
}解释
方法:
这个题解使用位运算来计算两个整数的和，具体思路如下：
1. 使用掩码 mask1 对 a 和 b 取模，将它们限制在 32 位整数范围内。
2. 使用一个 while 循环计算 a 和 b 的和：
- 用 a&b 计算 a 和 b 的进位，并将结果左移一位（乘以 2），再对 mask1 取模。
- 用 a^b 计算 a 和 b 的无进位和，再对 mask1 取模。
- 将进位赋值给 b，无进位和赋值给 a。
- 循环直到进位 b 为 0。
3. 最后判断 a 的最高位是否为 1（即是否为负数），如果是则对 a 进行取反并减一的操作，否则直接返回 a。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在题解中使用了三个掩码mask1, mask2, mask3，每个掩码具体的作用和意义是什么？
▷🦆
为什么在计算进位时使用了左移操作并取模mask1？这样做的目的是什么？
▷🦆
题解中提到，如果a的最高位为1，则a为负数，需要进行取反和减一操作。这种操作是如何确保转换为正确的负数值的？
▷🦆
题解中的while循环是如何确保最终能够停止的？即，如何保证进位b最终会变为0？
▷相关问题
两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[7,0,8] 解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0] 输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零