LeetCode菜笔记

Sum of 2 Integer

整数 a 和 b 之和 转化为 二进制 执行逻辑符号运算
例子：
a=158：1001 1110
b=87： 0101 0111
sum=245: 1111 0101
Carry:C = (a & b) <<1 = 0010 1100 (0001 0110<<1)
Sum: S= a ^ b = 1100 1001
继续对 Carry 和 Sum 求和 迭代得到新的 Carry 和 Sum, 停止条件为 Carry 为 零

需知：

1. 位运算规律
   a. 进位为 与运算 和 左移
   b. 无进位和为 异或运算

2. python 和 C++ 的整数储存规律
   在高级语言 C/JAVA/C++ 中 int 储存位长 32 bit，对于python来说, python整数类型为 Unifying Long Integers, 即无限长整数类型（24 byte). 主要差别在于 负数 和 正数的加法；
   假设 C++ 内 为 4 Bit 长度储存 求 -2 + 3，最高位 为符号位
   2原码：0010
   取反：1101
   加一： 1110 （-2）
   3：0011
   C = 0100 (位长有限， 移位直接溢出)
   S= 1101
   C= 1000 -> C= 0000
   S= 1001 -> S= 0001(结果)
   在 python中， 因为无限长整数类型的定义， 在求进位的移位运算中 将不会产生溢出，导致得不到正确 答案， 因此要限制存储位长， 取 32 位。 根据 取模 和 除法 的 定义 将两个数对 0x1 0000 0000 取模 保留0 到 31 位且第31位为符号位，最大值为 0x 7FFFF FFFF， 如果计算得到的 S 小于等于最大值 可以直接输出， 如果大于，则说明符号位为 1， 需要将其 与 0xFFFF FFFF 异或 并 取反 后输出；
   例如： S=1110 （ -2， 4 bit）
   实际输出假设为8 bit 则 S1= 0000 1110（14，8 bit） 不正确，应当取值 S2= 1111 1110 （-2， 8 bit）
   S1 -> S2 ：
   S2 = ~(S1 ^ 0xF)
   同理可推广到： 截取 32bit 输出为 无限长整数类型

3. 代码实现

• C++

int aplusb(int a, int b) {
        // a b 可以为任意整数
        int carry = 0;
        int sum_ = 0;
        
        while(b != 0){
            carry = (a & b) << 1;
            sum_ = (a ^ b);
            a = sum_;
            b = carry;
        }
        return a;
    }

• python

// 代码来自链接
def aplusb(a, b):
	while b != 0:
	    sum_ = a ^ b
	    carry = (a & b) << 1
	    a = sum_ % 0x100000000
	    b = carry % 0x100000000
	return a if a <= 0x7FFFFFFF else ~(a ^ 0xFFFFFFFF)

参考：
[1]:https://blog.csdn.net/skylake_/article/details/105858766.

本文地址：https://blog.csdn.net/zhangxin027/article/details/110914630