LeetCode: Sum of Two Integers C#

Question

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

potato · Accepted Answer · 2020-03-20 08:12:25Z

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;
}

Stack Exchange Network

LeetCode: Sum of Two Integers C#

1 Answer 1

You must log in to answer this question.

Hot Network Questions

LeetCode: Sum of Two Integers C#

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions