Adding binary integer without using + or -

Question

add two integers without using + or -.

This is my solution.

class Solution {
public:
    int getSum(int a, int b) {
        int temp=a & b; 
        a=a^b;
        while (temp>0){
            b=temp<<1; 
            temp=a & b; 
            a=a^b;
        }
        return a; 
    }
};

But it doesn't work on the cases when a=-12, b=-8.

Compare it side by side with another people's working solution, he has:

class Solution {
public:
    int getSum(int a, int b) {
        int sum = a;

        while (b != 0)
        {
            sum = a ^ b;//calculate sum of a and b without thinking the carry 
            b = (a & b) << 1;//calculate the carry
            a = sum;//add sum(without carry) and carry
        }

        return sum;
    }
};

which is bascially the same. Why my solution doesn't work?

Because yours is wrong. The order and placement of the operations is significant. — Ken White
– Ken White, Commented Nov 20, 2016 at 1:32
because while (temp>0) ... if you & 2 negative numbers, you get another negative — technosaurus
– technosaurus, Commented Nov 20, 2016 at 1:36
No, they're not basically the same. Read what I wrote again, specifically the second sentence. abc is not basically the same as bac or cab when you're reciting the alphabet. — Ken White
– Ken White, Commented Nov 20, 2016 at 1:37
if I change while(temp<0) to while (temp != 0) do you think this will work? — Anni_housie
– Anni_housie, Commented Nov 20, 2016 at 1:37

Peter · Accepted Answer · 2016-11-20 02:12:47Z

Strictly speaking both your solution and the one you are comparing with are incorrect, unless you make specific assumptions about the representation of signedintegral types. The reason yours differs is order of operations.

The explanation is written in the C standard itself. For example, from the 2011 ISO C standard (ISO/IEC 9899:2011) Section 6.5, para 4.

Some operators (the unary operator ~ , and the binary operators <<, >>, &, ^, and |, collectively described as bitwise operators) shall have operands that have integral type. These operators return values that depend on the internal representations of integers, and thus have implementation-defined and undefined aspects for signed types.

These concerns hit home with expressions like a & b if either a or b is negative .... and your example has both. a << 1 gives a similar concern if a is negative.

To eliminate your problem, you need to work with unsigned values (for which bitwise operators have well defined behaviour). If you need to deal with negative values, simply keep track of sign in another way (e.g. another variable of type bool).

In practice, bitwise operations work as expected for signed types with a twos-complement representation. The problem with relying on that, however, is that an implementation is not required to use such a representation.

Collectives™ on Stack Overflow

Adding binary integer without using + or -

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related