Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1170224
  • 博文数量: 695
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 4027
  • 用 户 组: 普通用户
  • 注册时间: 2013-11-20 21:22
文章分类

全部博文(695)

文章存档

2018年(18)

2017年(74)

2016年(170)

2015年(102)

2014年(276)

2013年(55)

分类: Java

2017-03-09 16:01:50

不用算术运算符实现两个数的加法(按位异或)

  对于二进制的加法运算,若不考虑进位,则1+1=0,1+0=1,0+1=1,0+0=0,通过对比异或,不难发现,此方法与异或运算类似。因而排出进位,加法可用异或来实现。然后考虑进位,0+0进位为0,1+0进位为0,0+1进位为0,1+1进位为1,该操作与位运算的&操作相似。

  那么加法运算可以这样实现:

  1)先不考虑进位,按位计算各位累加(用异或实现),得到值a;

  2)然后在考虑进位,并将进位的值左移,得值b,若b为0,则a就是加法运算的结果,若b不为0,则a+b即得结果(递归调用该函数)。

  算法代码如下(非vs平台):

点击(此处)折叠或打开

  1. int bitAdd(int a,int b)
  2. 2 {
  3. 3 if(b==0)
  4. 4 return a;
  5. 5 int sum = a^b;
  6. 6 int carry =(a&b)<<1;
  7. 7 return bitAdd(sum,carry);
  8. 8 }

加法运算:将一个整数用二进制表示,其加法运算就是:相异(^)时,本位为1,进位为0;同为1时本位为0,进位为1;同为0时,本位进位均为0.

所以,不计进位的和为sum = a^b,进位就是arr = a&b,(与sum相加时先左移一位,因为这是进位)。完成加法直到进位为0.

减法运算:a-b  = a+(-b)  根据补码的特性,各位取反加1即可(注意得到的是相反数,不是该数的补码,因为符号位改变了)

(上面用二进制实现的加减法可以直接应用于负数)

乘法运算:原理上还是通过加法计算。将b个a相加,注意下面实际的代码。

除法运算:除法运算是乘法的逆。看a最多能减去多少个b,




点击(此处)折叠或打开

  1. #include<iostream>
  2. #include<cstdlib>
  3. using namespace std;

  4. //递归版本的加法实现
  5. int Add(int a, int b)
  6. {
  7.     return b ? Add(a^b, (a&b)<<1) : a;
  8.     /*
  9.     if(b)
  10.         return plus_rec(a^b, (a&b)<<1);
  11.     else
  12.         return a;
  13.         */
  14. }

  15. //该为迭代版本
  16. int Add_iter(int a, int b)
  17. {
  18.     int ans;
  19.     while(b)
  20.     {
  21.         ans = a^b;
  22.         b = (a&b)<<1;
  23.         a = ans;
  24.     }
  25.     return ans;
  26. }

  27. //求a的相反数:将各位取反加一
  28. int negative(int a) //get -a
  29. {
  30.     return Add(~a, 1);
  31. }

  32. int Minus(int a, int b)
  33. {
  34.     return Add(a, negative(b));
  35. }

  36. //正数乘法
  37. int Multi(int a, int b)
  38. {
  39.     int ans = 0;
  40.     while(b)
  41.     {
  42.         if(b&1)
  43.             ans = Add(ans, a);
  44.         a = a << 1;
  45.         b = b >> 1;
  46.     }
  47.     return ans;
  48. }

  49. //正数除法
  50. int Divide(int a, int b)
  51. {
  52.     int coun = 0;
  53.     while(a >= b)
  54.     {
  55.         a = Minus(a, b);
  56.         coun = Add(coun, 1);
  57.     }
  58.     return coun;
  59. }

  60. //判断是否是负数,0,正数
  61. int isneg(int a)
  62. {
  63.     return a & 0x8000;
  64. }
  65. int iszero(int a)
  66. {
  67.     return !(a & 0xFFFF);
  68. }
  69. int ispos(int a)
  70. {
  71.     return (a&0xFFFF) && !(a&0x8000);
  72. }

  73. //处理负数的乘法和除法
  74. int My_Multi(int a, int b)
  75. {
  76.     if(iszero(a) || iszero(b))
  77.         return 0;
  78.     if(isneg(a))
  79.     {
  80.         if(isneg(b))
  81.             return Multi(negative(a), negative(b));
  82.         else
  83.             return negative(Multi(negative(a), b));
  84.     }else if(isneg(b))
  85.         return negative(Multi(a, negative(b)));
  86.     else
  87.         return Multi(a, b);
  88. }

  89. int My_Divide(int a, int b)
  90. {
  91.     if(iszero(b))
  92.     {
  93.         cout << "Error!" << endl;
  94.         exit(1);
  95.     }
  96.     if(iszero(a))
  97.         return 0;
  98.     if(isneg(a))
  99.     {
  100.         if(isneg(b))
  101.             return Divide(negative(a), negative(b));
  102.         else
  103.             return negative(Divide(negative(a), b));
  104.     }else if(isneg(b))
  105.         return negative(Divide(a, negative(b)));
  106.     else
  107.         return Divide(a, b);

  108. }

  109. int main(int argc, char **argv)
  110. {
  111.     int a = 5;
  112.     int aa = -5;
  113.     int b = 3;
  114.     int bb = -3;
  115.     int c = 15;
  116.     cout << Add(a, b) << endl;
  117.     cout << Add(a, bb) << endl;
  118.     cout << Minus(a, b) << endl;
  119.     cout << Minus(b, a) << endl;
  120.     cout << Multi(a, b) << endl;
  121.     cout << My_Multi(aa, b) << endl;
  122.     cout << Divide(c, a) << endl;

  123.     return 0;
  124. }



阅读(296) | 评论(0) | 转发(0) |
0

上一篇:尾递归

下一篇:设计模式二---适配器模式

给主人留下些什么吧!~~