LeetCode 371: Sum of Two Integers

Use bitwise XOR and AND operations to implement additive operation of two integers. XOR operation (a ^ b) forms the sum of binary addition (a + b) without carry. AND operation (a & b) forms the carry of the binary addition (a + b). Shift the carry to the left by 1 ((a & b) << 1). Keep performing addition of the carry and the sum (a ^ b + (a & b) << 1)until the carry becomes 0. The sum will be the result of addition.

addition using bitwise XOR and AND operations

Table of Contents

· Bitwise Operations
  ∘ Bitwise AND Operator(&)
  ∘ Bitwise XOR Operator(^)
· Problem
· Approach
· Graphic Explanation
· Code Implementation
  ∘ Complexity
  ∘ Golang
  ∘ Python

Bitwise Operations

Bitwise AND Operator(&)

Return 1 if both of bits are 1. Otherwise, return 0.

bitwise AND operator

Bitwise XOR Operator(^)

XOR stands for “exclusive or”. Return 0(false) if both bits are the same. Otherwise, return 1(true).

Problem

Given two integers a and b, return the sum of the two integers without using the operators + and -.

• -1000 <= a, b <= 1000

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

Example 2:
Input: a = 2, b = -5
Output: -3

Approach

Use bitwise XOR and AND operations to perform additive operation. XOR operation and AND operation produce the sum and carry of the binary addition respectively.

a XOR b (a ^ b): form bitwise sum of a+b w/o carry
a AND b (a & b): form bitwise carry of a+b

addition using bitwise XOR and AND operations table

Shift carry to the left by 1 and the adding carry and sum to produce the result of addition.

a + b = a XOR b + ((a AND b) << 1)
      = a ^ b + ((a & b) << 1)

addition using bitwise XOR and AND operations

Follow above approach, keep adding the two operands using bitwise XOR and AND operations until the operand that represented carry becomes 0.

Graphic Explanation

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

Example 2:
Input: a = 2, b = -5
Output: -3

Code Implementation

Complexity

Time: O(1) input is in a fixed range(-1000 <= a, b <= 1000)
Space: O(1)

Golang

Python

In Python, value of an integer is not restricted by the number of bits. we need to use a mask 0xFFFFFFFF to restrict the lengths. You can check below links for details.

What is the maximum possible value of an integer in Python ? - GeeksforGeeks

【Python】 BEST LeetCode 371 Explanation for Python - Sum of Two Integers - LeetCode

How is 0XFFFFFFFF represented in a 32-bit system in integer form (4294967295)?

You can access the source code here.

LeetCode Problem

• 371. Sum of Two Integers