只用位运算来实现整数的加减乘除四则运算

亦凉 2022-07-16 08:45 188阅读 0赞

转自：[http://blog.csdn.net/ojshilu/article/details/11179911][http_blog.csdn.net_ojshilu_article_details_11179911]

首先回忆计算机组成原理学过的内容，数字在机器ALU运算逻辑单元内部是以补码形式进行运算的，因为补码有两个优势：  
1、能做到符号位和数值部分一起运算，这样无需单独考虑符号。

2、能把减法运算转化为加法运算来处理。

3、补码的没有正0和负0之分，所以表示范围比原码和反码多1个。

# 问题一： 位运算实现加法 #

不管是十进制加法还是二进制加法，其加的的过程在每一位看分为‘和’、‘进位’两个部分。‘和’要留在当前位，‘进位’加入到下一位。

我们现在关注二进制加法。发现一个特点。

位的*异或运算*跟*求'和'*的结果一致：

**异或 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**

于是我们决定用异或运算和与运算来表示加法。下面是两种形式的实现。

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** add(**int** a, **int** b) //递归形式
2.  \{ 
3.  **if**(b==0) //递归结束条件：如果右加数为0，即不再有进位了，则结束。
4.  **return** a; 
5.  **int** s = a^b; 
6.  **int** c = (a&b)<<1; //进位左移1位，达到进位的目的。
7.  **return** add(s, c); //再把'和'和'进位'相加。递归实现。
8.  \}

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** add(**int** a, **int** b) //非递归形式
2.  \{ 
3.  **int** s, c; 
4.  **while**(b != 0) 
5.   \{ 
6.   s = a^b; 
7.   c = (a&b)<<1; 
8.   a = s; 
9.   b = c; 
10.  \} 
11. **return** a; 
12. \}

# 问题二： 位运算实现减法 #

减法其实是用加法来实现的。在ALU中，当我求a-b，其实是求\[a-b\]补。因为有\[a-b\]补=\[a\]补 - \[b\]补= \[a\]补+\[-b\]补。所以我就要先求出-b。求一个数的负的操作是将其连符号位一起取反然后加1。

于是有办法做减法了：先把减数求负，然后做加法。

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** negtive(**int** i) 
2.  \{ 
3.  **return** add(~i, 1); 
4.  \}

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** subtraction(**int** a, **int** b) //减法运算：利用求负操作和加法操作
2.  \{ 
3.  **return** add(a, negtive(b)); 
4.  \}

# 问题三： 位运算实现乘法 #

乘法操作时即使用补码也要需要考虑符号位了，所以我要先把符号拿出来单独计算。为了方便，先引入两个工具函数，

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** getsign(**int** i) //取一个数的符号，看是正还是负
2.  \{ 
3.  **return** (i>>31); 
4.  \} 
5.  
6.  **int** bepositive(**int** i) //将一个数变为正数，如果本来就是正，则不变；如果是负，则变为相反数。注意对于-2147483648，求负会溢出。
7.  \{ 
8.  **if**(i>>31) 
9.  **return** negtive(i); 
10. **else**
11. **return** i; 
12. \}

## 做乘法的第一种思路： ##

很直观，就是用循环加法替代乘法。a\*b，就是把a累加b次。时间复杂度为O(N)。

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** multiply(**int** a, **int** b) 
2.  \{ 
3.  **bool** flag = **true**; 
4.  **if**(getsign(a) == getsign(b)) //积的符号判定
5.   flag = **false**; 
6.  
7.   a = bepositive(a);//先把乘数和被乘数变为正数
8.   b = bepositive(b); 
9.  **int** ans = 0; 
10. **while**(b) 
11.  \{ 
12.  ans = add(ans, a); 
13.  b = subtraction(b, 1); 
14.  \} 
15. 
16. **if**(flag) 
17.  ans = negtive(ans); 
18. **return** ans; 
19. \}

## 做乘法的第二种思路： ##

在二进制数上做乘法，如下图：

![SouthEast][]

这一过程就是根据乘数的每一位为0或1时，将被乘数错位的加在积上。时间复杂度为O(logN)。

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** multiply(**int** a, **int** b) 
2.  \{ 
3.  **bool** flag = **true**; 
4.  **if**(getsign(a) == getsign(b)) //积的符号判定
5.   flag = **false**; 
6.  
7.   a = bepositive(a); 
8.   b = bepositive(b); 
9.  **int** ans = 0; 
10. **while**(b) 
11.  \{ 
12. **if**(b&1) 
13.  ans = add(ans, a); 
14.  a = (a<<1); //把a错位加在积上
15.  b = (b>>1); //从最低位开始依次判断b的每一位
16.  \} 
17. 
18. **if**(flag) 
19.  ans = negtive(ans); 
20. **return** ans; 
21. \}

# 问题四： 位运算实现除法 #

## 做除法的第一种思路： ##

也比较直观，从被除数上减去除数，看能减多少次之后变得不够减。时间复杂度为O(N)。

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** division(**int** a, **int** b) 
2.  \{ 
3.  **if**(b==0) 
4.  **return** 0; 
5.  
6.  **bool** flag = **true**; 
7.  **if**(getsign(a) == getsign(b)) //积的符号判定
8.   flag = **false**; 
9.  
10.  a = bepositive(a); 
11.  b = bepositive(b); 
12. 
13. **int** n = 0; 
14.  a = subtraction(a, b); 
15. **while**(a>=0) 
16.  \{ 
17.  n = add(n, 1); 
18.  a = subtraction(a, b); 
19.  \} 
20. 
21. **if**(flag) 
22.  n = negtive(n); 
23. **return** n; 
24. \}

## 做除法的第二种思路： ##

第一种方法实在太慢了。减法得减的快一些，不能一个一个减，于是采用类似二分法的思路，从除数\*最大倍数开始测试，如果比被除数小，则要减去。下一回让除数的倍数减少为上一次倍数的一半，这样的直到倍数为1时，就能把被除数中所有的除数减去，并得到商。时间复杂度降低到O(logN)。

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** divide(**int** dividend, **int** divisor) \{ 
2.  **bool** flag = **true**; 
3.  **if**(getsign(dividend) == getsign(divisor)) //积的符号判定
4.   flag = **false**; 
5.  
6.   unsigned **int** x = bepositive(dividend); 
7.   unsigned **int** y = bepositive(divisor); 
8.  
9.  **int** ans=0; 
10. **int** i=31; 
11. **while**(i>=0) 
12.  \{ 
13. //比较x是否大于y\*(1<<i)=(y<<i)，避免直接比较，因为不确定y\*(1<<i)是否溢出 
14. **if**( (x>>i) >= y) //如果够减
15.  \{ 
16.  ans = add(ans, (1<<i)); 
17.  x = subtraction(x, (y<<i)); 
18.  \} 
19.  i = subtraction(i, 1); 
20.  \} 
21. **if**(flag) 
22.  ans = negtive(ans); 
23. **return** ans; 
24. \}

**注意细节：**

1、注意考虑除法运算的特殊情况：除数不为0。

2、int整型的表示范围是-2147483648~+2147483647。所以在求负的时候，有一个数-2147483648是不可以求负的，因为int无法表示+2147483648这个数。对于乘法运算，如果出现了这个数，运算就会溢出。对于除法操作，如果被除数是-2147483648，那么不能直接求负。所以最好采用无符号数来进行运算。

3、2^31，2^30,......,64,32,16,8,4,2,1。为什么尝试用这样的倍数做减法就能把所有除数都减去呢？从二进制数的角度来看，这些权值就可以构成所有的整数，组成倍数不会有遗漏。从折半的思想来看，这样是一个逐步折半细化的过程。

有了上面的四则运算，再扩展别的运算就很容易了。

# 附加问题：只用加法实现1+2+3+...+n， #

（循环、判断语句也不用）

1、利用递归来代替循环结构；  
2、利用&&与运算的特性来代替if结构。

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** add(**int** n, **int** &sum) 
2.  \{ 
3.   n && add(n-1, sum); 
4.  **return** (sum += n); 
5.  \}

或者

**\[cpp\]** [view plain][] [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **int** sum(**int** n) 
2.  \{ 
3.  **int** k; 
4.   ((1 == n)&&(k = 1)) || (k = sum(n-1) + n); 
5.  **return** k; 
6.  \}

[http_blog.csdn.net_ojshilu_article_details_11179911]: http://blog.csdn.net/ojshilu/article/details/11179911
[view plain]: http://blog.csdn.net/ojshilu/article/details/11179911#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/80735
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/80735/fork
[SouthEast]: /images/20220716/728922db85184d5580b97c0b0ec1345a.png