C++二进制完成加减乘除

首先介绍计算机的二进制码

二进制常用的有原码，反码和补码，他们都是由最左边的一个符号位和右边的数值位构成。在计算机中为了更低成本的计算，数据都是用补码来存储和运算的。

原码

最高位表示符号位（0代表正数，1代表负数）。剩下的位数，是这个数的绝对值的二进制。

比如 一个int变量大小为4字节，在32位的编译器中的二进制表示就是00000000000000000000000000000000$00000000000000000000000000000000$
那么10$10$ 的原码就是00000000000000000000000000001010$00000000000000000000000000001010$
−10$-10$的原码就是 10000000000000000000000000001010$10000000000000000000000000001010$

反码

正数的反码和其原码是一样的
负数的反码就是在其原码的基础上 符号位不变 其他位取反。

10$10$的反码就是00000000000000000000000000001010$00000000000000000000000000001010$ 和原码一样
−10$-10$的反码就是11111111111111111111111111110101$11111111111111111111111111110101$

补码

正数的补码就是其原码
负数的补码就是在其反码的基础上+1$+1$

10$10$的补码就是00000000000000000000000000001010$00000000000000000000000000001010$
−10$-10$的补码就是 11111111111111111111111111111011$11111111111111111111111111111011$

总结一下

计算机系统中，数值一律用补码来表示：因为补码可以使符号位和数值位统一处理，同时可以使减法按照加法来处理。
二进制编码：数值编码分为原码，反码，补码，符号位均为0正1负。

原码 -> 补码： 数值位取反加1

补码 -> 原码： 对该补码的数值位继续 取反加1

补码 的绝对值（称为真值）：正数的真值就是本身，负数的真值是各位（包括符号位）取反加1（即变成原码并把符号位取反）.

介绍基本的位操作

^：按位异或；&$\mathrm{\&}$：按位与； |$|$ :按位或
b -> -b ： 各位（包括符号位）取反加1

用位操作实现加法运算

我们先不考虑进位，在1位数的加法上，如下
1. 1+1=0$1+1=0$
2. 1+0=1$1+0=1$
3. 0+1=1$0+1=1$
4. 0+0=0$0+0=0$
很明显上面几个表达式我们可以用异或进行统一
1. 1$1$^1=0$1=0$
2. 1$1$^0=1$0=1$
3. 0$0$^1=1$1=1$
4. 0$0$^0=0$0=0$
这样我们就完成了最基础的一位数的加法，但是怎么计算二位以上的加法呢？我们发现现在方法的问题在于不能够获取进位，于是我们通过观察一位数的加法的式子，发现只有两个数位都是1的时候才会有进位，其他都不进位，这不是和&$\mathrm{\&}$很像吗？ 我们通过把+$+$换成&$\mathrm{\&}$得到下式
1. 1&1=0$1\mathrm{\&}1=0$ 不进位
2. 1&0=1$1\mathrm{\&}0=1$ 不进位
3. 0&1=1$0\mathrm{\&}1=1$ 不进位
4. 0&0=0$0\mathrm{\&}0=0$ 进位
那么我们把所有位进行&$\mathrm{\&}$操作，然后<<$<<$左移一位，不就可以当作加数当前的进位吗？
到这里我们就完整解决了二进制相加问题中，对应位的相加和进位的问题
1. x$x$^y$y$ 加法
2. (x&y)<<1$(x\mathrm{\&}y)<<1$ 进位操作
那么总结一下：

定理1：设a$a$，b$b$为两个二进制数，则a+b=a$a+b=a$^b+(a&b)<<1$b+(a\mathrm{\&}b)<<1$。

证明：

a$a$^b$b$是不考虑进位时加法结果。当二进制位同时为1$1$时，才有进位，因此 (a&b)<<1$(a\mathrm{\&}b)<<1$是进位产生的值，称为进位补偿。将两者相加便是完整加法结果。

定理2：使用定理1可以实现只用位运算进行加法运算。

证明：

利用定理1中的等式不停对自身进行迭代。每迭代一次，进位补偿右边就多一位0$0$，因此最多需要加数二进制位长度次迭代，进位补偿就变为0$0$，这时运算结束。

那么我们可以根据上面的定理得到实际的C++代码如下

int add(int a, int b){
    int re = a;
    while(b){
        int tmp = a;
        a = a^b;
        b = (tmp&b)<<1;
        re = a;
    }
    return re;
}

用位操作实现减法

减法和加法原理相同，减去一个数相当于加上这个数的相反数，所以完全可以利用加法操作，唯一需要做的就是求出被减数的相反数。
求相反数的方法：每一位取反，末位加一。
代码如下：

int subtraction(int a, int b)
{
    b = add(~b,1); // 求b的相反数
    return add(a, b);
}

用位操作实现乘法

二进制的乘法同十进制的乘法并无什么不一样，对于a∗b$a\ast b$每次只需要将a左移对应的位，然后同上一次的结果相加即可
当b的对应位为1$1$的时候，对a左移一位相加即可
当b的对应位位0$0$的时候，对a左移一位，但是不相加
注意到我们上面的操作都是不包括符号位的，因此我们单独考虑符号位。
代码如下

int getSign(int n)
{
    unsigned count = 0;
    //计算n的位数
    do{
        ++count;
    }while(n >> count)
    //得到n的最左边的位
    return n >> (count-1);
}

int mul(int a, int b){
    bool isNegative = false;
    if(getSign(a) ^ getSigned(b))
        isNegative = true;
    if(a < 0) a = add(~a,1);//求出a的绝对值
    if(b < 0) b = add(~b,1);//求出b的绝对值
    int res = 0;
    while(b){               //当b不为0，继续循环
        if(b & 1)           //当b当前位为1 才需要加a
            res = add(res,a);
        a = a << 1;
        b = b >> 1;
    }
    if(isNegative)
        add(~res,1);
    return res;
}

二进制除法

同乘法一样，除法一样可以用减法来代替，当a≥b$a\ge b$才可以上商，在每次上一个商（也就是商值加1$1$）之后，a=a−b$a=a-b$
代码如下

int divide(int a, int b){
    if(!b)
        throw std::runtime_error("Divided can't be zero...");
    bool isNegative = false;
    bool isNegtive = false;
    if(getSign(a) ^ getSign(b))
        isNegtive = true;
    if(a < 0) a = add(~a,1);//求出a的绝对值
    if(b < 0) b = add(~b,1);//求出b的绝对值
    int res = 0;
    while(a >= b){
        res = add(res,1);
        a = subtraction(a,b);
    }
    if(isNegative)
        add(~res,1);
    return res;
}