Make delicious recipes!

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 class AddingWithBitwiseOps 
{

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


    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;
        
        return add (
            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:

Facebook comments:

Site Owner: Sachin Goyal