CodingGyan

Add Two Numbers Without + or -

hard Math and Number Theory

Problem

Read two integers a and b (|a|, |b| <= 10^9). Print a + b without using the + or - operators. Use only bit operations and shifts.

Constraints

  • -10^9 <= a, b <= 10^9

Examples

Input

5 -3

Output

2

Solutions

Best approachTime O(32)Space O(1)

A half adder in a computer: XOR gives the sum bits, AND shifted left gives the carry. Repeat until the carry is 0. Two's complement makes this work for negative numbers too.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Add two numbers with bit operations.
 * Input   : Two integers.
 * Output  : Their sum.
 * Approach: XOR is the sum without carry.
 * Time    : O(32)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long a, long b) {
        // Step 1: Work with 32-bit int values.
        int x = (int) a;
        int y = (int) b;

        // Step 2: Repeat until there is no carry left.
        while (y != 0) {
            // Step 3: AND finds the places where both bits are 1. They make a carry. Shift the carry left by 1.
            int carry = (x & y) << 1;

            // Step 4: XOR adds the bits without the carry.
            x = x ^ y;

            // Step 5: Add the carry in the next round.
            y = carry;
        }
        return x;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();
        System.out.println(solve(a, b));
    }
}
Hints (2)
  1. Which operation gives the sum bits without carry?
  2. Which operation finds the carry?

Try these next