SUM OF TWO INTEGERS - leetcode - Python

Let's get to the core of adding two integers without using the ' ' operator. This requires binary manipulation.

We'll approach this like regular addition, but using binary.

1. Start adding from the right, just as you normally would: 1 1, 0 1, 1 0, 0 0.
2. Since we're working in binary, if the sum reaches 2, reset it to 0 (1 1 = 10 binary, becomes 0 with a carry).
3. Repeat this for all bits. This gives us a partial sum, ignoring carries for now.

The XOR (^) bitwise operator handles this initial sum perfectly:

• If bits are the same, the result is 0. If they're different, the result is 1.

This aligns with our needs: 1 1 → 0 (with a carry), 0 1 or 1 0 → 1, and 0 0 → 0.

Now, let's address the carries. The AND (&) operator helps us find them:

• If both bits are 1, the result is 1 (a carry).

To shift the carry to the left, we'll use a left bit shift.

Algorithm:

1. Initialization:
   • sum = a ^ b (XOR for sum without carry)
   • carry = (a & b) (AND for carry)
2. Iteration:
   • Repeat until carry == 0:
     • a = sum
     • b = carry << 1 (left bit shift for carry)

Example (5 3):

1. Initial Values:
2. Iteration 1:
   • sum = 0101 ^ 0011 = 0110
   • carry = 0101 & 0011 = 0001
3. Iteration 2:
   • sum = 0110 ^ 0010 = 0100
   • carry = 0110 & 0010 = 0010
4. Iteration 3:
   • sum = 0100 ^ 00100 = 0000
   • carry = 0100 & 0100 = 0100
5. Iteration 4:
   • sum = 0000 ^ 1000 = 1000
   • carry = 0000 & 1000 = 0000

The carry is 0, so the final sum is 1000 (8).

Python's unbounded integers cause issues with negative numbers. The left bit shift can lead to infinite growth. To fix this, we need to simulate fixed-size integers (e.g., 32-bit).

We'll use a 32-bit mask (0xFFFFFFFF) to limit the number of bits:

This ensures that only the last 32 bits are considered, preventing infinite growth. We also handle potential negative results by converting them to their 32-bit two's complement representation if necessary.

This approach effectively simulates 32-bit integer arithmetic within Python, resolving the issue with unbounded integers and negative numbers. The if a > MAX_INT condition ensures that the result remains within the 32-bit signed integer range. The example with -12 and -8 demonstrates how this correction works to produce the expected result of -20.

My Name is Jaimin Bariya, if you find something useful, please like and comment, and follow me on github jaimin-bariya

The above is the detailed content of SUM OF TWO INTEGERS - leetcode - Python. For more information, please follow other related articles on the PHP Chinese website!