Python LintCode：A + B问题，最详原理

本文主要是介绍Python LintCode：A + B问题，最详原理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Python LintCode：A + B问题，最详原理

- 概述
- 如何用高级语言实现
- 简单说一下
- 参考链接

概述

该题中要求不使用加法运算符，那么我们就需要思考"+"运算符是如何实现的，我们先看在数电中加法是如何实现的，如下图所示(半加器结构)。
加法器，由一个异或门和与门组成

可以看出，加法器由一个异或门(上) 和一个与门(下) 组成，S为计算和，C为计算中产生的进位。那么这个时候我们就需要考虑使用位运算来完成上述题目。
我们举一个实际的例子来说明(假设用一个byte存储整数)：2 + 9

2 + 9(对应于A + B)
2对应的二进制可以表示为0000 0010
9对应的二进制可以表示为0000 1001

正常情况下，我们在做加法的时候，对应位相加，如果有进位则加上进位，计算出最终结果时进位为0。
①对于2 + 9，我们先考虑无进位加法，个位相加和2 + 9 = 1，所以S = 1，只考虑进位加法：2 + 9 个位产生了进位，所以进位1在十位，个位为0，即C = 10。以此方法可以推广到更高位。
②此时，我们让A = S，B = C，再次计算，个位相加为1 + 0为1，十位相加为0 + 1为1，所以最终结果为11，因为个位和十位均无进位产生，所以C = 0。

我们再举一个实际的例子来说明(十进制数)：29 + 73

29 + 73(对应于A + B)
29对应的二进制可以表示为0001 1101
73对应的二进制可以表示为0100 1001

①对于29 + 73，我们先考虑无进位加法，个位相加和9 + 3 = 2，十位相加为2 + 7 = 9，所以S = 92，只考虑进位加法：9 + 3 个位产生了进位，十位2 + 7并无进位产生，所以C = 10。
②此时，我们让A = S，B = C，再次计算，个位相加为2 + 0为2，十位相加为9 + 1为0，所以最终结果为2，十位产生了进位，所以C = 100。
③再次令A = S，B = C，再次计算，个位相加为2 + 0，十位为0，百位为1，最终结果S = 102，各个位均无进位产生。所以C = 0，此时结束计算，最终结果即为102。
通过上面两个例子可以知道，只要C不为0时，循环执行①②步骤，最终结果即为S。那么既然要用位运算，不可避免的要使用二进制数，那么适用于十进制的方法是否也适合二进制，我们继续采样上述例子(2 + 9)：
0000 0010 + 0000 1001在不考虑进位的情况下，其结果为0000 1011，那么这个结果即为二进制下无进位加法，也等价于A ^ B(A与B的异或)
只考虑进位的情况下：观察上述二进制码，我们发现各个位都没有进位，因此C = 0，此时加法的结果位S = 0b1011 = 11

对于29 + 73这个例子
首先考虑无进位加法，0001 1101 + 0100 1001结果为S = 0101 0100(即A ^ B)，只考虑进位加法C = 0001 0010，我们发现这个C的值恰好为(a & b) << 1，即A与B相与后，左移一位。
接下来执行A = S，B = C，继续，那么无进位加法S = 0100 0110， C = 0010 0000，继续执行A = S，B = C，无进位加法S = 0110 0110，C = 0000 0000，此时进位为0，那么S即为最终结果S = 0110 0110 = 102。
以上四个例子(2个十进制和2个二进制)主要说明了一个算法的流程，在十进制下如何进行，二进制下如何进行，总结上述方法的过程如下：

对于给定的A B整数值，通过位运算进行加法运算
步骤①：S = A ^ B
步骤②：C = (A & B) << 1
步骤③：如果C不为0，执行A = S，B = C，然后重复执行步骤①和步骤②

如何用高级语言实现

通过概述一栏中的描述，我们已经知道了位运算的这样一个过程，但是请注意，我在举例子的时候提到过我们使用一个byte来存储，我们可以很快的计算出最终的结果(因为C中的左移操作可以很快完成)，在C或者C++、Java等高级语言中，int类型值得存储使用4个字节，一共32位，这里用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中，同样代码只能进行正整数与正整数的加和计算，如果A与B存在负数，那么程序会进入死循环，这是由Python对int的储存机制造成，那么我先上正确的代码，然后解释为什么要这么写

def aplusb(a, b):while b != 0:sum_ = a ^ bcarry = (a & b) << 1a = sum_ % 0x100000000b = carry % 0x100000000return a if a <= 0x7FFFFFFF else ~(a ^ 0xFFFFFFFF)

在python中，int类型并不是4 bytes存储，而是24 bytes，可以认为python中的int支持无限长的整型值，这样的话会导致进位在左移时永远不会溢出，也就是永远无法获得最终的结果，所以我们需要手动去模拟边界，32bit的最大值为 $2^{32} - 1$ ，也就是说32bit的支持的整数长度为 $2^{32}$ ，写成二进制为0x100000000，这样的话通过取模运算，就可以将A与B的值限制在32bit可以表示的集合中，那么我们将正整数集合划分为[-0x10000000, 0x7FFFFFFF]这样两部分，可以类似于8bit的范围为[-128, 127]，最大值为255，一共可以表示256个数，这样构造结束之后，当C = 0时，只要A的值小于等于最大值0x7FFFFFFF，那么就可以直接返回，而对于大于0x7FFFFFFF，可知其最高位必为1，我们需要对其进行处理，将其符号位提取出来。

再举一个简介明了的例子，比如我们用4 bit来存储一个int值，假如这个值为-2，其二进制为1110，如果我想把这个值转换为8 bit类型的值，应该如何做呢？这里我们需要知道的是，负数的二进制表示为正数的补码形式。
**我们先看-2在8 bit中如何表示：
2的原码：0000 0010
2的反码：1111 1101
2的补码：1111 1110 (8bit中，-2的二进制表示) **

而0000 1110在8bit中对应的值是14，我们需要将其转换，首先将 0000 1110 与 0xF做异或操作，结果为0000 0001，然后取反1111 1110，这样的话，就将4bit中的-2转换为8bit中的-2了，总结下来就两步：
① 将4bit中的结果与0xF异或
② 将异或的结果取反

可以将其扩展至32位，只要将结果与0xFFFFFFFF做异或运算，然后取反即可。如果说这个你没看懂，那我再写一个推理，如下：

1111 1110(8bit，-2的二进制表示) 8bit转16bit

原码：0000 0000 0000 0010 (2的原码)
反码：1111 1111 11111 1101
补码：1111 1111 1111 1110 (16bit的 -2的表示)

0000 0000 1111 1110 (16bit的 -2的表示)
0000 0000 1111 1111 (0xFF)
异或：0000 0000 0000 0001
取反：1111 1111 1111 1110 (8bit转16bit的结果)

1111 1111 1111 1110 (16位 -2的表示) 转8bit的-2 (1111 1110)

1111 1111 1111 1110 (16位 -2的表示)
0000 0000 1111 1111 (0xFF)

异或：1111 1111 0000 0001
取反：0000 0000 1111 1110
结果：1111 1110 与上述结果一致

Python的int存储机制，使得我们要从高位转低位，所以当我们要转换位32bit的表示时，需要与0xFFFFFFFF做异或然后取反即为最终结果。