#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

const int PRINT = 0;
const int NUM_BITS = 12;

class Solution //: public testing::Test
{
public:

    //virtual void SetUp() {}
    //virtual void TearDown() {}
    
    // XOR
    // ---
    // 0 0 | 0
    // 1 0 | 1
    // 0 1 | 1
    // 1 1 | 0

    // iterate over bit positions starting with LSB. result bit is XOR
    // of bit_a, bit_b, carry.

    // bit_a bit_b carry result next_carry
    // 0     0     0     0      0
    // 0     0     1     1      0
    // 0     1     0     1      0
    // 0     1     1     0      1
    // 1     0     0     1      0
    // 1     0     1     0      1
    // 1     1     0     0      1
    // 1     1     1     1      1

    // examples:     6 + 3 = 9    7 + 7 = 14
    // -------------------------------------
    // nxt_carry ->   1 1 0 0      1 1 1 0
    //                 0 1 1 0      0 1 1 1
    //              +  0 0 1 1    + 0 1 1 1
    //                --------   ----------
    //                 1 0 0 1      1 1 1 0
    //
    // start with curr_carry = 0
    // result_bit = curr_carry ^ bit_a ^ bit_b

    // bit_a bit_b curr_carry next_carry
    // 0     0     0          0
    // 0     0     1          0
    // 0     1     0          0
    // 0     1     1          1 <--- bit_b & curr_carry
    // 1     0     0          0
    // 1     0     1          1 <--- bit_a & curr_carry
    // 1     1     0          1 <--- bit_a & bit_b
    // 1     1     1          1 <--- bit_a & bit_b & curr_carry

    void printBitset(const string& tag, const bitset<NUM_BITS>& bs)
    {
        cout << tag << ": " << bs << " " << bs.to_ulong() << endl;
    }
    
    void printBitset(const string& tag_a, const bitset<NUM_BITS>& bs_a,
                     const string& tag_b, const bitset<NUM_BITS>& bs_b)
    {
        cout << tag_a << ": " << bs_a << " " << bs_a.to_ulong() << " "
             << tag_b << ": " << bs_b << " " << bs_b.to_ulong()
             << endl;
    }
    
    bool is_negative(bitset<NUM_BITS>& bs) { return bs.test(NUM_BITS-1); }

    bitset<NUM_BITS> from_twos_complement(bitset<NUM_BITS>& bs)
    {
        bs.flip();
        bitset<NUM_BITS> one(1);        
        return binaryAdd(bs, one);
    }
    
    bitset<NUM_BITS> twos_complement(int x)
    {
        bitset<NUM_BITS> a(abs(x));
        a.flip();
        bitset<NUM_BITS> one(1);
        bitset<NUM_BITS> result = binaryAdd(a, one);
        printBitset(string("twos_complement ") + to_string(x), result);
        return result;
    }

    bitset<NUM_BITS> binaryAdd(bitset<NUM_BITS> x, bitset<NUM_BITS> y)
    {
        printBitset("  binaryAdd: x", x, "y", y);
        
        bitset<NUM_BITS> result, next_carry;
        
        for (int i = 0; i < NUM_BITS; i++)
        {
            if (PRINT) cout << "i=" << i << endl;
            printBitset("  x", x, "y", y);
            
            bitset<1> a, b, curr_carry;
            if (x.test(i))          a.set();
            if (y.test(i))          b.set();
            if (next_carry.test(i)) curr_carry.set();

            if (PRINT)
                cout << "  a: " << a << " b: " << b << " curr_carry: " << curr_carry << endl;
            
            bitset<1> xor_result = a ^ b ^ curr_carry;
            
            if (PRINT) cout << "  xor_result: " << xor_result << endl;
            
            if (xor_result.all())
                result.set(i);
            
            if (PRINT) cout << "  result: " << result << endl;
            
            // next_carry
            if ( (a.all() && b.all())           ||
                 (a.all() && curr_carry.all())  ||
                 (b.all() && curr_carry.all()))
            {
                if (i+1 < NUM_BITS)
                    next_carry.set(i+1);
            }
            if (PRINT) cout << "  next_carry: " << next_carry << endl;
        }

        printBitset("result", result);
        
        return result;
    }

    int getSum(int a, int b)
    {
        //                  111
        //                  2109876543210
        // 2^12 = (4096) = (1000000000000)2

        cout << "==============================" << endl;
        cout << "a=" << a << " b=" << b << endl;
        
        bitset<NUM_BITS> bs_a = (a >= 0) ? bitset<NUM_BITS>(a) : twos_complement(a);
        bitset<NUM_BITS> bs_b = (b >= 0) ? bitset<NUM_BITS>(b) : twos_complement(b);

        printBitset("bs_a", bs_a, "bs_b", bs_b);
        
        bitset<NUM_BITS> result = binaryAdd(bs_a, bs_b);
        
        if (is_negative(result))
        {
            result = from_twos_complement(result);
            printBitset("from twos_complement: ", result);
            return result.to_ulong() * -1;
        }
        
        return result.to_ulong();        
    }
};

// TEST_F(Solution, Sum)
// {
//     for (auto testCase: testCases)
//     {
//         int sum = getSum(get<0>(testCase), get<1>(testCase));
//         EXPECT_EQ(sum, get<2>(testCase));
//         cout << "sum: " << get<0>(testCase) << " + " << get<1>(testCase) << " = " << get<2>(testCase) << endl;
//     }
// }

// TEST_F(Solution, TwosComplement)
// {
//     for (int x: {-1, -2})
//     {
//         bitset<NUM_BITS> result = twos_complement(x);
//         cout << "twos_complement: " << x << " " << result.to_ulong() << " " << result << endl;
//     }
// }

// TEST_F(Solution, MaxMin)
// {
//     // bit NUM_BITS is sign bit
//     bitset<NUM_BITS> max_bs;
//     max_bs.set();
//     long max_positive = max_bs.to_ulong();
//     long max_negative = max_bs.to_ulong() * -1;
//     EXPECT_EQ(max_positive, 1023);
//     EXPECT_EQ(max_negative, -1023);    
// }

int main(int argc, char** argv)
{
    // constraint
    // -1000 <= a, b <= 1000

    vector<tuple<int,int,int>> testCases = {
        //    a     b       a+b
        {     1,    -1,     0   },
        {     1,     1,     2   },
        {    -1,    -2,    -3   },
        {  1000,  1000,  2000   },
        { -1000, -1000, -2000   },        
    };

    Solution s;

    for (auto testCase: testCases)
    {
        cout << "---------------------------------------" << endl;
        cout << "add: "  << get<0>(testCase) << " + " << get<1>(testCase) << endl;

        int sum = s.getSum(get<0>(testCase), get<1>(testCase));
        cout << "    sum: "  << get<0>(testCase) << " + " << get<1>(testCase) << endl;
        cout << "expected: " << get<2>(testCase) << endl;
        cout << "  actual: " << sum << endl;
    }

    //testing::InitGoogleTest(&argc, argv);
    
    //int ret = RUN_ALL_TESTS();
    
    // return ret;
    return 0;
}