Monday, July 4, 2016

Sum of Two integers

Problem:
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.


Credits:
Special thanks to @fujiaozhu for adding this problem and creating all test cases.

Solution:

class Solution {
public:
    int getSum(int a, int b) {
        // Simpler solution.
        /*
        int sum = a, carry = 0;
        while (b) {
            carry = sum & b;
            sum ^= b;      // xor operator take care of summing except 1 ^ 1.
            carry <<= 1;   // All carries will be adding up in next position.
            b = carry;     // So, make it new number to add.
        }
        return sum;
        */
        // Another Solution.
        int size = (8 * sizeof(int)), ans = 0, a_i, b_i, carry = 0, loc;
        for (int i = 0; i < size; i++) {
            loc = 1 << i;
            a_i = a & loc;
            b_i = b & loc;
            ans ^= a_i ^ b_i ^ carry;
            carry = (a_i & b_i) | (carry & a_i) | (carry & b_i);
            carry <<= 1;
        }
        return ans;
    }
};

No comments:

Post a Comment