Wednesday, March 19, 2014

Add two numbers without using arithmetic operators

Problem
Write a function Add() that returns sum of two integers. The function should not use any of the arithmetic operators (+, ++, –, -, .. etc).
Solution
We can get carry by &(and) operator and bit by ^ (xor) operator. We have already seen, how we can use bit-wise operators to replace arithmetic operators i.e. implement arithmetic operators using bitwise operators.


Method 1 - Iterative method
int Add(int x, int y)
{
    // Iterate till there is no carry 
    while (y != 0)
    {
        // carry now contains common set bits of x and y
        int carry = x & y; 
 
        // Sum of bits of x and y where at least one of the bits is not set
        x = x ^ y;
 
        // Carry is shifted by one so that adding it to x gives the required sum
        y = carry << 1;
    }
    return x;
}

Method 2 - Recursive approach
int Add(int x, int y)
{
    if (y == 0)
        return x;
    else
        return Add( x ^ y, (x & y) << 1);
}

Thanks.

0 comments:

Post a Comment