1
\$\begingroup\$

Here's my code. Please review it for correctness, readability and efficiency. If you think it can be improved also let me know. This code works fine for positive numbers but doesn't for negative. How can I change it ? Any comments for improvement will be appreciated.

int sum(int a, int b)
    {
       int sum = 0;
       int carry = 0;
       int mask = 1;
       sum = doAdd(a,b,mask,carry, 0);
       return sum;
    }

    int doAdd(int a,int b, int mask, int carry, int sum)
    {
       int aBit = a&mask;
       int bBit = b&mask;

       if(mask<a||mask<b||carry!=0)
       {
          sum = sum | (carry^aBit^bBit);
          carry = (carry==0) ? (aBit&bBit) : (carry&a|carry&b);
          mask = mask << 1;
          if(carry!=0)
          carry = mask;
          return (doAdd(a,b,mask,carry, sum));
       }

       return sum;
    }
\$\endgroup\$
3
\$\begingroup\$

Your algorithm looks good, but the best algorithm (as far as I know) is following:

  1. Add 2 binary numbers without considering carry (an xor operation)
  2. Construct the difference with the actual solution, i.e., construct a number in the carry positions (a and operation then a left shift)
  3. Add the result of step 1 with step 2 (by recursion), until step2 is 0.

The code will look like this:

int add(int a, int b) {
    if (b == 0) return a;
    return add(a ^ b, (a & b) << 1);
}
\$\endgroup\$
  • \$\begingroup\$ why does you step#2 work ? \$\endgroup\$ – Phoenix Apr 17 '13 at 3:26
  • \$\begingroup\$ We can mathametically prove that the algorithm will converge (step 2 will eventually become zero). \$\endgroup\$ – faisal Apr 17 '13 at 5:04
  • \$\begingroup\$ The proof goes like this: if we can prove that (a & b) << 1) will have less or equal number of 1 bits as b, then the algorithm will converge. Since "b is bitwise and" with a, it will always have less or equal number of 1 bits than b. So, the algorithm will converge (WORST CASE SCENARIO: a has same 1 bit positions as b for all the recursive calls, even then because of the left shift (a&b)<<1 will eventtually have less number of 1 bit than b). I did not want to tap into theoritical computer science, but hope this helps :) \$\endgroup\$ – faisal Apr 17 '13 at 5:29
0
\$\begingroup\$

Nice.

Start by following Java Code Conventions; 8.2 asks for spaces around binary operators.

Add a unit test with nested loops that compares your results with + results.

There's no need for temp variables (though they do have nice self documenting names!) in sum(); it would be enough to just have it invoke the helper function like this: return doAdd(a, b, 0x1, 0, 0). Consider renaming doAdd to sum1 to more clearly show how they're related. Consider renaming the final argument to acc or accumulator.

Adding a comment (or an assert) that points out that mask only has a single bit on would be an aid to the reader. Another way to do that would be to change the API so currentBitPosition is what's passed in, and then immediately assign mask = 1 << currentBitPosition.

There seems to be a typo - looks like you wanted carry & aBit.... Oh, wait, now I see, carry can be as large as mask. Wow, that's surprising. Rename it to carryMask. Better yet, change the type to boolean to minimize reader surprise. Maybe refactor to:

...
sum |= carry ^ aBit ^ bBit;
carry = carry ? (aBit | bBit) : (aBit & bBit);
mask <<= 1;   (or: mask *= 2)
...

As far as signed arithmetic goes, you're going to have to declare your word length, and turn the comparison between mask and a into a test of whether mask is about to overflow. Good luck!

\$\endgroup\$
0
\$\begingroup\$

Formal tip : as you past zero and do nothing with sum you can remove it :

int sum(int a, int b)
    {
       int carry = 0;
       int mask = 1;
       return doAdd(a,b,mask,carry, 0);
    }
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.