Jaimin Bariya

Posted on Jan 22

371 SUM OF TWO INTEGERS - leetcode - Python

#learning #python #programming #datastructures

Let's come to the point

We have to perform sum without using the + operator. So developers first thoughts, say -> I guess,` have to use binary manipulation, which is correct.

Let's think more about this approach.

Do this like normal numbers

start summing from the right side as usual, 1 + 1, 0 + 1, 1 + 0, and 0 + 0.
because we are doing with binary, if the number goes to 2 (sum) then make it 0 [like 1 + 1 -> 2 but we can not exceed 0 to 1]
Do this with all numbers, we gate half answer, why because we did not care about carry numbers 😁

this task can done by using the XOR bitwise operator,

Rule of XOR Operator

if bits are the same then -> 0, and if bits are different then -> 1

This matches our need because we have to do 1 + 1 -> 0 and 0 + 1 or 1 + 0 -> 1 (do the usual sum 🤘). and 0 + 0 -> 0 [Based on XOR Rule - Same number than 0 and also usual 0 + 0 -> 0]

Cary your Carry Numbers [think little for them]

Usually, we pass carry to the left number, read it again, I said pass carry to the left number, Here developer's first thinking suggests about using shift operators like << and >>.

But, How we get carry number, for that, think more about and (&) operator.

And & Operator rule said -> if both bits are 1 then result is 1, Great we get carry for those where both bits are 1.

To shift this to the left, we will use << left shift operator. example 0001 << 1 -> 0010

Okay, Enough story building, now let's go to the algorithm

Algorithm:

Initial Step:
- sum = a ^ b (This is the XOR to get the sum without carry)
- carry = (a & b) << 1 (This is the AND to get the carry, shifted left)
Repeat:
- Until carry == 0, update a and b as:
  - a = sum
  - b = carry

In each iteration, you compute the new sum and carry, until the carry becomes zero.

Example:

Let’s walk through the example of adding 5 and 3 step by step.

Initial Values:
First iteration:
- sum = a ^ b = 0101 ^ 0011 = 0110 (sum without carry, which is 6)
- carry = (a & b) << 1 = (0101 & 0011) << 1 = 0001 << 1 = 0010 (carry of 2)

So now:

Second iteration:
- sum = a ^ b = 0110 ^ 0010 = 0100 (new sum, which is 4)
- carry = (a & b) << 1 = (0110 & 0010) << 1 = 0010 << 1 = 0100 (carry of 4)

Now:

Third iteration:
- sum = a ^ b = 0100 ^ 0100 = 0000 (new sum, which is 0)
- carry = (a & b) << 1 = (0100 & 0100) << 1 = 0100 << 1 = 1000 (carry of 8)

Now:

Fourth iteration:
- sum = a ^ b = 0000 ^ 1000 = 1000 (final sum, which is 8)
- carry = (a & b) << 1 = (0000 & 1000) << 1 = 0000 << 1 = 0000 (carry is now 0)

Now, the carry is 0, so we stop, and the final result is 8.

Pseudocode Thought Process

Use XOR to add without carry.
Use AND + shift to compute the carry.
Keep updating the result with XOR and carry until the carry becomes 0.

Okay, perfect, we done it. but when I run this, I got TLE error.

I got this error just because I am using Python for this manipulation, I will teach you why, and how to resolve this, but see what happens when I code in C++, jaimin bariya, SUM OF TWO INTEGERSImage description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/k4u0x5sydlmfeyf8pdyc.png)
It is working, but if you are also using python for DSA like me, then congratulation, we have a chance to learn something new here.

New Chapter begins

We got this issue because python is unbounded, and it works well with positive integer but make problem with negative integer like we have shown in image,

So, the main issue arises when working with negative numbers in Python because integers in Python are unbounded, unlike in many other programming languages where integers are represented using fixed bits (e.g., 32-bit or 64-bit integers).

What’s Happening in the Code:

In your implementation, you're calculating carry as:

a & b: This finds the bits where both a and b are 1.
<< 1: This shifts all bits of the result left by 1 position to simulate carrying them over for addition.

The Problem with Negative Numbers in Python:

Infinite Precision Integers:
- Python's integers are not fixed-size like in many other languages (e.g., 32-bit or 64-bit integers).
- Instead, Python integers can grow in size as needed, meaning there's no limit to the number of bits used to represent a number.
Sign Bit Behavior:
- In fixed-size integers (e.g., 32-bit), the most significant bit (MSB) is reserved as the sign bit:
  - 0 = Positive number
  - 1 = Negative number (two's complement form)
- In Python, there’s no fixed MSB to act as the sign bit because integers are unbounded. Negative numbers are stored in two's complement form but don’t have a fixed number of bits.
Infinite Carry Growth:
- When working with negative numbers, the & operation can produce bits beyond the expected range.
- When you shift left (<<), these bits can keep growing indefinitely.
- For example:

(a & b) produces a bit pattern that keeps extending.
<< 1 shifts the bits left, growing the number further.
This can lead to an infinite loop because the condition b != 0 never resolves.

Why Fixed-Size Integers Avoid This:

In a 32-bit integer, bits are confined to 32 positions.
Shifting left (<<) causes overflow (bits outside the range are discarded).
This keeps the calculation bounded, ensuring the loop terminates.

Fix in Python:

To prevent infinite growth, you can simulate fixed-size integers using a mask to limit the bits:

This ensures:

Only the last 32 bits are considered.
The calculation doesn’t grow indefinitely.

Key Takeaway:

Because Python integers are unbounded, operations like & and << on negative numbers can create infinite precision values, causing your loop to run forever. Using a mask helps simulate fixed-size integer behavior to avoid this issue. 🚀

Challenges with Negative Numbers

When performing bitwise operations on negative numbers in Python, the lack of a fixed bit-width can lead to unexpected results. For example, the left shift operation << can cause the number to grow indefinitely, leading to a Time Limit Exceeded (TLE) error in competitive programming or coding platforms.

Solution

To handle negative numbers correctly, you can simulate a fixed bit-width environment. Here's how you can modify your function to work within a 32-bit integer range:

Explanation

MASK: 0xFFFFFFFF is a 32-bit mask (all bits set to 1). Applying & MASK ensures that we only consider the last 32 bits of the result, effectively simulating a 32-bit integer.
MAX_INT: 0x7FFFFFFF represents the maximum positive value for a 32-bit signed integer.
Handling Negative Results: If the result a exceeds MAX_INT, it indicates a negative number in 32-bit two's complement form. To convert it to a Python negative integer, we use the bitwise complement operator ~ in conjunction with ^ MASK.

The code if a > MAX_INT: a = ~(a ^ MASK) ensures that a stays within the 32-bit signed integer range.

What Happens:

a ^ MASK: Flips all the bits of a (simulate overflow).
~(...): Converts the flipped result back into a negative number (32-bit two's complement).

This handles overflow caused by Python's unbounded integers, making sure a behaves like a 32-bit signed integer.

For example:

If a = 2147483648 (overflowed), it becomes -2147483648 after this operation.

Example with negative number

Let's break it down using your specific example where:

a = -12
b = -8

The goal is to compute a + b using the bitwise operations in 32-bit integer arithmetic. Let's see why the output differs and how the if a > MAX_INT condition fixes it.

Step-by-Step Explanation

Initial Values

a = -12 → In 32-bit signed representation: 0xFFFFFFF4
b = -8 → In 32-bit signed representation: 0xFFFFFFF8

Bitwise Addition Logic

First Iteration:
- sum = a ^ b:
  - a ^ b = 0xFFFFFFF4 ^ 0xFFFFFFF8 = 0xFFFFFFFC
- carry = (a & b) << 1:
  - a & b = 0xFFFFFFF4 & 0xFFFFFFF8 = 0xFFFFFFF0
  - carry = 0xFFFFFFF0 << 1 = 0xFFFFFFE0
Update a and b:
- a = sum = 0xFFFFFFFC
- b = carry = 0xFFFFFFE0

Repeat Until `b == 0`

Second Iteration:
- sum = a ^ b:
  - a ^ b = 0xFFFFFFFC ^ 0xFFFFFFE0 = 0x0000001C
- carry = (a & b) << 1:
  - a & b = 0xFFFFFFFC & 0xFFFFFFE0 = 0xFFFFFFE0
  - carry = 0xFFFFFFE0 << 1 = 0xFFFFFFC0

Update:
- a = sum = 0x0000001C
- b = carry = 0xFFFFFFC0

Third Iteration:
- Keep repeating this process until b = 0.

Final Result in Python

After the loop ends, the raw value of a is 0xFFFFFFEC, which is 4294967276 in Python because Python treats it as an unbounded integer.

Adjusting for 32-bit Signed Range

To ensure the result fits into a 32-bit signed integer range, we do:

Define constants:
- MAX_INT = 0x7FFFFFFF (2147483647)
- MASK = 0xFFFFFFFF (all bits set to 1)
Handle Overflow:
- If a > MAX_INT, we convert it back to its negative form: python a = ~(a ^ MASK)
- Here:
  - a = 4294967276 (decimal)
  - a ^ MASK = 4294967276 ^ 0xFFFFFFFF = 0x13 (decimal 20)
  - ~(a ^ MASK) = ~0x13 = -20

Final Output

The corrected result after handling overflow is:
- a + b = -20

This step ensures the output matches the expected value in 32-bit arithmetic.

Why the Condition Exists

Without the if a > MAX_INT logic, Python's integers overflow to large positive numbers (e.g., 4294967276 instead of -20). This condition ensures we bring the result back into the 32-bit signed range, making it behave like a real 32-bit system.

Simple and done! 😊

My Name is Jaimin Bariya, if you find something useful give all 5 likes plz, and throw a comment below, and Follow me on github jaimin-bariya

Top comments (2)

Jaimin Bariya • Jan 22

DEV Community

371 SUM OF TWO INTEGERS - leetcode - Python

Do this like normal numbers

Rule of XOR Operator