371. Sum of Two Integers

Problem¶

Return a + b without using + or -.

Compact example:

input: a = 5, b = -3
work:  0101 + 1101 -> 0010
output: 2

Key trick¶

Use bit addition:

a ^ b gives the sum bits without carry.
(a & b) << 1 gives the carry bits.
Repeat until carry becomes 0.

For Python negatives, simulate fixed-width integers with a mask.

Trap¶

Python integers are not fixed-width, so negative numbers do not behave like 32-bit signed ints unless you mask.
Forgetting signed conversion at the end returns a large positive number instead of a negative one.

Why is it interesting?¶

It tests whether you understand how addition works at the bit level.
It also checks whether you know Python's integer model differs from languages with fixed-width ints.

Python solution¶

class Solution:
    def getSum(self, a: int, b: int) -> int:
        # Simulate 32-bit signed arithmetic.
        mask = 0xFFFFFFFF
        max_int = 0x7FFFFFFF

        # Keep only the low 32 bits during the process.
        a &= mask
        b &= mask

        while b:
            partial = (a ^ b) & mask # Sum without carry.
            carry = ((a & b) << 1) & mask # Carry, shifted to the next bit.
            a, b = partial, carry

        # Convert back from unsigned 32-bit to Python signed int.
        if a <= max_int:
            return a
        return ~(a ^ mask)

Complexity:

Time: \(O(1)\) for fixed 32-bit integers
Space: \(O(1)\)

Comment on my solution¶

The overall direction is good:
- you tried to simulate binary addition bit by bit.
The main issues are:
- negative numbers break this approach in Python because right-shifting negatives keeps extending 1 bits forever;
- using -~x is also rejected here because it is a disguised use of addition.
In interviews, the XOR-plus-carry loop is the standard clean answer.

# DON'T WORK
# ERROR: Line 27: The unary operator ~ combined with - is a common trick
# to perform addition (x + 1 is -~x), which violates the restriction
# on addition operations.
class Solution:
    def getSum(self, a: int, b: int) -> int:
        # a = an*2^n + a(n-1)*2^(n-1) + ...
        # b = bn*2^n + b(n-1)*2^(n-1) + ...
        # - maybe do the sum digit by digit using shift, &, ^, |

        total = 0
        carry = 0
        shift = 0

        while a or b or carry:
            a, a_digit = a >> 1, a & 1
            b, b_digit = b >> 1, b & 1

            if carry & a_digit & b_digit:
                carry, digit = 1, 1
            elif (carry & a_digit) or (carry & b_digit) or (a_digit & b_digit):
                carry, digit = 1, 0
            elif carry | a_digit | b_digit:
                carry, digit = 0, 1
            else:
                carry, digit = 0, 0

            total |= digit << shift
            # increment shift by 1
            # ~digit is -(shift + 1)
            shift = -~shift

        return total

Extra¶

Negative integers in Python¶

As -1000 <= a, b <=1000 are the constraints on a, b, why do we have to use the mask to simulate 32-bit signed arithmetic? So I understand, the while loop without the mask, and I think that we don't need it if number a and b are both positive. Is that correct? What am I missing? Is because of integer in Python or something else?

Yes: if a and b are both non-negative, you do not need the mask.

The mask is needed because of negative numbers in Python, not because the inputs can be large.

Why it works without a mask for positive numbers¶

The loop is:

while b:
    a, b = a ^ b, (a & b) << 1

For non-negative integers:

a ^ b computes sum bits without carry.
(a & b) << 1 computes carries.
Carries move left and eventually disappear.
So b becomes 0, and the loop ends.

Example:

a = 5  = 0101
b = 3  = 0011

a ^ b      = 0110
(a & b)<<1 = 0010

a = 0110
b = 0010

a ^ b      = 0100
(a & b)<<1 = 0100

a = 0100
b = 0100

a ^ b      = 0000
(a & b)<<1 = 1000

a = 0000
b = 1000

a ^ b      = 1000
(a & b)<<1 = 0000

Done: result is 8.

Why it breaks for negative numbers in Python¶

Python integers are not fixed-width.

In many languages, int is 32-bit, so negative numbers have a fixed two's-complement representation.

In Python, negative integers behave as if they had infinitely many leading 1 bits.

Example idea:

-1  = ...11111111
 1  = ...00000001

Now try the loop:

a = -1
b = 1

Step by step:

a ^ b = -2
a & b = 1
carry = 2

a = -2
b = 2

