Problem

Given two integers x and y, compute x - y without using the arithmetic subtraction operator (-). Use bitwise operators and shifts only, and preserve two’s-complement semantics for negative numbers.

Examples

Example 1

1
2

Input: x = 10, y = 4
Output: 6

Example 2

1
2

Input: x = 5, y = -3
Output: 8
Similar Problems

Solution

This problem is a small variant of the addition-without-+ trick (LeetCode 371). Subtraction can be reduced to addition by using two’s complement: x - y == x + (-y) where -y == ~y + 1.

We present two concise approaches: (A) use an add routine that uses XOR/AND+shift to compute sum+carry iteratively, then compute x + (~y + 1), and (B) directly perform the iterative subtraction-like step using XOR and borrow propagation.

Method 1 — Two’s-complement reduction (use add)

Intuition

In two’s-complement arithmetic, negation is ~y + 1. So subtraction x - y equals x + (~y + 1). Implement add(a, b) using bitwise XOR for sum and bitwise AND/shift for carry, and reuse it for subtraction.

Approach

  1. Implement add(a, b):
    • sum = a ^ b (sum without carries).
    • carry = (a & b) << 1 (carries shifted into place).
    • Repeat with a = sum, b = carry until b == 0.
  2. Compute neg_y = add(~y, 1) and return add(x, neg_y).

Edge cases: work in fixed-width words (32/64-bit) depending on language; be aware of overflow behavior according to language semantics.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
 public:
  static int add(int a, int b) {
    while (b != 0) {
      int sum = a ^ b;
      int carry = (a & b) << 1;
      a = sum;
      b = carry;
    }
    return a;
  }

  static int subtract(int x, int y) {
    int neg_y = add(~y, 1);
    return add(x, neg_y);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

package main

func Add(a, b int32) int32 {
    for b != 0 {
        sum := a ^ b
        carry := (a & b) << 1
        a = sum
        b = carry
    }
    return a
}

func Subtract(x, y int32) int32 {
    negY := Add(^y, 1)
    return Add(x, negY)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public static int add(int a, int b) {
        while (b != 0) {
            int sum = a ^ b;
            int carry = (a & b) << 1;
            a = sum;
            b = carry;
        }
        return a;
    }

    public static int subtract(int x, int y) {
        int negY = add(~y, 1);
        return add(x, negY);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    @staticmethod
    def add(a: int, b: int) -> int:
        while b != 0:
            s = a ^ b
            carry = (a & b) << 1
            a = s
            b = carry
        return a

    @staticmethod
    def subtract(x: int, y: int) -> int:
        neg_y = Solution.add(~y, 1)
        return Solution.add(x, neg_y)

Complexity

  • ⏰ Time complexity: O(k) where k is the machine-word bit-width (each iteration propagates carries/borrows across bits).
  • 🧺 Space complexity: O(1) extra space.

Method 2 — Direct XOR/borrow iteration (no explicit add)

Intuition

This method uses the same idea as addition without + but propagates borrows instead of carries. The recurrence x' = x ^ y, y' = (~x & y) << 1 repeatedly removes borrow bits until y == 0 and x contains the result.

Approach

  1. While y != 0 do:
    • diff = x ^ y (subtraction without borrows applied yet).
    • borrow = (~x & y) << 1 (bits that must be borrowed).
    • Set x = diff, y = borrow.
  2. When y == 0, x is the final result.

This loop is equivalent to recursive sub(x ^ y, (~x & y) << 1) and terminates in O(k) steps.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
 public:
  static int subtract(int x, int y) {
    while (y != 0) {
      int diff = x ^ y;
      int borrow = (~x & y) << 1;
      x = diff;
      y = borrow;
    }
    return x;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

package main

func Subtract(x, y int32) int32 {
    for y != 0 {
        diff := x ^ y
        borrow := (^x & y) << 1
        x = diff
        y = borrow
    }
    return x
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public static int subtract(int x, int y) {
        while (y != 0) {
            int diff = x ^ y;
            int borrow = (~x & y) << 1;
            x = diff;
            y = borrow;
        }
        return x;
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    @staticmethod
    def subtract(x: int, y: int) -> int:
        while y != 0:
            diff = x ^ y
            borrow = (~x & y) << 1
            x = diff
            y = borrow
        return x

Complexity

  • ⏰ Time complexity: O(k) where k is the machine-word bit-width.
  • 🧺 Space complexity: O(1) extra space.

Notes

  • For languages with unbounded integers (Python) the same code works and semantics match mathematical integers; for fixed-width languages be mindful of overflow and signed shifts.