Addition without arithmetic operators

[nitin1]

#include<iostream>

using namespace std;

int add(int x,int y)
{
    int ans=0;
    int carry=0;

    for(int i=0;i<=31;i++)
    {
        int p = (1<<i)&x;
        int q = (1<<i)&y;

        int r = p ^ q;
        r = r^(carry<<i);

        ans = r | ans;

        if(p&q || p&(carry<<i) || q&(carry<<i))
            carry = 1;
        else
            carry =0;

    }

    return (ans);
}

int main()
{
    int x,y;

    x=-2;y=6;
//add(4,6);
    cout<<endl<<add(x,y)<<endl;

   return 0;
}

Actually, I am trying to add bit by bit. When number is negative, it is represented by 2's compliment. But, here I am using the 32th leftmost bit. Isn't it wrong?

It is giving corrent for small numbers but for large numbers like (-2222222,6) giving wrong answer. Can anyone explain why?

Thanks a lot in advance.

[rubberman]

This is a good exercise in bit-twiddling. Just remember, a left shift is a multiply by 2, a right shift divide by 2. Your logic is faulty and you need to rethink how to deal with the bits. Here is an example:

2 (dec) == 0x10 hex.
3 (dec) == 0x11 hex.

So 2+3 == ??

0x10 + 0x10 (2+2) == 0x100 (4)
0x100 + 0x1 (4+1) == 0x101 (5)

which is 2+3. So, without adding this would be the same as (0x10 << 1) | 0x1 == 0x101 (5). No &'s required.

[vijayan121]

#include <iostream>
#include <limits>
#include <stdexcept>
#include <algorithm>
#include <cassert>

// algorithm from 'Hacker's Delight' by Henry S. Warren
// http://www.amazon.com/dp/0201914654 
unsigned int plus( unsigned int a,  unsigned int b )
{
    auto carry = a & b;
    auto sum = a ^ b;

    while( carry != 0 )
    {
        const auto carry_shl = carry << 1 ;
        carry = sum & carry_shl ;
        sum ^= carry_shl ;
    }

    return sum ;
}

// Note: This assumes that the signed integer value representation is two's complement
// Two's complement is almost universally used, though he C++ standard allows any
// appropriate signed integer representation.
// For instance, one's complement and sign-and-magnitude representations would be conforming
int signed_plus( int a,  int b )
{
    const long long aa = a ;
    long long result = aa + b ;
    if( result < std::numeric_limits<int>::min() || result > std::numeric_limits<int>::max() )
                    throw std::out_of_range( "signed integer overflow!" ) ;

    return int( plus(a,b) ) ;
}

int main()
{
    const int test[][2] { {12345678,0}, {-12345678,0}, {12345678,67890}, {12345678,-67890}, {-12345678,67890}, {-12345678,-67890} } ;
    for( const auto& arr : test  )
    {
         int x = arr[0] ;
         int y = arr[1] ;

         std::cout << x << " + " << y << " == " << x+y << " == " << signed_plus(x,y) << '\n' ;

         std::swap(x,y) ;
         std::cout << x << " + " << y << " == " << x+y << " == " << signed_plus(x,y) << '\n' ;

         assert( ( (x+y) == signed_plus(x,y) ) && ( (x+y) == signed_plus(y,x) ) );
    }

    try { std::cout << signed_plus( 1999999999, 2000000000 ) << '\n' ; }
    catch( const std::exception& e ) { std::cerr << "**** error: " << e.what() << '\n' ; }
}

http://coliru.stacked-crooked.com/a/93d91547db0164fa
http://rextester.com/SSBR13704

[nitin1]

@rubberman, so what's the problem with my code? How can I correct my code? I got whatever you said in the post. Can you mark the points where my program might be going wrong which is resulting in wrong answers for some cases? Thanks

[rubberman]

Start with lines 42 and 43. I assume you want to add the numbers in each element of the array, but it is a 2 dimension array, so lines 42 and 43 would have to be like this:

 int x = arr[0][0] ;
 int y = arr[0][1] ;

Also, you are making your code much more complex than it needs to be. Make the last element of the test array a guard element, such as {0,0} or {-1,-1} and do a regular loop for (i = 0; test[i][0] == -1 && test[i][1] == -1; i++) setting x and y to test[i][0] and test[i][1].

Processing negative numbers is a bit more complex than the all positive ones, though even with the positive numbers you have to deal with integer overflow which would set the top bit, making it a negative number, in which case you need to throw an overflow exception. Anyway, I'm leaving that to you to deal with that in your plus() function. Also, you are using addition in your signed_plus() function, which you say you are not supposed to do. Try to do some trivial positive and negative number sums by hand to determine what the bits should look like. That will help you work out the algorithms you need. And remember, simplify, simplify, simplify. You are trying to be too clever and complex for the task at hand. And this may be a good time to see how an assembler would do this. :-)

[nitin1]

@rubberman, you told me about vijayan121 code. I want to discuss about the code which I posted in the beginning only. That is fine which you told me for Vijayan's code. Please discuss about my code also.

[rubberman]

@nitin1 - oops, sorry about that. I hate it when people hijack other folks' threads. I'll get back to that when I have a minute.