Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
这是来自 leetcode 的一道经典题目——不使用+实现求和。本文将从整数（有符号和无符号）在内存的表现入手并讨论该题解法。
以上是有无符号整数的公式化表示，截图自CMU 15-213讲座视频，其中w表示该数在内存中占的bit数。
首先先了解有无符号整数的表示方法和他们的最大最小值。
无符号整数
先从最简单的无符号整数开始，以下是一个无符号整数(8bit)的二进制表示的例子。
| # | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|
| 值 | 128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| 二进制 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| x= | 0 | 64 | 32 | 0 | 0 | 4 | 0 | 0 |
| Sum | 100 |
以上是无符号整数二进制01100100的十进制值求法。从其最小位开始，设第一位值1，第二位值2……第n位值2^n。然后做一个简单的求和即可算出来其十进制值。
用 Windows 10 自带的计算器验证结果（BIN 0110 0100 == DEC 100）。
我们可以由上表推算出8位二进制可以表示的最大无符号数为0b1111 1111，即2^0+2^1+2^2+…+2^7=255；最小值当然就是0b0000 0000，即十进制0。
有符号整数（补码）
在“补码”表示的有符号整数中，人们规定把二进制的MSB(most significant bit)，即最后一位规定为符号位，具体表现是这样的：
| # | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|
| 值 | -128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| 二进制 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
| x= | 0 | 64 | 32 | 0 | 0 | 4 | 0 | 0 |
| Sum | 100 |
注意最后一位的“价值”从128变成了-128，而其它各位的“价值”保持不变，这样就在一定程度上保持了有无符号数内存表示的兼容。
由此表可得，有符号数字的最大值是0b0111 1111（除了-128的一位其它位都选上），即127，如下表所示：
#|8|7|6|5|4|3|2|1 :—–:|:—–:|:—–:|:—–:|:—–:|:—–:|:—–:|:—–:| 值|-128|64|32|16|8|4|2|1 二进制|0|1|1|1|1|1|1|1 x=|0|64|32|16|8|4|2|1 Sum|127
而有符号整数的最小值则为0b1000 0000（只选择-128这个负数“价值”的位），即-128：
| # | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
|---|---|---|---|---|---|---|---|---|
| 值 | -128 | 64 | 32 | 16 | 8 | 4 | 2 | 1 |
| 二进制 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| x= | -128 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| Sum | -128 |
∴8bit有符号整数的范围为-128~127
加法
二进制的加法其实就和十进制加法一样，列个竖式算个进位就出来了。比如说0b0010 0001 + 0b0001 0111:
0b 0010 0001 (33)
+ 0b 0001 0111 (23)
= 0b 0011 1000 (56)
有趣的是，相同的规则也能运用到有符号整数中，例如：
0b 1010 0001 (-95)
+ 0b 0001 0111 (23)
= 0b 1011 1000 (-72)
（所以说其实根本不需要知道补码是什么的吗(╯‵□′)╯︵┻━）） 那么我们只要写程序模拟这个竖式加法过程就可以了。 在此之前先介绍一下异或运算符(^)，其运算过程如下：
| A | B | A^B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
可以看到异或运算和加法运算很像，我们可以利用该运算符来模拟加法，然后只要手动处理进位就可以了。
#include <iostream>
int add(int a, int b) {
// a+b
int sum = 0;
constexpr size_t intLength = sizeof(int) * 8;
bool lcarry = false;
for (size_t i = 0; i < intLength; ++i) {
bool carry = false; // 这一位是否会产生进位
int mask = 1 << i; // 指定我们正在处理的位数
bool val = (a&mask) ^ (b&mask); // 这一位的运算结果
if ((a&mask) && (b&mask)) carry = true; // 如果两个加数这一位都是1的话就会产生进位
if (lcarry) { // 上一位有进位吗?
if (val) carry = true; // 如果上一位有进位，这一位是1的话，那这一位也会产生进位
val ^= 1; // 不然的话就加一
}
lcarry = carry;
if (val) sum |= mask; // 设置这一位的运算结果
}
return sum;
}
int main(){
int a, b;
std::cin >> a >> b;
std::cout << add(a, b) << std::endl;
}
这样我们就花了16行实现了a+b。 然而，可能你也发现了，这样实现其实在for循环里还是有一个++运算的orz 不过幸好这个加号很容易就可以去掉——我们只需要手动展开循环就可以了（逃
好吧其实还有更优雅的方式，我们可以一次性把所有位数全部运算一遍！优化过的代码如下：
#include <iostream>
int add(int a, int b) {
int carry=(a&b)<<1;
int sum=a^b;
while (carry!=0){ // 一直加到没有进位为止
int newSum=sum^carry; // 加进位
carry=(sum&carry)<<1; // 获取加进位的时候可能产生的进位
sum=newSum;
}
return sum;
}
int main(){
int a, b;
std::cin >> a >> b;
std::cout << add(a, b) << std::endl;
}