To perform addition without using + or ++ (or java.lang.Math class which internally uses +), we will have to perform addition using logical operators. To understand how addition works using logical operators, we will have to take it at binary level.
Lets try addition of 25 & 15 which should result in 40. We will first convert 25 & 15 into binary.
x = 25 = 00011001
y = 15 = 00001111
Manual addition of binary numbers
As we all know, manually addition of binary on paper is done using below rules.
Rules:
|
1 2 3 4 5 |
0 + 0 = 0, carry 0 0 + 1 = 1, carry 0 1 + 0 = 1, carry 0 1 + 1 = 0, carry 1 Special: 1 + 1 + 1 = (1 + 1) + 1 = (0, carry 1) + 1 = 1 , carry 1 |
Addition of 25 & 15 in binary: Add digits right to left using above rules, Add carry to left digit. Consider carry in addition of next left digit & use same rules again & so on.
|
1 2 3 4 5 6 7 |
0 0 1 1 1 1 1 0 <-- Carry --------------- 0 0 0 1 1 0 0 1 <-- 25 + 0 0 0 0 1 1 1 1 <-- 15 ---------------- 0 0 1 0 1 0 0 0 <-- 40 |
Do this programmatically
Now if you look at rules, you might find some similarity with the truth tables of some logical operations.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Rules: 0 + 0 = 0, carry 0 0 + 1 = 1, carry 0 1 + 0 = 1, carry 0 1 + 1 = 0, carry 1 This is similar to XOR truth table 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0 This is similar to AND truth table. 0 + 0 = carry 0 0 + 1 = carry 0 1 + 0 = carry 0 1 + 1 = carry 1 |
So basically XOR can tell us the addition of digit without carry & AND operator can tell us carry. There’s one slight catch here. Carry is supposed to be added in earlier/left digit, so basically once you figure out carry, you will have to shift left by 1 position to actually use carry in addition.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
0 0 0 1 1 0 0 1 <-- 25 + 0 0 0 0 1 1 1 1 <-- 15 ---------------- 0 0 0 1 0 1 1 0 <-- XOR (This is 'sum without carry') 0 0 0 0 1 0 0 1 <-- AND 0 0 0 1 0 0 1 0 <-- AND with left shift (This is 'carry') Now lets add 'sum without carry' & 'carry' using SAME method. --------------- 0 0 0 0 0 1 0 0 <-- XOR (This is 'sum without carry') 0 0 0 1 0 0 1 0 <-- AND 0 0 1 0 0 1 0 0 <-- AND with left shift (This is 'carry') Now lets add 'sum without carry' & 'carry' using SAME method. --------------- 0 0 1 0 0 0 0 0 <-- XOR (This is 'sum without carry') 0 0 0 0 0 1 0 0 <-- AND 0 0 0 0 1 0 0 0 <-- AND with left shift (This is 'carry') Now lets add 'sum without carry' & 'carry' using SAME method. --------------- 0 0 1 0 1 0 0 0 <-- XOR (This is 'sum without carry') 0 0 0 0 0 0 0 0 <-- AND 0 0 0 0 0 0 0 0 <-- AND with left shift (This is 'carry') --> Now here carry is all ZERO i.e. we have taken care of all carry. Hence, 'sum without carry' is our final sum |
0 0 1 0 1 0 0 0 = 40 (Which is correct sum of 25 + 15)
Java Code to achieve this
Below Java code achieves exact same steps shown above using Bitwise XOR (^), Bitwise AND (&) & Left Shift (<<) operator.
|
1 2 3 4 5 6 7 8 9 |
// Addition without + or ++ public static int add(int x, int y){ while(y != 0){ x = x ^ y; int carry = x & y; y = carry << 1; } return x; } |