371. Sum of Two Integers
Given two integers a and b, return the sum of the two integers without using the operators + and -.
Example 1:
Input: a = 1, b = 2
Output: 3
Example 2:
Input: a = 2, b = 3
Output: 5
Constraints:
- -1000 <= a, b <= 1000
From: LeetCode
Link: 371. Sum of Two Integers
Solution:
Ideas:
1. XOR (^) for Sum Without Carry
- The XOR operation a ^ b computes the sum of a and b without considering the carry.
- For each bit position, XOR produces a 1 if the bits are different and a 0 if they are the same.
- This is equivalent to binary addition without carrying over (e.g., 1 ^ 1 is 0, similar to how 1 + 1 without carry is 0).
2. AND (&) and Shift for Carry
- The AND operation a & b computes the carry for each bit position.
- It produces a 1 only where both bits of a and b are 1.
- This carry needs to be added to the next higher bit, so we left-shift it by one position using << 1.
3. Iterating Until No Carry
- The process is repeated:
- Calculate the carry.
- Update a to be the sum without the carry.
- Update b to be the carry shifted left by one bit.
- This continues until there is no carry left (b becomes 0).
4. Masking to 32 Bits
- To handle potential overflow and to manage negative numbers in a 32-bit integer system, we mask the results to 32 bits using & 0xFFFFFFFF.
- This ensures that the intermediate results remain within the range of a 32-bit signed integer.
Code:
int getSum(int a, int b) {while (b != 0) {// Calculate carry and mask it to 32 bitsunsigned int carry = (unsigned int)(a & b) & 0xFFFFFFFF;// Sum without carry and mask it to 32 bitsa = (a ^ b) & 0xFFFFFFFF;// Shift carry to the left by 1 and mask it to 32 bitsb = (carry << 1) & 0xFFFFFFFF;}// Return the result as a signed 32-bit integerreturn a;
}