位运算算法篇：位运算实现加减乘除

位运算算法篇：位运算实现加减乘除

那么我们想必对加减乘除这些数学计算并不陌生，但是对于我们的计算机来说，由于机器只能识别二进制的语言，那么我们底层的数据都是以二进制的形式存在，那么我们CPU的计算器的加减乘除运算肯定都是通过位运算的方式来实现的，那么本篇文章就是用位运算来实现我们的加减乘除运算，那么废话不多说，我们进入正文

1.加法运算

那么在我们的现实生活中我们熟悉我们十进制的加法运算，运算规则就是对应的十进制位进行相加，然后逢十进一，进位到下一位上去，而由于我们计算机的各种数据都是以二进制序列的形式存在，所以我们的加法运算实际上就是要实现二进制的加法运算。

那么要实现二进制的加法运算的话，我们首先得知道二进制加法运算的规则，那么二进制加法运算的规则就是对应二进制位相加，逢二进一，那么这里我们只能通过我们的位运算来实现，那么我们的位运算无非就是与，或，非以及异或运算等等，那么我们怎么通过这些位运算来实现我们加法运算的一个逻辑呢。

其中异或运算我专门花了一片文章来讲解异或运算的原理以及应用，那么我们知道异或运算的本质就是无进位相加，那么对于实现我们二进制的加法运算，那么我们可以采取这样的一个思路，那么我们知道我们两个数进行异或运算就相当于两个数进行一个无进位相加的加法运算，那么此时我们这里进行完一次异或运算，我们相当于得到了每个对应二进制位相加的结果，但是唯独每一个二进制位没有加上进位信息，那么也就意味着只要我们将我们异或运算的结果得到的二进制序列的每一位再对应加上进位信息，那么就是我们的正确结果。

那么这里的进位信息，我们知道只有两个二进制位都为1那么会产生进位，所以这里我们假设我们a和b两个数做加法运算，那么我们要得到a+b的进位信息的话，我们可以a & b，那么与运算的规则是对应二进制位都为1结果才能为1，只要有一个二进制位为0结果就为0，那么我们a&b的结果会得到一个二进制序列，那么这个二进制序列的每一位的0和1就表示该二进制位相加如果有进位，那么该二进制位就是1,反之为0,。

那么我们实现加法运算的最后关键一步就是刚才异或运算无进位相加的结果再异或上与运算的进位信息即可，但是与运算得到的二进制序列中的0和1表示是该二进制位是否有进位，但是实际要相加的话，因为进位是要进到下一位，所以我们就得将与运算的二进制序列给左移一位，然后加上异或运算的序列。

那么可能有的读者就有疑问，那么我们加完万一还会有进位怎么办，比如：假设是4个二进制位的两个数相加

1011+0001，这里我们最低位会产生一个进位到第二位，那么第二位加上我们的进位又会产生一个进位，而我们刚才的思路的话，我们将1011与0001先异或运算得到1010，然后将1011与0001在与运算得到0001，然后左移一位得到0010，那么我们将刚才得到的异或运算的结果1010在与我们与运算右移的结果再进行异或：1010 ^ 0010 = 1000,但是我们知道1011+0001的答案实际上是1100.

所以此时将我们的刚才计算的结果1000与之前的与运算右移的结果0010重新作为新的两个加数，异或完后得再一次与运算一下，确定运算的结果是否为0，如果不为0，说明还有进位，那么就得在加上之前的进位信息，所以重复之前的步骤，先异或，再与运算然后左移，再异或：

1000 ^ 0010 =1010

(1000 & 0010)<<1=0000

1010 ^ 0000 =1010

那么我们此时将我们的结果1010和0000重新作为加数，但是我们如果得到进位信息为0，也就是没有进位，那么我们计算就结束，那么这里就是我们代码设计循环的一个终止条件。

代码实现：

#include<iostream>
using namespace std;
int add(int a,int b)
{while(b!=0){a=a^b;b=(a&b)<<1;}return a;
}
int main()
{int a=10,b=30;cout<<a<<"+"<<b<<"="<<endl;int res=add(a,b);cout<<res<<endl;	
}

2.减法运算

那么我们在位运算的第一篇就讲到过，由于负数的补码专门进行了处理，所以一个数减去一个数，可以看成一个数加上该数的负数，那么我们减法运算就可以应用我们加法运算的逻辑，这里注意一个正数得到负数我们就取反加一即可：

#include<iostream>
using namespace std;
int add(int a,int b)
{while(b!=0){int carry=(a&b)<<1;a=a^b;b=carry;}return a;
}
int main()
{int a=10,b=30;cout<<a<<"-"<<b<<"="<<endl;int res=add(a,(~b)+1);cout<<res<<endl;	
}

3.乘法运算

那么我们对于十进制的乘法运算我们十分熟悉，那么可能对于二进制的乘法运算的话我们就显得稍微有点陌生，那么我们二进制的乘法运算和我们十进制的乘法运算的运算规则是一样的，也就是每一个二进制位来与另一个数相乘。

