We are very used to using +
and -
to do addition and subtraction. Have you considered how to use bitwise operations to do these? In this article, let's explore some of them.
Addition
First, let's see how to do simple addition in 2 base in normal way.
3 + 5
11
101
----
1000 <= answer
We do it from right to left on every digits. Note that if current sum is bigger than the base, then a carry need to be stored to be used in next digit addition.
Now let's see how to do it using only bitwise operation.
First, calculate answer without considering carry.
11
101
----
110 <= answer without carry
This operation can be done by a ^ b
.
Then calculate carry(without considering previous carry).
11
101
----
001 <= carry
This operation can be done by (a & b) << 1
.
Do this process again, until carry is 0, then we can get the final result.
Let's see this process in code.
function add(a: number, b: number) {
while (b > 0) {
const answer = a ^ b;
const carry = (a & b) << 1;
a = answer;
b = carry;
}
return a;
}
console.log(add(3, 5));
Subtraction
Same as addition, let's first see how to do subtraction in 2 base.
5 - 3
101
- 11
------
010 <= answer
Remember that, if current digit is not enough to subtrack, then a borrow needed to be made from next digit.
Now let's see how to do is in bitwise operations.
First, calculate answer without considering borrow.
101
- 11
------
110 <= answer without considering borrow
This operation can be done by a ^ b
.
Then calculate borrow without considering previous borrow.
101
- 11
------
010 <= borrow
This operation can be done by ((~a) & b) << 1
.
Then let answer subtrack borrow again, until borrow is 0, then we can get final result.
Let's see this process in code.
function subtrack(a: number, b: number) {
while(b > 0) {
const answer = a ^ b;
const borrow = ((~a) & b) << 1;
a = answer;
b = borrow;
}
return a;
}
console.log(subtrack(105, 3))
Sum of Two Integers
Now we can use this leetcode problem to test the above code.
function getSum(a: number, b: number): number {
let [x, y] = [Math.abs(a), Math.abs(b)];
if (x < y) {
// abs big one first
return getSum(b, a);
}
// consider negative
const sign = a > 0 ? 1 : -1;
if (a * b >= 0) {
return add(x, y) * sign;
} else {
return subtrack(x, y) * sign;
}
};
console.log(getSum(-14, 16))