Monday, July 15, 2013

Multiplication not with multiplication operator


Problem 1 Efficient way to multiply with 7

 Clue : Use bitwise operator
 << by one bit is multiply by 2
<< by 3 bits is multiply by 8.

Then substract the original number.

int multiplyBySeven(unsigned int n)
{
    /* Note the inner bracket here. This is needed
       because precedence of '-' operator is higher
       than '<<' */
    return ((n<<3) - n);
}

Note: Works only for positive integers only. Same concept can be used for fast multiplication by 9 or other numbers.

Problem 2 Add two numbers without using arithmetic operators 

Sum of two bits can be obtained by performing XOR (^) of the two bits.
Carry bit can be obtained by performing AND (&) of two bits.

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;
}

Recursive Solution

int Add(int x, int y)
{
    if (y == 0)
        return x;
    else
        return Add( x ^ y, (x & y) << 1);
}

No comments:

Post a Comment