CODEWITHSUNDEEP
c++binarybit-manipulationbit
Anni_housie
Anni_housie

Reputation: 489

Adding binary integer without using + or -

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?

Upvotes: 0

Views: 78

Answers (1)

Peter
Peter

Reputation: 36597

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.

Upvotes: 2

Related Questions