1.加法

基本思路：

  • 使用位运算a ^ b来实现没有进位的本位和
  • 用a & b来获得需要进位的位置，则(a & b << 1)则表示进位加1后的数
  • 再用或运算求本位和，直至(a & b) == 0即没有进位为止。

代码

  1. int Add(int a, int b){
  2.     return b ? Add(a ^ b, (a & b) << 1) : a;
  3. }

2.减法

基本思路：

  • 将a - b 转换成a + (-b)
  • 由于 ~ b = -(b + 1)，故 -b = ~b + 1

代码

  1. int Minus(int a, int b){
  2.     return Add(a, Add(~b, 1));
  3. }

3.乘法

基本思路：

  • 暴力算法：模拟加法，但是加法次数太多
  • 模拟手算乘法，当乘数最后一位是1，则结果加上被乘数
  • 一次判断后，要将乘数右移一位，被乘数左移一位
  • 当乘数为0时，终止运算

代码

  1. int Multiply(int a, int b){
  2.     int a1 = a > 0 ? a : Add(~a, 1);
  3.     int b1 = b > 0 ? b : Add(~b, 1);
  4.     int sum = 0;
  5.     while(b1){
  6.         if(b1 & 0x1){
  7.             sum = Add(sum, a1);
  8.         }
  9.         a1 = a1 << 1;
  10.         b1 = b1 >> 1;
  11.     }
  12.     if((a ^ b) < 0)
  13.         return Add(~sum, 1);
  14.     else return sum;
  15. }

4.除法

基本思路：

  • 暴力做法：模拟减法，但是减法次数太多
  • 考虑到int的大小为32个bit，则从i=32开始比较被除数与除数2^i的大小
  • 若被除数大，则在商处直接加上2^i从而减小减法的次数

代码

  1. int Divide(int a, int b){   
  2.     int quotient = 0;
  3.     if(!b){
  4.         cout << "Error" << endl;
  5.         return 1;
  6.     }
  7.     for(int i = 31; i --; i > 0){
  8.         if((a >> i) >= b)
  9.         {
  10.             quotient = Add(quotient, 1 << i);
  11.             a = Minus(a, b << i);
  12.         }
  13.     }
  14.     if((a ^ b) < 0)
  15.         quotient = Add(~quotient, 1);
  16.     return quotient;
  17. }

引用