Welcome to Subscribe On Youtube
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 get323
 If you
only consider
the carry, you can get1110
 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 ofXOR
,  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 ofand
,  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 32bit environment.

mask = 0xFFFFFFFF
: This is a 32bit mask with all bits set to1
. In binary,mask
is11111111 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 32bit 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 betweena
andmask
. 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 withmask
effectively inverts all bits ofa
, 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 ofa ^ mask
. The combination of XOR withmask
and then applying~
effectively computes the two’s complement ofa
, turning it back into a positive number ifa
was negative. This is because, in two’s complement, negative numbers are represented by inverting all bits of their absolute value and then adding1
.
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 32bit signed integer range.
 If
a
is a positive number within the range of a 32bit signed integer,a < kMax
evaluates toTrue
, and the method simply returnsa
.  If
a
exceeds the 32bit signed integer range (meaning it’s a negative number in two’s complement representation due to overflow),a < kMax
evaluates toFalse
, and~(a ^ mask)
is used to converta
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 32bit environment, mimicking the behavior of 32bit 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 32bit 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 is4
in decimal.  Addition without carry:
a ^ b = 2 ^ 3 = 10 ^ 11 = 01
(in binary), which is1
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 is0
in decimal.  Addition without carry:
a ^ b = 4 ^ 1 = 100 ^ 001 = 101
(in binary), which is5
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 // recurion1: sum=0, carry= (10)左移1位 =(100)=4 // recursion2: a=0,b=4 // recursion3: 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; // step1 sum carry = (a&b)<<1; // step2 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/howis0x80000000equatedto2147483648injava 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/detectint32overflowusing0xffffffffmaskinginpython >>> 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 }