Sum of two numbers with bitwise operator

Question

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

Don't do this. The JITter will optimize this for you already. — SLaks, Mar 10 '13 at 20:27
If it for education then why do you need optimization? Else DO NOT DO THIS! as @SLaks already said. — Smertokogt, Mar 10 '13 at 20:31
@Trying: I don't mean to sound rude, but if you don't know what the JIT is, you have no business doing low-level optimizations like this. If you want to make your program run faster, make it do less work. Writing code like this will not help and may hurt. — SLaks, Mar 10 '13 at 20:41
@SLaks i know it, but confused with the word JITter!!! But anyways thanks for your comment. — Trying, Mar 10 '13 at 20:43
The standard answer is a lot simpler than this. See http://stackoverflow.com/questions/4068033/addition-of-two-integers-using-bitwise-operators — harold, Mar 11 '13 at 09:53

Joop Eggen · Accepted Answer · 2019-05-07T15:32:50.863

28

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).

edited May 07 '19 at 15:32

answered Mar 16 '13 at 14:15

Joop Eggen

107,315
7
83
138

1

Didn't get, Why do you do left shift in line 4. Carry is (a AND b), isn't it? – Shivendra Mishra Jan 21 '16 at 04:53
2

@ShivendraMishra binary 1+1 = 10 = (1 and 1) shift left once. So a carry counts for the bit to the left. Or else: `x+y = (x^y) + ((x&y) << 1)`. – Joop Eggen Jan 21 '16 at 20:46

score 2 · Answer 2 · answered Mar 10 '13 at 20:29

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

score 0 · Answer 3 · answered Feb 21 '19 at 05:13

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

Sum of two numbers with bitwise operator

3 Answers3

Use for loop instead of while

Divide the numbers by two

Linked