Skip to content

17.01. Add Without Plus

Description

Write a function that adds two numbers. You should not use + or any arithmetic operators.

Example:

Input: a = 1, b = 1

Output: 2

 

Note:

  • a and b may be 0 or negative.
  • The result fits in 32-bit integer.

Solutions

Solution 1

Thinking

Add without \(+,-,*,/\). A loop that adds would break the rule; simulating pencil-and-paper on strings is longer.

XOR is the sum without carry; AND shifted left is the carry. Repeat until the carry vanishes.

\(sum=a\oplus b\) and \(carry=(a\& b)\ll 1\) are written back into \(a\) and \(b\). The sign bit follows arithmetic shift; the loop is \(O\)(bit width).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
    public int add(int a, int b) {
        int sum = 0, carry = 0;
        while (b != 0) {
            sum = a ^ b;
            carry = (a & b) << 1;
            a = sum;
            b = carry;
        }
        return a;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
    func add(_ a: Int, _ b: Int) -> Int {
        var a = a
        var b = b
        var sum = 0
        var carry = 0

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

        return a
    }
}

Comments