Sum of Two Integers
Adding Two Integers Without Using + or -:
How do you add two integers without using the traditional + or - operators? This intriguing question challenges us to think beyond conventional arithmetic and explore the underlying mechanics of binary operations.
In this article, we’ll break down the problem and walk through an innovative solution.
Problem Statement
Given two integers, a and b, return their sum without using the + or – operators.
Constraints
- -1000 <= a, b <= 1000
Example 1
Input: a = 1, b = 1
Output: 2
Explanation:
The sum of 1 and 1 is 2, which can be computed without directly using the + operator.
Example 2
Input: a = 4, b = 7
Output: 11
Explanation:
The sum of 4 and 7 is 11.
Approach: Leveraging Bitwise Operations
To compute the sum of two integers without using + or -, we can take advantage of bitwise operators, specifically AND, XOR, and bit shifting. Here’s how:
Binary Arithmetic Breakdown
In binary, addition is performed digit by digit, just like in decimal arithmetic. The key steps are:
- Use the XOR operator (
^) to calculate the sum ofaandbwithout considering the carry. - Use the AND operator (
&) to calculate the carry bits, which indicate where carry-over is required. - Shift the carry bits left by one position (
<<) to align them with the next higher bit for the next addition. - Repeat steps 1-3 until there are no carry bits left.
There are mainly 4 approach to solve this problem –
- Brute Force
- Bit Manipulation
- Bit Manipulation (Optimal)
1. Brute Force
- Time complexity: O(1)
- Space complexity: O(1)
Python
C++
Java
JavaScript
Python
class Solution:
def getSum(self, a: int, b: int) -> int:
return a + b
C++
class Solution {
public:
int getSum(int a, int b) {
return a + b;
}
};
Java
public class Solution {
public int getSum(int a, int b) {
return a + b;
}
}JavaScript
class Solution {
/**
* @param {number} a
* @param {number} b
* @return {number}
*/
getSum(a, b) {
return a + b;
}
}
2. Bit Manipulation
Time & Space Complexity
- Time complexity: O(1)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
int getSum(int a, int b) {
int carry = 0, res = 0, mask = 0xFFFFFFFF;
for (int i = 0; i < 32; i++) {
int a_bit = (a >> i) & 1;
int b_bit = (b >> i) & 1;
int cur_bit = a_bit ^ b_bit ^ carry;
carry = (a_bit + b_bit + carry) >= 2 ? 1 : 0;
if (cur_bit) {
res |= (1 << i);
}
}
if (res > 0x7FFFFFFF) {
res = ~(res ^ mask);
}
return res;
}
};
Java
public class Solution {
public int getSum(int a, int b) {
int carry = 0, res = 0, mask = 0xFFFFFFFF;
for (int i = 0; i < 32; i++) {
int a_bit = (a >> i) & 1;
int b_bit = (b >> i) & 1;
int cur_bit = a_bit ^ b_bit ^ carry;
carry = (a_bit + b_bit + carry) >= 2 ? 1 : 0;
if (cur_bit != 0) {
res |= (1 << i);
}
}
if (res > 0x7FFFFFFF) {
res = ~(res ^ mask);
}
return res;
}
}
Python
class Solution:
def getSum(self, a: int, b: int) -> int:
carry = 0
res = 0
mask = 0xFFFFFFFF
for i in range(32):
a_bit = (a >> i) & 1
b_bit = (b >> i) & 1
cur_bit = a_bit ^ b_bit ^ carry
carry = (a_bit + b_bit + carry) >= 2
if cur_bit:
res |= (1 << i)
if res > 0x7FFFFFFF:
res = ~(res ^ mask)
return resJavaScript
class Solution {
/**
* @param {number} a
* @param {number} b
* @return {number}
*/
getSum(a, b) {
let carry = 0, res = 0, mask = 0xFFFFFFFF;
for (let i = 0; i < 32; i++) {
let a_bit = (a >> i) & 1;
let b_bit = (b >> i) & 1;
let cur_bit = a_bit ^ b_bit ^ carry;
carry = (a_bit + b_bit + carry) >= 2 ? 1 : 0;
if (cur_bit) {
res |= (1 << i);
}
}
if (res > 0x7FFFFFFF) {
res = ~(res ^ mask);
}
return res;
}
}3. Bitmanipulation (Optimal)
- Time complexity: O(1)
- Space complexity: O(1)
Code
C++
Java
Python
JavaScript
C++
pubclass Solution {
public:
int getSum(int a, int b) {
while (b != 0) {
int carry = (a & b) << 1;
a ^= b;
b = carry;
}
return a;
}
};
Java
public class Solution {
public int getSum(int a, int b) {
while (b != 0) {
int carry = (a & b) << 1;
a ^= b;
b = carry;
}
return a;
}
}
Python
class Solution:
def getSum(self, a: int, b: int) -> int:
mask = 0xFFFFFFFF
max_int = 0x7FFFFFFF
while b != 0:
carry = (a & b) << 1
a = (a ^ b) & mask
b = carry & mask
return a if a <= max_int else ~(a ^ mask)JavaScript
class Solution {
/**
* @param {number} a
* @param {number} b
* @return {number}
*/
getSum(a, b) {
while (b !== 0) {
let carry = (a & b) << 1;
a ^= b;
b = carry;
}
return a;
}
}
