Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Find sum of two numbers using only bitwise operators

Problem: Add two positive numbers without using + or ++

Solution:
If bits in both numbers were at different places, then sum is given just by (a | b)

If some bits are common in the two numbers, then ORing those will give back those same
bits where as a sum operation would have demanded a carry for each such OR between sum bits.

These means that bits common in both the numbers need to be handled specially.
Bits common in two numbers are given by (a & b)

Truth table comparison
A B A + B A | B A ^ B
0 0 0 0 0
0 1 1 1 1
1 0 1 1 1
1 1 10 1 0

So A+B = A^B except for last case, where its equal to (A|B << 1) || (A^B)

We get the uncommon bits using XOR and common bits using AND

Since result of adding common bits is same as multiplying by 2,
(Example: 01001 + 01001 = 10010),
we just shift the common bits by 1 and add them to uncommon bits recursively.
```
{

public static void main(String[] args)
{
int i = (int)(Math.random()*16);
int j = (int)(Math.random()*16);
}

static int add(int i, int j)
{
// Debug code
printBinary(i);
printBinary(j);
System.out.println();

// Actual algorithm
int uncommonBitsFromBoth = i ^ j;
int commonBitsFromBoth   = i & j;

if (commonBitsFromBoth == 0)
return uncommonBitsFromBoth;

uncommonBitsFromBoth,
commonBitsFromBoth << 1
);
}

static void printBinary(int num)
{
int n = num;
String s = "";
for (int i=0; i<8;i++)
{
s = (n&1) + s;
n = n >gt;>gt; 1;
}
System.out.println(num + " = " + s);
}
}

```
Examples:
```
6 = 00000110
2 = 00000010

4 = 00000100
4 = 00000100

0 = 00000000
8 = 00001000

Sum = 8

12 = 00001100
12 = 00001100

0 = 00000000
24 = 00011000

24

14 = 00001110
3 = 00000011

13 = 00001101
4 = 00000100

9 = 00001001
8 = 00001000

1 = 00000001
16 = 00010000

17

```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: