371. Sum of Two Integers

Description

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

Example 1:

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

Example 2:

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

Constraints:

-1000 <= a, b <= 1000

Solutions

Bit Manipulation, when doing addition operation, after each bit is added, there may be a Carry generated, and then the next bit calculation needs to be added to the calculation together, then can the two parts be separated, let’s look at an example 759+ 674

If you do not consider the carry, you can get 323
If you only consider the carry, you can get 1110
Put the above two numbers holiday 323+1110=1433 is the final result

Then further analysis, if you get the first and second cases above, looking at it in binary,

Do not consider the addition of carry, 0+0=0, 0+1=1, 1+0=1, 1+1=0, this is the operation rule of XOR,
If you only consider the addition of carry 0+0=0, 0+1=0, 1+0=0, 1+1=1, this is actually the operation of and,
In the third step, when the two are added, the algorithm is called recursively, and the termination condition is that when the carry is 0, the result of the first step is directly returned.

Components of `~(a ^ mask)`:

~(a ^ mask) is part of a technique to handle the addition of two integers a and b without using the + or - operators, with an emphasis on correctly handling negative numbers in a 32-bit environment.

mask = 0xFFFFFFFF: This is a 32-bit mask with all bits set to 1. In binary, mask is 11111111 11111111 11111111 11111111. When used with the & operator, it ensures that any integer is trimmed to its lowest 32 bits. This is crucial for simulating 32-bit integer overflow behavior in environments (like Python) where integers have arbitrary precision and won’t naturally overflow.
a ^ mask: This operation performs a bitwise XOR between a and mask. For positive numbers, this operation does not change the sign of the result. However, for negative numbers represented in two’s complement (which is the standard way to represent negative numbers in binary), XORing with mask effectively inverts all bits of a, turning it into its two’s complement minus one (you can think of it as a step before obtaining the two’s complement representation of a positive number).
~: This bitwise NOT operation inverts all bits in the result of a ^ mask. The combination of XOR with mask and then applying ~ effectively computes the two’s complement of a, turning it back into a positive number if a was negative. This is because, in two’s complement, negative numbers are represented by inverting all bits of their absolute value and then adding 1.

Why use `~(a ^ mask)`?

The expression ~(a ^ mask) is used to convert the final sum a from a two’s complement negative number back to its normal negative representation if a originally was a negative number that exceeded the 32-bit signed integer range.

If a is a positive number within the range of a 32-bit signed integer, a < kMax evaluates to True, and the method simply returns a.
If a exceeds the 32-bit signed integer range (meaning it’s a negative number in two’s complement representation due to overflow), a < kMax evaluates to False, and ~(a ^ mask) is used to convert a back to a standard negative integer that Python can understand.

This technique allows the method to correctly return both positive and negative sums within a 32-bit environment, mimicking the behavior of 32-bit signed integer addition, including handling overflow correctly.

Let’s walk through the provided code with the input a = 2 and b = 3 to understand how it calculates the sum without using the + or - operators.

Example input walkthrough

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

Initial Setup

a = 2 (in binary: 10)
b = 3 (in binary: 11)

The binary representation is used because the algorithm performs bit manipulation operations.

Masks

mask = 0xFFFFFFFF is used to handle negative numbers correctly by limiting the integer size to 32 bits.
kMax = 0x80000000 is the value used to check if the resulting number is negative. It represents the highest bit in a 32-bit integer, which determines the sign of the number in two’s complement notation.

Loop Iteration 1

Calculate a & b to find the carry, and a ^ b to add without carrying.

Carry: (a & b) << 1 = (2 & 3) << 1 = (10 & 11) << 1 = 10 << 1 = 100 (in binary), which is 4 in decimal.
Addition without carry: a ^ b = 2 ^ 3 = 10 ^ 11 = 01 (in binary), which is 1 in decimal.

Apply the mask to both to ensure they fit into 32 bits (has no effect in this case because the numbers are small).

a = 4 & mask = 4
b = 1 & mask = 1

Loop Iteration 2

Repeat the calculations with the new values of a and b.

Carry: (a & b) << 1 = (4 & 1) << 1 = (100 & 001) << 1 = 000 << 1 = 000 (in binary), which is 0 in decimal.
Addition without carry: a ^ b = 4 ^ 1 = 100 ^ 001 = 101 (in binary), which is 5 in decimal.

Apply the mask again (still no effect).

a = 0 & mask = 0
b = 5 & mask = 5

