First of all, 看了最最基本的leetcode 371 和 001 都是两个数求和这种，诚然，可以直接return a + b, 但是大部分公司显然不会满足这种答案。所以借此机会认真复习了bit manipulation，two’s complement等二进制位运算方面的知识。编码尽量采用c++, javascript, python

two’s complement补码

About binary还有关于2进制，位运算什么的

Two’s complement is the way every computer I know of chooses to represent integers. To get the two’s complement negative notation of an integer, you write out the number in binary. You then invert the digits, and add one to the result. Suppose we’re working with 8 bit quantities (for simplicity’s sake) and suppose we want to find how -28 would be expressed in two’s complement notation. First we write out 28 in binary form. 00011100 Then we invert the digits. 0 becomes 1, 1 becomes 0. 11100011 Then we add 1. 11100100 That is how one would write -28 in 8 bit binary.

Arithmetic with Two’s Complement

One of the nice properties of two’s complement is that addition and subtraction is made very simple. With a system like two’s complement, the circuitry for addition and subtraction can be unified, whereas otherwise they would have to be treated as separate operations. In the examples in this section, I do addition and subtraction in two’s complement, but you’ll notice that every time I do actual operations with binary numbers I am always adding.

位运算实现加法

用位运算实现加法也就是计算机用二进制进行运算，32位的CPU只能表示32位内的数，这里先用1位数的加法来进行，在不考虑进位的基础上，如下

1 + 1 = 0
1 + 0 = 1
0 + 1 = 1
0 + 0 = 0

很明显这几个表达式可以用位运算的“^”来代替，如下

1 ^ 1 = 0
1 ^ 0 = 1
0 ^ 1 = 1
0 ^ 0 = 0 这样我们就完成了简单的一位数加法，那么要进行二位的加法，这个方法可行不可行呢？肯定是不行的，矛盾就在于，如何去 获取进位？要获取进位我们可以如下思考：

0 & 0 = 0
1 & 0 = 0
0 & 1 = 0
1 & 1 = 1

//换个角度看就是这样

0 & 0 = 不进位
1 & 0 = 不进位
0 & 1 = 不进位
1 & 1 = 进位

正好，在位运算中，我们用“«”表示向左移动一位，也就是“进位”。那么我们就可以得到如下的表达式

//进位可以用如下表示：
(x&y)<<1 到这里，我们基本上拥有了这样两个表达式

x^y //执行加法
(x&y)<<1 //进位操作

a + b = a ^ b + ((a & b) << 1) 

代码实现

下面的代码还支持 传 负数进去… 好神奇。

#include <stdio.h>
#include <assert.h>

#define __DEBUG__       1

int MyAdd(int a, int b)
{
    /* 定理1：
     * if (0 == (a & b)) {
     *     a + b == a ^ b;
     * }
     * 换句话说就是，如果两数相加时没有进位，则加法运算可由异或运算代替。
     * 两数相与生存下来的位就是相加会向左产生进位的位，所以
     * （a & b)就可以判断两数相加会不会产生进位，而且（a & b) << 1
     * 就是所有--进位位--的进位值之和。
     * */
    /* 定理2：a + b = a ^ b + ((a & b) << 1)
     * 就是把加法拆成--每位相加的和--与--进位值--两部分相加
     * 等式右边也是加法，又可以拆，这就形成了一个递归的过程
     * 要使递归终止，需使用定理1，也就是不再有进位，定理2等式右边
     * 的加号就可以换成异或符号。
     * */

    /* 这里的a, b可视为某两个数A和B的--每位相加的和--和--进位值 */
    int cf = a & b;
    int sum = a ^ b;

    while (cf) {
        a = sum;
        b = cf << 1;
        cf = a & b;
        sum = a ^ b;
    }

    #if __DEBUG__
    assert(sum == a + b);
    #endif

    return sum;
}