Trying
Trying

Reputation: 14278

Sum of two numbers with bitwise operator

I am pasting the code to find the sum of two numbers with bitwise operator. Please suggest if it can be optimized. Thanks...

public static int getSum(int p, int q)
{
int carry=0, result =0;
for(int i=0; i<32; i++)
{
    int n1 = (p & (1<<(i)))>>(i); //find the nth bit of p
    int n2 = (q & (1<<(i)))>>(i); //find the nth bit of q

    int s = n1 ^ n2 ^ carry; //sum of bits
    carry = (carry==0) ? (n1&n2): (n1 | n2); //calculate the carry for next step
    result = result | (s<<(i)); //calculate resultant bit
}

return result;
}

Upvotes: 6

Views: 21372

Answers (3)

Joop Eggen
Joop Eggen

Reputation: 109557

Think in entire bits:

public static int getSum(int p, int q)
{
    int result = p ^ q; // + without carry 0+0=0, 0+1=1+0=1, 1+1=0
    int carry = (p & q) << 1; // 1+1=2
    if (carry != 0) {
        return getSum(result, carry);
    }
    return result;
}

This recursion ends, as the carry has consecutively more bits 0 at the right (at most 32 iterations).

One can easily write it as a loop with p = result; q = carry;.

Another feature in algorithmic exploration is not going too far in differentiating cases. Above you could also take the condition: if ((result & carry) != 0).

Upvotes: 28

Rakesh Chaudhari
Rakesh Chaudhari

Reputation: 3500

I think below soln is easy to understand & simple,

public static void sumOfTwoNumberUsingBinaryOperation(int a,int b)
{
    int c = a&b;
    int r = a|b;
    while(c!=0)
    {
        r =r <<1;
        c = c >>1;      
    }
    System.out.println("Result:\t" + r);    
}

Upvotes: 0

Adam Matan
Adam Matan

Reputation: 136211

I think that the optimizations should be in the field of readability, rather than performance (which will probably be handled by the compiler).

Use for loop instead of while

The idiom for (int i=0; i<32; i++) is more readable than the while loop if you know the number of iterations in advance.

Divide the numbers by two

Dividing the numbers by two and getting the modulu:

n1 = p % 2;
p  /= 2;

Is perhaps more readable than:

(p & (1<<(i-1)))>>(i-1);

Upvotes: 2

Related Questions