当前位置：首页 > article >正文

大一计算机的自学总结：位运算实现加减乘除

article 2025/1/31 23:59:57

前言

位运算当然可以用来实现加减乘除。

一、加法

#include<bits/stdc++.h>
using namespace std;

int add(int a,int b)
{
	int ans=a;
	while(b!=0)
	{
		ans=a^b;
		b=(a&b)<<1;
		a=ans;
	}
	return ans;
}

int main()
{
	int a,b;
	cout<<"a,b:"<<endl;
	cin>>a>>b;
	
	cout<<add(a,b);
	
	return 0;
}

加法的原理就是利用了异或运算的本质：无进位加法再加上进位信息所得。

先让ans=a，然后只要b不等于0，先取两数的异或，即无进位加法；之后取两数进位信息，若两数在相同数位上都为1，所以该位进位，就是a&b。然后为了将进位信息加到ans中，要将a&b的的结果左移一位，直到两数没有进位信息。

二、减法

#include<bits/stdc++.h>
using namespace std;

int add(int a,int b)
{
	int ans=a;
	while(b!=0)
	{
		ans=a^b;
		b=(a&b)<<1;
		a=ans;
	}
	return ans;
}

int neg(int n)
{
	return add(~n,1);
}

int sub(int a,int b)
{
	return add(a,neg(b));
}

int main()
{
	int a,b;
	cout<<"a,b:"<<endl;
	cin>>a>>b;
	
	cout<<sub(a,b);
	
	return 0;
}

减法就很简单了，转化成a+(-b)即可，而-b就是~b+1。

三、乘法

#include<bits/stdc++.h>
using namespace std;

int add(int a,int b)
{
	int ans=a;
	while(b!=0)
	{
		ans=a^b;
		b=(a&b)<<1;
		a=ans;
	}
	return ans;
}

int mult(int a,int b)
{
	int ans=0;
	while(b!=0)
	{
		if((b&1)!=0)
		{
			ans=add(ans,a);
		}
		a<<=1;
		b>>=1;
	}
	return ans;
}

int main()
{
	int a,b;
	cout<<"a,b:"<<endl;
	cin>>a>>b;
	
	cout<<mult(a,b);
	
	return 0;
}

乘法依旧借助了竖式运算的原理，只不过这里是按二进制数位进行的。

若b的最后一位是1，就让ans再加上一个a，之后，要将a左移1位，并且为了取b的下一个数位，要让b右移一位。

四、除法

#include<bits/stdc++.h>
using namespace std;

int add(int a,int b)
{
	int ans=a;
	while(b!=0)
	{
		ans=a^b;
		b=(a&b)<<1;
		a=ans;
	}
	return ans;
}

int neg(int n)
{
	return add(~n,1);
}

int sub(int a,int b)
{
	return add(a,neg(b));
}

int divide(int a,int b)
{
	int x=a<0?neg(a):a;
	int y=b<0?neg(b):b;
	int ans=0;
	for(int i=30;i>=0;i--)
	{
		if((x>>i)>=y)
		{
			ans|=(1<<i);
			x=sub(x,y<<i);
		}
	}
	return (a<0)^(b<0)?neg(ans):ans;
}

int main()
{
	int a,b;
	cout<<"a,b:"<<endl;
	cin>>a>>b;
	
	cout<<divide(a,b);
	
	return 0;
}

除法借助的原理是，例如280除以25，只保留商，可以将280转化成25*2^3+25*2^1+25*2^0。

首先先将负数转为正数，然后从第30位开始到第0位，若x右移i位比y大，即x还包含2^i个y，所以往ans的第i位里或进去一个1，之后让x减去2^i个y即可。最后这个判断很妙，只有a和b异号时才返回-ans。