Reputation: 14278
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
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
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
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).
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.
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