1
\$\begingroup\$

https://leetcode.com/problems/sum-of-two-integers/

Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1:

Input: a = 1, b = 2 Output: 3 Example 2:

Input: a = -2, b = 3 Output: 1

using Microsoft.VisualStudio.TestTools.UnitTesting;

namespace MathQuestions
{
    /// <summary>
    /// https://leetcode.com/problems/sum-of-two-integers/
    /// </summary>
    [TestClass]
    public class SumOfTwoIntegersTest
    {
        [TestMethod]
        public void ExampleTest()
        {
            int a = 1;
            int b = 2;
            int expected = 3;
            Assert.AreEqual(expected, GetSum(a,b));
        }

        [TestMethod]
        public void ExampleTest2()
        {
            int a = 5;
            int b = 7;
            int expected = 12;
            Assert.AreEqual(expected, GetSum(a, b));
        }


        public int GetSum(int a, int b)
        {
            if (a == 0) return b;
            if (b == 0) return a;

            while (b != 0)
            {
                int carry = a & b;
                a = a ^ b;
                b = carry << 1;
            }

            return a;

        }
    }
}

Please review for performance

\$\endgroup\$
2
\$\begingroup\$

Your code is pretty much perfect, the only problem is that you chose to sacrifice some performance in most cases (non 0 operands) for the sake of making the rare case faster. Here's a slight improvement based on the assumption that most of the times none of the operands will be 0.

The trick is to keep it efficient in the case of 0 without wasting time on special checks that don't help the actual calculation. If the carry is 0 then you know you're done. Storing the output (a ^ b) in the same variable removes the need for an if statement for returning b instead of a.

Also 1 bitwise operation and assignment is saved by shifting the carry at the start of the loop, so there is no extra unused shift at the end. (note: it would slow the function down in case of overflow, but that's a rare case and it's expected that the programmer will avoid overflow anyway)

public int GetSum(int a, int b)
{
    int carry = a & b;
    a = a ^ b;

    while (carry != 0)
    {
        b = carry << 1;
        carry = a & b;
        a = a ^ b;
    }

    return a;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.