Problem
Given two integersa and b, return their sum without using the + and - operators.
We can solve this problem using bit manipulation. The key idea is to use
^ for addition without carry and & to determine the carry.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
a = 5
b = 3Output
8Solution
The XOR operator^ adds two bits without considering the carry.
For example:
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 01, XOR produces 0, but a carry needs to be generated. We can find these carry bits using the AND operator &.
1 & 1 = 1
1 & 0 = 0
0 & 1 = 0
0 & 0 = 0carry = (a & b) << 1class Solution {
public int getSum(int a, int b) {
while (b != 0) {
// Calculate the carry.
int carry = (a & b) << 1;
// Add without considering the carry.
a = a ^ b;
// Process the carry in the next iteration.
b = carry;
}
return a;
}
}a = 5 and b = 3:
a = 0101
b = 0011
a ^ b = 0110
(a & b) << 1 = 0010
a = 0110
b = 0010
a ^ b = 0100
(a & b) << 1 = 0100
a = 0100
b = 0100
a ^ b = 0000
(a & b) << 1 = 1000
a = 0000
b = 1000
a ^ b = 1000
carry = 0000
Result = 1000 = 8Complexity
The algorithm processes the fixed-size integer bit by bit. For a 32-bit integer, the number of iterations is bounded by a constant, resulting inO(1) time complexity.
Only a constant number of variables is used, resulting in
O(1) space complexity.
