目录
计算机最基本的操作单元是字节(byte)，一个字节由8个位(bit)组成，一个位只能存储一个0或1，其实也就是高低电平。无论多么复杂的逻辑、庞大的数据、酷炫的界面，最终体现在计算机最底层都只是对0101的存储和运算。
加法
不考虑进位情况下，位的异或运算跟求'和'的结果一致：
异或 1^1=0 1^0=1 0^0=0
求和 1+1=0 1+0=1 0+0=0
位的与运算跟求'进位‘的结果也是一致：
位与 1&1=1 1&0=0 0&0=0
进位 1+1=1 1+0=0 0+0=0
举个例子：
13 + 9 = 22
我们像这样来拆分这个运算过程：
不考虑进位，分别对各位数进行相加，结果为sum：
个位数3加上9为2；十位数1加上0为1； 最终结果为12；
只考虑进位，结果为carry：
3 + 9 有进位，进位的值为10；
如果步骤2所得进位结果carry不为0，对步骤1所得sum，步骤2所得carry重复步骤1、 2、3；如果carry为0则结束，最终结果为步骤1所得sum：
这里即是对sum = 12 和carry = 10重复以上三个步骤，(a) 不考虑进位，分别对各位数进行相加:sum = 22; (b) 只考虑进位: 上一步没有进位，所以carry = 0； (c) 步骤2carry = 0，结束，结果为sum = 22.
我们发现这三板斧行得通！
那我们现在还使用上面的三板斧把十进制运算放在二进制中看看是不是也行的通。
13的二进制为0000 1101，9的二进制为0000 1001:
不考虑进位，分别对各位数进行相加：
sum = 0000 1101 + 0000 1001 = 0000 0100
考虑进位：
有两处进位，第0位和第3位，只考虑进位的结果为：
carry = 0001 0010
步骤2carry == 0 ?，不为0，重复步骤1 、2 、3；为0则结束，结果为sum：
本例中，
(a)不考虑进位sum = 0001 0110;
(b)只考虑进位carry = 0;
(c)carry == 0，结束，结果为sum = 0001 0110
转换成十进制刚好是22.
我们发现，适用于十进制的三板斧同样适用于二进制！仔细观察者三板斧，大家能不能发现其实第一步不考虑进位的加法其实就是异或运算；而第二部只考虑进位就是与运算并左移一位–；第三步就是重复前面两步操作直到第二步进位结果为0。
这里关于第三步多说一点。为什么要循环步骤1、 2、 3直到步骤2所得进位carry等于0？其实这是因为有的数做加法时会出现连续进位的情况，举例：3 + 9，我们来走一遍上述逻辑：
C++代码：
//非递归写法
int Add(int num1, int num2)
{
int n1,n2;
n1=(num1&num2)<<1;
n2=num1^num2;
while(n1&n2)
{
num1=n1;num2=n2;
n1=(num1&num2)<<1;
n2=num1^num2;
}
return n1|n2;
}
//递归写法
int add(int num1,int num2)
{
return num2?add(num1^num2,(num1&num2)<<1):num1;
}
减法
问题：负数在计算机中是怎么表示的？
8在计算机中表示为二进制的1000，那-8怎么表示呢？
很容易想到，可以将一个二进制位（bit）专门规定为符号位，它等于0时就表示正数，等于1时就表示负数。比如，在8位机中，规定每个字节的最高位为符号位。那么，+8就是00001000，而-8则是10001000。这只是直观的表示方法，其实计算机是通过2的补码来表示负数的，那什么是2的补码（同补码，英文是2’s complement，其实应该翻译为2的补码）呢？它是一种用二进制表示有号数的方法，也是一种将数字的正负号变号的方式，求取步骤：
第一步，每一个二进制位都取相反值，0变成1，1变成0（即反码）。
第二步，将上一步得到的值（反码）加1。
我们知道，减法与加法运算互为逆运算，当我们求a-b，其实是求[a-b]补。因为有[a-b]补=[a]补 - [b]补= [a]补+[-b]补。所以我就要先求出-b。求一个数的负的操作是将其连符号位一起取反然后加1。于是有办法做减法了：先把减数求负，然后做加法。
int subtraction(int a, int b)
{
return add(a, add(~b, 1));
}
乘法
前边已经讲过了加法运算和减法运算的实现，而乘法运算可以转化为加法运算，但是需要考虑符号问题。
因此乘法运算分为两个部分。
1）计算绝对值乘积；
2）根据同正异负，确定符号位。
根据以上总结写出代码：
int multiply(int a, int b){
// 取绝对值
int multiplicand = a < 0 ? add(~a, 1) : a;
int multiplier = b < 0 ? add(~b , 1) : b;// 如果为负则取反加一得其补码，即正数
// 计算绝对值的乘积
int product = 0;
int count = 0;
while(count < multiplier) {
product = add(product, multiplicand);
count = add(count, 1);// 这里可别用count++，都说了这里是位运算实现加法
}
// 确定乘积的符号
if((a ^ b) < 0) {// 只考虑最高位，如果a,b异号，则异或后最高位为1；如果同号，则异或后最高位为0；
product = add(~product, 1);
}
return product;
} 上面的思路在步骤上没有问题，但是第一步对绝对值作乘积运算我们是通过不断累加的方式来求乘积的，这在乘数比较小的情况下还是可以接受的，但在乘数比较大的时候，累加的次数也会增多，这样的效率不是最高的。我们可以思考，如何优化求绝对值的乘积这一步。
第二种思路：二进制乘法！
这一过程就是根据乘数的每一位为0或1时，将被乘数错位的加在积上。时间复杂度为O(logN)。
(1) 判断乘数是否为0，为0跳转至步骤(4)
(2) 将乘数与1作与运算，确定末尾位为1还是为0，如果为1，则相加数为当前被乘数；如果为0，则相加数为0；将相加数加到最终结果中；
(3) 被乘数左移一位，乘数右移一位；回到步骤(1)
(4) 确定符号位，输出结果；
int multiply(int a, int b) {
//将乘数和被乘数都取绝对值
int multiplicand = a < 0 ? add(~a, 1) : a;
int multiplier = b < 0 ? add(~b , 1) : b;
//计算绝对值的乘积
int product = 0;
while(multiplier > 0) {
if((multiplier & 0x1) > 0) {// 每次考察乘数的最后一位
product = add(product, multiplicand);
}
multiplicand = multiplicand << 1;// 每运算一次，被乘数要左移一位
multiplier = multiplier >> 1;// 每运算一次，乘数要右移一位（可对照上图理解）
}
//计算乘积的符号
if((a ^ b) < 0) {
product = add(~product, 1);
}
return product;
} 第二种方法要优于第一种方法。
除法
根据乘法运算的第一种思路，很多人想到把除法运算转换成减法运算，即不停的用除数去减被除数，直到被除数小于除数时，此时所减的次数就是我们需要的商，而此时的被除数就是余数。这里需要注意的是符号的确定，商的符号和乘法运算中乘积的符号确定一样，即取决于除数和被除数，同号为证，异号为负；余数的符号和被除数一样。
int division(int a, int b)
{
if (b == 0)return 0;
bool flag = true;
if ((a^b) > 0) flag = false;
a = (a < 0) ? add(~a, 1) : a;
b = (b < 0) ? add(~b, 1) : b;
int n = 0;
a = subtraction(a, b);
while (a >= 0)
{
n = add(n, 1);
a = subtraction(a, b);
}
if (flag)
return add(~n, 1);
return n;
} 这种方法很容易想到，算法时间复杂度为O(N)。但是当被除数非常大，除数非常小，那就需要进行很多的减法运算。简单地说，就是减的太慢了，得找个方法让它加速一下。
于是采用类似二分法的思路，从除数*最大倍数开始测试，如果比被除数小，则要减去，下一回让除数的倍数减少为上一次的一半，当倍数为1时，就把被除数中所有的除数减去，并得到商。时间复杂度优化到O(logN)。
计算机是一个二元的世界，所有的int型数据都可以用[2^0, 2^1,…,2^31]这样一组基来表示（int型最高31位）。不难想到用除数的2^31,2^30,…,2^2,2^1,2^0倍尝试去减被除数，如果减得动，则把相应的倍数加到商中；如果减不动，则依次尝试更小的倍数。这样就可以快速逼近最终的结果。
2的i次方其实就相当于左移i位，为什么从31位开始呢？因为int型数据最大值就是2^31啊。
int divide(int dividend, int divisor) {
bool flag = true;
if ((dividend^divisor)>0) //积的符号判定
flag = false;
int x = (dividend < 0) ? add(~dividend, 1) : dividend;
int y = (divisor < 0) ? add(~divisor, 1) : divisor;
int ans = 0;
int i = 31;
while (i >= 0)
{
//比较x是否大于y*(1<<i)=(y<<i)，避免直接比较，因为不确定y*(1<<i)是否溢出
if ((x >> i) >= y) //如果够减
{
ans = add(ans, (1 << i));
x = subtraction(x, (y << i));
}
i = subtraction(i, 1);
}
if (flag)
return add(~ans, 1);
return ans;
} 欢迎关注我的个人订阅号，微信扫码！
参考文献：https://blog.csdn.net/ojshilu/article/details/11179911#commentBox
京公网安备 11010502036488号