Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 程序设计 » 

位运算实现加减乘除四则运算

程序设计中大量使用到加减乘除等四则运算,但有时我们被要求只用位操作来实现这些功能,本文将通过具体代码介绍如何使用位运算实现加减乘除取模和乘方等操作,可以借此看到位运算使用的巧妙之处。

加法

两个整数a和b相加时,考虑他们的二进制补码相加情况,有些二进制位相加后没有进位,有些则需要进位。

  • 考虑a&b,与的结果为1的位对应着原来两个数在该位上都为1,则相加进位,此时a&b乘以2即为相加后的结果。
  • 考虑a^b,异或的结果为1的位表示原来两个数在该位上有一个为1,相加后结果仍然是1,则此时a^b即为该位相加的结果。

此时a和b相加的结果可以变为a&b和a^b相加,这是一个类似的问题,并且相对更加简单,可以递归求解,直到a&b为0,即没有进位时,可以得到最终结果。

//加法
int Add(int a, int b)
{
	int t;
	while (b)
		t = a ^ b, b = (a & b) << 1, a = t;
	return a;
}

减法

两个整数a和b相减可以看出a和-b相加的结果,于是可以转化为加法求解。
而一个正数的相反数可以表示为它的取反加一,于是有以下代码。

//取相反数
int Neg(int a)
{
	return Add(~a, 1); //取反加一
}

//减法
int Min(int a, int b)
{
	return Add(a, Neg(b)); // a + (-b)
}

乘法

乘法可以看成是加法的延伸,只是相加的项多了一点。但是可以把其中一个乘数拆成二进制,根据二进制的每一位进行求和。不过首先还是先判断一下正负号统一转化为正数进行运算比较方便。

//乘法
int Mul(int a, int b)
{
	bool isNeg = (a > 0) ^ (b > 0);
	unsigned int x = a > 0 ? a : Neg(a), y = b > 0 ? b : Neg(b);
	int ans = 0;
	while (y)
	{
		if (y & 0x01) ans = Add(ans, x);
		y >>= 1, x <<= 1;
	}
	return isNeg ? Neg(ans) : ans;
}

乘方

乘方也是乘法的延伸,我们可以使用相同的办法求得乘方的结果。这也称为二分快速幂算法。

//乘方
int Pow(int a, int b)
{
	int ans = 1, q = a;
	while (b)
	{
		if (b & 0x01) ans = Mul(ans, q);
		b >>= 1, q = Mul(q, q);
	}
	return ans;
}

除法

除法是乘法的逆运算,乘法是相加,则除法只需要相减即可。同样地,可以想象把商展开成二进制表示,对应减去除数的倍数即可。

//除法
int Div(int a, int b) //b不为0
{
	bool isNeg = (a > 0) ^ (b > 0);
	unsigned int x = a > 0 ? a : Neg(a), y = b > 0 ? b : Neg(b);
	int ans = 0;
	for (int i = 31; i >= 0; i--)
		if ((x >> i) >= y) //x >= (y << i)等价写法,避免溢出
			x = Min(x, y << i), ans = Add(ans, 1 << i);
	return isNeg ? Neg(ans) : ans;
}

得到除法结果后可以利用除法的定义顺便得到取模的结果。

//取模
int Mod(int a, int b)
{
	return Min(a, Mul(Div(a , b), b)); //a - a / b * b
}

测试

可以使用以下的主函数进行简单测试。该函数随机产生两个数,正负数不定,然后测试每个运算的结果。这里不包括乘方,因为数据太大容易溢出,但程序中没有做任何的溢出处理。如果函数运行中崩溃了,说明某个地方出错了,否则可以得到最后输出的"Done"。

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <assert.h>

int main()
{
	srand(time(0));
	for (int i = 0; i < 1e7; i++)
	{
		int t1 = rand() + 1, t2 = t1 / 2;
		int a = rand() % t1 - t2, b = rand() % t1 - t2;
		//printf("%d %d\n", a, b);

		int c, d;
		c = Add(a, b), d = a + b; assert(c == d);
		c = Min(a, b), d = a - b; assert(c == d);
		c = Mul(a, b), d = a * b; assert(c == d);
		if (b != 0)
		{
			c = Div(a, b), d = a / b; assert(c == d);
			c = Mod(a, b), d = a % b; assert(c == d);
		}
	}
	printf("Done!\n");
}
上一篇: 下一篇:
  1. 請教一下:您在除法和取模那兒,有用到一個Min()的東西,這是宏還是函式?? 因為這一部份您沒定義也沒註明!! 謝謝!!

  2. #广东硅谷学院#学好IT好就业选硅谷IT,学技能拿文凭事半功倍,紧跟专业教师一起冲浪IT行业。我们有建设学习型专业师资团队,教师领跑学生紧随其后。(QQ:800015777,电话0754-88989555)

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论