以四位二进制数为例

1001

0110

————

​ 0

1001

1001

​ 0

————

​ 011 0

那么我们则如何实现我们乘法运算的这套逻辑呢，那么我们知道我们乘法运算的话，那么如果该二进制位是1，那么则是另一个乘数本身，反之如果是0，那么则是0，所以我们要现将这个乘数的每一个二进制位来判断，所以得将其与1进行与运算判断该位置是0还是1，然后将下一个要判断的二进制位移到最低位，然后我们要将另一个乘数给左移同样的步数，因为左移之后右边是用0来补，所以我们左移完的结果在与之前的数相加即可

代码实现：

#include<iostream>
using namespace std;
int mulpitly(int a,int b)
{int i=0;int res=0;while(a!=0){int ant=a&1;if(ant!=0){res+=(b<<i);}i++;a=a>>1;}return res;
}
int main()
{int a=10,b=30;cout<<a<<"*"<<b<<"="<<endl;int res=mulpitly(a,b);cout<<res<<endl;	
}

4.除法运算

那么我们除法运算是我们加减乘除这4个运算中最难实现的一个运算，其中难于实现的原因就是很多人它不知道我们二进制的除法的规则是什么，那么你要问我是具体怎么实现我们的除法运算，那么我的思路不是从我们除法本身的规则除法，那么我们在实现除法运算之前，我们前面已经有了我们的加法以及减法和乘法运算，那么我们谁说一定就要按照二进制本身除法的运算规则去实现它，我们可以转换为我们的乘法以及加法来实现我们的除法。

那么可能读者看到这还是内心里还是有点疑惑，那么我接着将一步阐述我实现除法的一个原理：

那么我们假设我们有两个不同的数比如a和b，那么我们a与b做除法运算，那么这里我们假设a是被除数，b是除数，并且a不是整除b的，我们除法运算不就是要得到a/b的尚以及余数吗？那么我们知道a/b会得到一个商和余数，那么意味着我们a除以b我们可以写成：a=b*商+余数

那么现在我们首先求这个商的值，那么我们知道我们任何一个数本质上都是一个二进制序列，那么同理我们的商本质也是一个由0和1组成的二进制序列，那么我们假设我们的数是8个二进制位，那么如果说我们的商是01000111，那么我们知道我们a=b*商+余数，那么我们可以将我们这个商根据它的二进制序列将我们的原式转换成这样的形式：$$a=b\ast (2^6+2^2+2^1+2^0)+余数$$
那么我们求这个商的值是多少，我们知道我们的商本质是一个二进制序列，那么我们求商实际上就是可以转换为确定商的二进制序列中哪些位置为1，只要把所有二进制位为1的位置确定，那么商的二进制序列我们就知道了，那么商的值自然也就知道了，那么我们确定我们二进制为1的位置

那么现在的思路就是怎么确定商的二进制序列的1会出现在哪些位置呢，那么我的策略就是先依次确定该二进制序列最左侧的1出现的位置是哪里：

假设被除数是a，除数是b，那么对于一个有符号整形的数来说，最高位是符号位，那么其余剩下是数值位，那么对于一个int类型含有32个二进制位的数来说，那么它的最高位就是第31位，因为第32位是符号位，那么我们就假设该二进制序列中最左侧的1在第31位，那么直到我们a除以b得到商或者余数，也就意味着除数b乘以商是一定等于或者小于我们的被除数的，那么如果满足该位置是最左侧的1的话，那么我们二进制序列的第31位为1的得到数比如c乘以我们的除数b，它一定是小于等于我们的被除数a的，那么如果不满足，也就是说该二进制位为1的数乘以除数b大于了我们的被除数a，那么我们知道该二进制位肯定不可能为1，只能为0，那么最左侧的1肯定不在第31位，那么我们就依次右移讨论，那么直到讨论到二进制位为1的该数c乘以b它小于等于我们的被除数a，那么意味着该最左侧的二进制位为1的位置在该位置，那么我们就记录，然后我们在用被除数减去除数a乘以c，然后这个数作为我们的被除数，因为我们a/b可以写成:
$$a=b\ast (2^6+2^2+2^1+2^0)+余数$$
也就是
$$a=b\ast 2^6+a\ast 2^2+a\ast 2^1+a\ast 2^0+余数$$
最后转换成：
$$a-b\ast 2^6=a\ast 2^2+a\ast 2^1+a\ast 2^0+余数$$
那么确定剩余的为1的二进制位，那么重复刚才的思路，直到最后被除数如果不为0，那么该被除数就是余数。

代码实现：

#include<iostream>
using namespace std;
void chufa(int& a,int& b)
{int res=0;for(int i=29;i>=0;i--){if(a==0){break;}long long ant=(long long)b*(1<<i);if(a>=ant){res+=(1<<i);a-=ant;}}b=res;return;
}
int main()
{int a=280,b=25;cout<<a<<"/"<<b<<"="<<endl;chufa(a,b);cout<<b<<" "<<a<<endl;return 0;	
}