leetcode
leetcode 2851 ~ 2900
不用加号的加法

不用加号的加法

难度:

标签:

题目描述

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 and b 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)

代码细节讲解

🦆
在不使用加号的情况下,为什么选择位运算(尤其是异或和与操作)来实现加法功能?
在进行二进制加法时,异或运算可以用来模拟不带进位的加法,因为它只在两个比特位不同的时候产生1(即0+1或1+0)。与运算则用来确定哪些位置会产生进位,因为只有两个比特位都为1时(即1+1),才会在该位置产生进位。这使得位运算特别适合模拟加法过程,因为它可以分开处理加法的两个主要部分:求和与进位。
🦆
你提到使用掩码来确保数字在32位整数范围内,能否详细解释这些掩码(MASK1, MASK2, MASK3)各自的作用和必要性?
这三个掩码用于处理32位整数的边界条件和符号。MASK1 (2**32) 用于确保数字在32位整数范围内,防止溢出。在Python中,整数可以超过标准的32位大小,使用MASK1进行模运算可以限制结果保持在32位内。MASK2 (2**31) 是32位整数的符号位,用于检测结果是否为负数(即最高位是否为1)。如果最高位为1,结果应被视为负数。MASK3 (2**31 -1) 是32位整数中最大的正整数,用于在负数处理中将符号位以外的部分转换回原本的负数表示方法。
🦆
在处理负数时,为何需要将最高位的1转换回原本的负数表示方法?具体是如何实现的?
在二进制中,负数通常使用补码形式表示。如果计算的结果是负数,最高位会是1。在32位整数中,这意味着需要将这个表示转换成标准的负数形式。具体操作是首先通过异或操作 (a ^ MASK2) 移除符号位,然后将结果与MASK3异或,最后取反。这样能将补码形式的负数转换为其正确的负数值。

相关问题