a ^ b = -4
a & b = 2
carry = 4

a = -4
b = 4

a ^ b = -8
a & b = 4
carry = 8

This keeps going forever.

Why?

The carry never disappears.
With infinite leading 1s on the negative number, there is always another carry bit to generate.

So the issue is not the input range [-1000, 1000]. The issue is that any negative input can make the naive loop non-terminating in Python.

What the mask does¶

The mask forces all values to stay within 32 bits:

mask = 0xFFFFFFFF

So instead of:

-1 = ...11111111111111111111111111111111...

you treat it as:

-1 = 11111111111111111111111111111111

Now the number of bits is finite, so carries can only move left a limited number of times. Eventually they fall off, and the loop stops.

Why 32 bits specifically¶

Because that is the standard fixed-width signed integer model used in this problem's usual solution.

You could also use another width large enough to contain the result, but 32 bits is conventional and safe here.

Since a, b are in [-1000, 1000]:

the true result is in [-2000, 2000]
so even 16 bits would be enough

But interview solutions usually use 32 bits because:

it matches common two's-complement intuition
it is the standard LeetCode-style answer
it works generally, not just for this constraint

Short answer¶

What you're missing is:

for positive numbers, no mask is needed
for negative numbers in Python, the loop may never end
the mask simulates fixed-width two's-complement arithmetic, which makes the algorithm valid again

So yes, it is because of Python's integer model.

Emacs Calc: switching base and binary operations¶

In Emacs calc, how to enter number in binary (01010) or hexa (0x7FF) and switch display to show numbers in binary, decimal or hexa?

For binary operations, push the value and shift count or second operand first, then press the key sequence. Use d 2 to display results in binary.

Enter binary: type 2#01010, then press RET.
Enter hexadecimal: type 16#7FF, then press RET.

Display radix:

Binary: d 2
Decimal: d 0
Hexadecimal: d 6
Arbitrary radix: d r, then enter the radix.

In Emacs calc, how to do binary operation like &, |, ^, ~, >> and <<?

In Calc's RPN stack:

Operation	Keys
AND `&`	`b a`
OR `\|`	`b o`
XOR `^`	`b x`
NOT `~`	`b n`
Left shift `<<`	`b l`
Right shift `>>`	`b r`

What is 32-bit two's complement?¶

A 32-bit pattern \(b_{31}\ldots b_0\) represents: \(-b_{31}2^{31}+\sum_{i=0}^{30}b_i2^i\)

Its range is: \(-2^{31} \le x \le 2^{31}-1\). That is: \(-2147483648 \le x \le 2147483647\)

For a negative integer \(x\), its bit pattern is the unsigned value: \(2^{32}+x\)

Examples:

Value	32-bit hexadecimal pattern
\(0\)	\(\mathrm{00000000}\)
\(1\)	\(\mathrm{00000001}\)
\(-1\)	\(\mathrm{FFFFFFFF}\)
\(-2\)	\(\mathrm{FFFFFFFE}\)
\(-2^{31}\)	\(\mathrm{80000000}\)
\(2^{31}-1\)	\(\mathrm{7FFFFFFF}\)

Negation can be performed by inverting all 32 bits and adding one, modulo \(2^{32}\).

The important limitation is that only 32 bits exist. Results outside the range must wrap, trap, saturate, or be undefined, depending on the language. For example, an unbounded calculation gives: \(1 \mathbin{<<} 31 = 2147483648\)

The same 32-bit pattern interpreted as a signed two's-complement integer represents: \(-2147483648\)

Infinite-precision two's-complement semantics - integer representation¶

Definition of the floor function¶

For every real number \(y\), the floor \(\lfloor y\rfloor\) is the unique integer \(k\) such that \(k\le y<k+1.\)

This definition applies equally to positive and negative numbers. For example, \(\left\lfloor\frac12\right\rfloor=0\), and \(\left\lfloor-\frac12\right\rfloor=-1.\)

Definition of the bits¶

The infinite-precision two's-complement representation of any \(x\in\mathbb Z\) is defined to be the infinite sequence

\[ \boxed{ \ldots b_3(x)b_2(x)b_1(x)b_0(x) } \]

where bit at position \(i\) are defined by:

\[ \boxed{ b_i(x) = \left\lfloor\frac{x}{2^i}\right\rfloor - 2\left\lfloor\frac{x}{2^{i+1}}\right\rfloor } \]

One can prove from the floor definition that \(b_i(x)\in\{0,1\}.\)

