不用加号的加法
难度:
标签:
题目描述
Write a function that adds two numbers. You should not use + or any arithmetic operators.
Example:
Input: a = 1, b = 1 Output: 2
Note:
a
andb
may be 0 or negative.- The result fits in 32-bit integer.
代码结果
运行时间: 23 ms, 内存: 16.0 MB
/*
* 思路:
* 使用Java Stream实现同样的位运算方法来求和。
* 主要区别在于,将逻辑封装在函数式接口中,通过流操作进行处理。
*/
import java.util.function.IntBinaryOperator;
import java.util.stream.Stream;
public class Solution {
public int getSum(int a, int b) {
IntBinaryOperator sumWithoutCarry = (x, y) -> x ^ y;
IntBinaryOperator carry = (x, y) -> (x & y) << 1;
while (b != 0) {
int carryResult = carry.applyAsInt(a, b);
a = sumWithoutCarry.applyAsInt(a, b);
b = carryResult;
}
return a;
}
}
解释
方法:
本题解利用位运算来实现加法。首先,通过异或操作 `a^b` 计算出不考虑进位的和,通过 `a&b` 获取需要进位的位置。将进位结果左移一位得到新的进位值。这个过程重复,直到没有新的进位产生(即进位值为0)。对于负数的处理,使用掩码将其转换为32位有符号整数。如果最高位为1表示结果为负数,需要将其转换回原本的负数表示方法。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
在不使用加号的情况下,为什么选择位运算(尤其是异或和与操作)来实现加法功能?
▷🦆
你提到使用掩码来确保数字在32位整数范围内,能否详细解释这些掩码(MASK1, MASK2, MASK3)各自的作用和必要性?
▷🦆
在处理负数时,为何需要将最高位的1转换回原本的负数表示方法?具体是如何实现的?
▷