Dare2Solve
The task is to calculate the sum of two integers a
and b
without using the +
or -
operators. The solution leverages bitwise operations to achieve this. This is often useful in low-level programming and systems where addition needs to be optimized.
The idea behind the solution is that the bitwise XOR operation (^
) can be used to add numbers without carrying, while the bitwise AND operation (&
) followed by a left shift (<<
) can be used to calculate the carry. By repeatedly applying these operations, we can compute the sum of the two numbers as though we were manually adding them, bit by bit.
^
) gives us the sum of bits where there is no carry.&
) followed by a left shift gives us the carry.a
will hold the final result.^
) to calculate the sum without carry. This is equivalent to adding two numbers as if carry does not exist.&
) followed by a left shift (<<
) to calculate the carry.b == 0
).a
.O(1) in the best case when there are no carry bits, but in general, it is O(log(max(a, b))) since each step reduces the number of bits involved in the calculation.
O(1), as we are using a constant amount of extra space.
class Solution {
public:
int getSum(int a, int b) {
while (b != 0) {
int tmp = (a & b) << 1; // carry calculation
a = a ^ b; // sum without carry
b = tmp; // carry shifted left
}
return a;
}
};
class Solution:
def getSum(self, a: int, b: int) -> int:
MAX = 0x7FFFFFFF # Maximum positive int (32-bit)
MASK = 0xFFFFFFFF # Mask to get last 32 bits
while b != 0:
tmp = (a & b) << 1 # carry calculation
a = (a ^ b) & MASK # sum without carry (limit to 32 bits)
b = tmp & MASK # carry shifted left (limit to 32 bits)
# If a is greater than MAX, it's a negative number in 32-bit representation
return a if a <= MAX else ~(a ^ MASK)
class Solution {
public int getSum(int a, int b) {
while (b != 0) {
int tmp = (a & b) << 1; // carry calculation
a = a ^ b; // sum without carry
b = tmp; // carry shifted left
}
return a;
}
}
var getSum = function(a, b) {
while(b !=0)
{
let tmp = (a& b) <<1;
a = a^b;
b = tmp;
}
return a;
};