Add Two Numbers

https://leetcode.com/problems/add-two-numbers
https://leetcode.com/problems/add-two-numbers

给定两个非空链表代表两个整数，所有的数字被逆序存放在其中，所有节点只存放一位数字，将两数相加并将和返回。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        carry=0
        head=ListNode(0)
        cur=head
        while l1 or l2:
            sum_of_two_numbers=carry
            if l1:
                sum_of_two_numbers+=l1.val
                l1=l1.next
            if l2:
                sum_of_two_numbers+=l2.val
                l2=l2.next
            if sum_of_two_numbers>=10:
                carry=1
                sum_of_two_numbers=sum_of_two_numbers%10
            else:
                carry=0
            cur.next=ListNode(sum_of_two_numbers)
            cur=cur.next
        if carry==1:
            cur.next=ListNode(1)
        return head.next

Sum of Two Integers

https://leetcode.com/problems/sum-of-two-integers/
https://leetcode.com/problems/sum-of-two-integers/

给定两个整数a和b，不要用加减运算符返回他们的和。

进位carry只有在ab皆为1的情况下才会为1，使用&；对于每一位的运算遵循相同为0不同为1，使用^。

1
2
3
4
5
6
7
class Solution:
    def getSum(self, a: int, b: int) -> int:
        while b:
            c=a&b
            a=a^b
            b=(c)<<1
        return a

看似没问题，但是在处理两个正负数相加时，可能会导致死循环。

当 a 和 b 分别为正负数时，a 和 b 的符号位不同，而位运算 a&b 的结果会将符号位置为 0，使得 c 为正数。接着，a 和 b 的异或运算 a^b 的结果会将符号位置为 1，使得 a 变成了负数。然而，将 c 左移一位后赋值给 b 时，b 的符号位将变为 0，变成了正数。

这样，b 的值会不断增加，并且 a 的符号位会变为 0，导致进入死循环。

解决办法是引入一个 mask 变量来限制结果的位数，并将左移的结果与 mask 进行与运算，确保结果在限定的位数范围内。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def getSum(self, a: int, b: int) -> int:
        MAX_INT = 0x7FFFFFFF
        mask = 0xFFFFFFFF
        
        while b:
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask
            
        if a <= MAX_INT:
            return a
        else:
            return ~(a ^ mask)

首先，定义 MAX_INT 为 0x7FFFFFFF，即 32 位有符号整数的最大值。同时，mask 定义为 0xFFFFFFFF，用于限制结果的位数在 32 位有符号整数的范围内。

在循环中，首先使用 (a ^ b) & mask 对 a 和 b 进行异或运算，并将结果与 mask 进行与运算，确保结果在 32 位范围内。然后使用 ((a & b) << 1) & mask 对 a 和 b 进行与运算，并将结果左移一位，再次与 mask 进行与运算，同样确保结果在 32 位范围内。

最后，通过比较 a 是否小于等于 MAX_INT，如果小于等于，则返回 a。如果大于 MAX_INT，则说明结果溢出，需要进行补码运算来得到正确的结果。补码运算的操作是首先执行 a ^ mask 来对 a 进行取反，然后再执行 ~(a ^ mask) 来对结果进行取反，得到正确的结果。

快来参与讨论吧~