/**
*371. Sum of two integers
Binary bit based add and subtract
*/
See the code on github at: https://github.com/zcoderz/leetcode/blob/main/src/main/java/bitwise/BinaryBitBasedAdd.java
Observation: We can only use bit operations. Simplify the work to use only positive numbers and negate the final number if needed.
Add is simple. Do XOR and find carry, repeat until carry is 0.
Subtract is tricky. We XOR to merge the bits. We identify the carry bits by ~X & Y. ~X identifies bits which were off in X, when you and with Y, you get the borrow number. Since you had merged the Y bits that needed borrowing during XOR you need to left shift borrow by 1 bit.
Observe 8-4. The bits are 1000-0100. XOR returns 1100. Borrow becomes 1000. When you XOR 1100 and 1000 you get 0100 which is 4.
Observe 12-7. It works in 3 iterations until borrow is 0.
- Start with 12-7 (1100 – 0111)
- First iteration returns 11 – 6 (1011 -0110)
- Second iteration returns 13 – 8 (1101-1000)
- Third iteration returns 5-0 (0101-0)
- Notice how the borrow keeps shifting left until it is 0
Here is the code:
public int getSum(int a, int b) {
int x = Math.<em>abs</em>(a);
int y = Math.<em>abs</em>(b);
int sign = a >= 0 ? 1 : -1;
if (y > x) {
return getSum(b, a);
} else {
if (a * b > 0) {
//add
while (y != 0) {
int s = x ^ y; // add the xor bits (bits unique in each num)
int c = (x & y) << 1; //find the carry bits and shift them left by 1 to identify the carry
x = s;
y = c;
}
} else {
//subtract
while (y != 0) {
//this one is tricky , logic is :
// 1. that you run XOR. merge the unique bits.
// 2. you find the borrow bits and repeat the process. borrow is simply (~x & y) << 1
// 3. i,e think of 8-4 (1000 - 0100)
// 1st step you merge 8 & 4 to 1100 and you calculate borrow as: (~8&4)=0100, left shift to 1000
// 2nd iteration you work on 1100 & 1000. xor gives 0100. borrow comes out as 0 and you are done
// think of 12-7, steps would be 11-6 in first iteration, second 13-8 and last 5 with no borrow
// borrow is left shifting until it becomes 0
int s = x ^ y; // add the xor bits (bits unique in each num)
//find the borrow bit and shift them left by 1 to identify the borrow
//the off bits in x when & with y identify the bits where borrow is needed.
//since xor would merge these bits from y into x (above), we need to shift the ~x & y one left
//to identify the borrow number.
int c = ((~x) & y) << 1;
x = s;
y = c;
}
}
}
return sign * x;
}