/* LeetCode 371. Sum of Two Integers Given two integers a and b, return the sum of the two integers without using the operators + and -. Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5 Constraints: -1000 <= a, b <= 1000 */ #include #include using namespace std; const int PRINT = 0; const int NUM_BITS = 12; class Solution //: public testing::Test { public: //virtual void SetUp() {} //virtual void TearDown() {} // Twos complement: invert digits and add '1' // 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& bs) { cout << tag << ": " << bs << " " << bs.to_ulong() << endl; } void printBitset(const string& tag_a, const bitset& bs_a, const string& tag_b, const bitset& bs_b) { cout << tag_a << ": " << bs_a << " " << bs_a.to_ulong() << " " << tag_b << ": " << bs_b << " " << bs_b.to_ulong() << endl; } bool is_negative(bitset& bs) { return bs.test(NUM_BITS-1); } bitset from_twos_complement(bitset& bs) { cout << "fom_twos complmement: " << bs << endl; bs.flip(); bitset one(1); return binaryAdd(bs, one); } bitset twos_complement(int x) { cout << " twos complmement: " << x << endl; bitset a(abs(x)); a.flip(); bitset one(1); bitset result = binaryAdd(a, one); return result; } bitset binaryAdd(bitset x, bitset y) { printBitset(" binaryAdd: x", x, "y", y); bitset 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 bs_a = (a >= 0) ? bitset(a) : twos_complement(a); bitset bs_b = (b >= 0) ? bitset(b) : twos_complement(b); printBitset("bs_a", bs_a, "bs_b", bs_b); bitset result = binaryAdd(bs_a, bs_b); if (is_negative(result)) { result = 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 result = twos_complement(x); // cout << "twos_complement: " << x << " " << result.to_ulong() << " " << result << endl; // } // } // TEST_F(Solution, MaxMin) // { // // bit NUM_BITS is sign bit // bitset 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); // } struct Solution_xAI { int getSum(int a, int b) { while (b != 0) { bitset<32> aa(a), bb(b); cout << format("a={} [{}] b={} [{}]\n", a, aa.to_string(), b, bb.to_string()); int c = (a & b) << 1; bitset<32> x(a^b), y(a&b), z(c); cout << format(" (a ^ b)={} [{}] (a & b)={} [{}] carry={} [{}]\n", (a ^ b), x.to_string(), (a & b), y.to_string(), c, z.to_string()); // 2 + 2 = 4 // carry carry // ----------- --------- // a ^ b a & b (a&b) << 1 a ^ b a & b (a&b) << 1 // 2 ^ 2 2 & 2 (2&2) << 1 0 ^ 4 0 & 4 (0&2) << 1 // ----- ----- ----------- ----- ----- ---------- // 0010 0010 sum = 0 0000 0000 // 0010 0010 carry = 4 0100 0100 ==> a = 4, carry = 0 // ---- ---- ---- ---- ==> result = 4 // 0000 0010 0100 0100 0000 0000 int carry = (a & b) << 1; // generate carry int sum = a ^ b; // add without carry a = sum; b = carry; } return a; } }; int main(int argc, char** argv) { // constraint // -1000 <= a, b <= 1000 vector> testCases = { // a b a+b { 1, -1, 0 }, { 1, 1, 2 }, { -1, -2, -3 }, { 1000, 1000, 2000 }, { -1000, -1000, -2000 }, { 2, 2 , 4 }, }; Solution_xAI s; for (auto testCase: testCases) { cout << "add: " << get<0>(testCase) << " + " << get<1>(testCase) << endl; int sum = s.getSum(get<0>(testCase), get<1>(testCase)); int expected = get<2>(testCase); cout << " sum: " << get<0>(testCase) << " + " << get<1>(testCase) << endl; cout << "expected: " << expected << endl; cout << " actual: " << sum << endl; EXPECT_EQ(expected, sum); cout << "---------------------------------------" << endl; } //testing::InitGoogleTest(&argc, argv); //int ret = RUN_ALL_TESTS(); // return ret; return 0; }