Final check

The loop ends when a becomes 0, indicating there’s no carry left to add. The sum is stored in b, which is now 5.

Since b < kMax, the condition b if b < kMax else ~(b ^ mask) simply returns b, which is the sum 5.

Thus, the output for the input a = 2, b = 3 is 5, as expected.

public class Sum_of_Two_Integers {

    public static void main(String[] args) {

        Sum_of_Two_Integers out = new Sum_of_Two_Integers();
//        System.out.println(out.getSum(1, 2)); // no carry

        // 2+2
        // recurion-1: sum=0, carry= (10)左移1位 =(100)=4
        // recursion-2: a=0,b=4
        // recursion-3: b=0
        System.out.println(out.getSum(2, 2)); // with carry
    }


    public int getSum(int a, int b) {
        if(b == 0){ // complete the operation when there is no carry
            return a;
        }

        int sum, carry;
        sum = a^b; // step-1 sum
        carry = (a&b)<<1; // step-2 sum

        return getSum(sum, carry);
    }
}

/////////

class Solution {
    public int getSum(int a, int b) {
        return b == 0 ? a : getSum(a ^ b, (a & b) << 1);
    }
}

class Solution {
public:
    int getSum(int a, int b) {
        while (b) {
            unsigned int carry = (unsigned int) (a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

'''
0x80000000
Taking the binary of 0x80000000 we get:
    1000 0000 0000 0000 0000 0000 0000 0000

equivalent decimal value is 2,147,483,648(1's complement conversion)
https://stackoverflow.com/questions/18813875/how-is-0x80000000-equated-to-2147483648-in-java



0xffffffff
Taking the binary of 0xffffffff we get:
    1111 1111 1111 1111 1111 1111 1111 1111

No sign bit in python
0xFFFFFFFF masking to detect int32 overflow

x & 0xFFFFFFFF == x
    ===> will return True if x doesn't oveflow and x is larger than 0.

https://stackoverflow.com/questions/36819849/detect-int32-overflow-using-0xffffffff-masking-in-python



>>> bin(0x80000000)
'0b10000000000000000000000000000000'
>>> bin(0xffffffff)
'0b11111111111111111111111111111111'

>>> 0x80000000 & 0xffffffff
2147483648
>>> 0x80000000 ^ 0xffffffff
2147483647
'''

'''
>>> 1^1
0
>>> 0^0
0
>>> 1^0
1
>>> 0^1
1
'''

class Solution:
  def getSum(self, a: int, b: int) -> int:
    mask = 0xFFFFFFFF
    kMax = 0x80000000
    # the result of each step is passed recursively to the getSum function
    # until there is no carry (b == 0)
    # at that point, the function returns the final sum.
    while a:
      a, b = ((a & b) << 1) & mask, (a ^ b) & mask

    return b if b < kMax else ~(b ^ mask)
    # ~(b ^ mask) turning it back into a positive number if b was negative


class Solution: # also passing OJ by switching a/b
  def getSum(self, a: int, b: int) -> int:
    mask = 0xFFFFFFFF
    kMax = 0x80000000
    # the result of each step is passed recursively to the getSum function
    # until there is no carry (b == 0)
    # at that point, the function returns the final sum.
    while b:
      a, b = (a ^ b) & mask, ((a & b) << 1) & mask

    return a if a < kMax else ~(a ^ mask)

#############

class Solution: # no mast, no overflow consideration
  def getSum(a: int, b: int) -> int:
    if b == 0:
        return a

    sum = a ^ b  # Step 1: sum without carry
    carry = (a & b) << 1  # Step 2: calculate carry

    return getSum(sum, carry)

func getSum(a int, b int) int {
	for b != 0 {
		s := a ^ b
		b = (a & b) << 1
		a = s
	}
	return a
}

371 - Sum of Two Integers

371. Sum of Two Integers

Description

Solutions

Components of `~(a ^ mask)`:

Why use `~(a ^ mask)`?

Example input walkthrough

Initial Setup

Masks

Loop Iteration 1

Loop Iteration 2

Final check

All Problems

All Solutions

Welcome to Subscribe On Youtube

371. Sum of Two Integers

Description

Solutions

Components of ~(a ^ mask):

Why use ~(a ^ mask)?

Example input walkthrough

Initial Setup

Masks

Loop Iteration 1

Loop Iteration 2

Final check

All Problems

All Solutions

Components of `~(a ^ mask)`:

Why use `~(a ^ mask)`?