Sum of Two Integers — Bit Addition
Sanjeev SharmaAdvertisement
Problem
Calculate a + b without using + or -.
Approach — Bit Addition
a ^ bgives sum without carry(a & b) << 1gives carry- Repeat until no carry
Time: O(1) (32-bit bounded) | Space: O(1)
Solutions
Python
class Solution:
def getSum(self, a: int, b: int) -> int:
mask=0xFFFFFFFF
while b&mask:
carry=((a&b)<<1)&mask
a=(a^b)&mask
b=carry
if b: a=~(a^b) # handle overflow for negative
return a if a<=0x7FFFFFFF else a-0x100000000
C++
class Solution {
public:
int getSum(int a, int b){
while(b){int carry=a&b;a^=b;b=(unsigned)carry<<1;}
return a;
}
};
Java
class Solution {
public int getSum(int a, int b){
while(b!=0){int c=a&b;a^=b;b=c<<1;}
return a;
}
}
Complexity
- Time: O(1) bounded by 32 bits | Space: O(1)
Advertisement