Definition of the lowest \(n\) bits¶

For every integer \(x\), whether nonnegative or negative, define

\[ \boxed{ r_n(x) = x-2^n\left\lfloor\frac{x}{2^n}\right\rfloor } \]

The number \(r_n(x)\) is the unique integer satisfying \(0\le r_n(x)<2^n\) and \(r_n(x)\equiv x\pmod{2^n}.\) Thus \(r_n(x)\) is the unsigned integer represented by the lowest \(n\) bits of \(x\).

As a consequence, we have:

\[ \boxed{ r_n(x)=\sum_{i=0}^{n-1}b_i(x)2^i } \]

Nonnegative case - why the bits eventually become zero¶

Suppose that \(x\ge0\), \(x\in\mathbb Z\).

By Euclidean division, write \(x=q2^n+s, 0\le s<2^n.\) Then \(r_n(x)=s.\)

In particular, if \(0\le x<2^n,\) then \(r_n(x)=x.\)

For sufficiently large \(i\), one has \(2^i>x\), so \(\left\lfloor\frac{x}{2^i}\right\rfloor = \left\lfloor\frac{x}{2^{i+1}}\right\rfloor = 0.\)

Consequently, \(b_i(x)=0.\)

Therefore a nonnegative integer has eventually all zero bits.

Negative case - why the bits eventually become one¶

Suppose that \(x<0, x\in\mathbb Z.\)

Write \(x=-m, m>0.\)

If \(0<m\le2^n,\) then \(\left\lfloor-\frac{m}{2^n}\right\rfloor=-1,\) and therefore

\[ \boxed{ r_n(-m)=2^n-m } \]

For example, with \(n=2\):

\[ r_2(-1)=4-1=3=1\cdot2^0+1\cdot2^1, \\ r_2(-2)=4-2=2=0\cdot2^0+1\cdot2^1, \\ r_2(-3)=4-3=1=1\cdot2^0+0\cdot2^1, \\ r_2(-4)=4-4=0=0\cdot2^0+0\cdot2^1. \]

For sufficiently large \(i\), one has \(2^i\ge m\), so \(-1\le-\frac{m}{2^i}<0.\) Hence \(\left\lfloor-\frac{m}{2^i}\right\rfloor = \left\lfloor-\frac{m}{2^{i+1}}\right\rfloor = -1.\)

Consequently, \(b_i(-m) = -1-2(-1) = 1.\)

Therefore a negative integer has eventually all one bits.

Why use infinite-precision semantics?¶

It is natural for arbitrary-precision integers because:

There is no arbitrary choice of 8, 16, 32, or 64 bits.
Operations do not unexpectedly overflow or discard high bits.
Widening by sign extension preserves the value.
Identities such as \(\mathord{\sim}x=-x-1\) hold for every integer.
Arithmetic right shift has the simple interpretation: \(x \mathbin{>>} n = \left\lfloor \frac{x}{2^n} \right\rfloor\)

Fixed-width two's complement is preferred in hardware-oriented languages because processors operate on fixed-size registers and fixed-size values have predictable memory and performance costs.

Definition of bitwise operations¶

Once the bits are defined, bitwise operations are defined position by position:

\[ b_i(x\mathbin{\&}y)=b_i(x)b_i(y), \\ b_i(x\mathbin{|}y)=\max\bigl(b_i(x),b_i(y)\bigr), \\ b_i(x\mathbin{\hat{}}y) = \bigl(b_i(x)+b_i(y)\bigr)\bmod 2, \\ b_i(\mathord{\sim}x)=1-b_i(x). \]

From the finite-residue definition, \(\mathord{\sim}x \equiv (2^n-1)-x \equiv -x-1 \pmod{2^n}\) for every \(n\). Therefore,

\[ \boxed{\mathord{\sim}x=-x-1}. \]

Arithmetic shifts are defined by

\[ x\mathbin{<<}k=2^k x, \\ x\mathbin{>>}k = \left\lfloor\frac{x}{2^k}\right\rfloor. \]

The right-shift identity corresponds exactly to discarding the lowest \(k\) bits while retaining the infinite sign extension.

Relation to finite two's complement¶

A 32-bit two's-complement representation keeps only \(r_{32}(x)=x\bmod 2^{32}.\)

Infinite-precision two's complement keeps the entire compatible family \(r_1(x),r_2(x),r_3(x),\ldots\) Thus it can be understood as two's-complement representation simultaneously at every possible bit width.