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

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

转自：http://blog.csdn.net/hackbuteer1/article/details/7390093

^: 按位异或；&：按位与； | ：按位或

计算机系统中，数值一律用补码来表示：因为补码可以使符号位和数值位统一处理，同时可以使减法按照加法来处理。

对补码做简单介绍：数值编码分为原码，反码，补码，符号位均为0正1负。

原码 -> 补码： 数值位取反加1

补码 -> 原码： 对该补码的数值位继续 取反加1

补码 的绝对值（称为真值）：正数的真值就是本身，负数的真值是各位（包括符号位）取反加1（即变成原码并把符号位取反）.

b -> -b ： 各位（包括符号位）取反加1

加法运算：将一个整数用二进制表示，其加法运算就是：相异（^）时，本位为1，进位为0；同为1时本位为0，进位为1；同为0时，本位进位均为0.

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

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

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

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

除法运算：除法运算是乘法的逆。看a最多能减去多少个b，
#include<iostream>
 #include<cstdlib>
 using namespace std;
 
 //递归版本的加法实现
 int Add(int a, int b)
 {
     return b ? Add(a^b, (a&b)<<1) : a;
     /*
     if(b)
         return plus_rec(a^b, (a&b)<<1);
     else
         return a;
         */
 }
 
 //该为迭代版本
 int Add_iter(int a, int b)
 {
     int ans;
     while(b)
     {
         ans = a^b;
         b = (a&b)<<1;
         a = ans;
     }
     return ans;
 }
 
 //求a的相反数：将各位取反加一
 int negative(int a)     //get -a
 {
     return Add(~a, 1);
 }
 
 int Minus(int a, int b)
 {
     return Add(a, negative(b));
 }
 
 //正数乘法
 int Multi(int a, int b)
 {
     int ans = 0;
     while(b)
     {
         if(b&1)
             ans = Add(ans, a);
         a = a << 1;
         b = b >> 1;
     }
     return ans;
 }
 
 //正数除法
 int Divide(int a, int b)
 {
     int coun = 0;
     while(a >= b)
     {
         a = Minus(a, b);
         coun = Add(coun, 1);
     }
     return coun;
 }
 
 //判断是否是负数，0，正数
 int isneg(int a)
 {
     return a & 0x8000;
 }
 int iszero(int a)
 {
     return !(a & 0xFFFF);
 }
 int ispos(int a)
 {
     return (a&0xFFFF) && !(a&0x8000);
 }
 
 //处理负数的乘法和除法
 int My_Multi(int a, int b)
 {
     if(iszero(a) || iszero(b))
         return 0;
     if(isneg(a))
     {
         if(isneg(b))
             return Multi(negative(a), negative(b));
         else
             return negative(Multi(negative(a), b));
     }else if(isneg(b))
         return negative(Multi(a, negative(b)));
     else
         return Multi(a, b);
 }
 
 int My_Divide(int a, int b)
 {
     if(iszero(b))
     {
         cout << "Error!" << endl;
         exit(1);
     }
     if(iszero(a))
         return 0;
     if(isneg(a))
     {
         if(isneg(b))
             return Divide(negative(a), negative(b));
         else
             return negative(Divide(negative(a), b));
     }else if(isneg(b))
         return negative(Divide(a, negative(b)));
     else
         return Divide(a, b);
 
 }
 
 int main(int argc, char **argv)
 {
     int a = 5;
     int aa = -5;
     int b = 3;
     int bb = -3;
     int c = 15;
     cout << Add(a, b) << endl;
     cout << Add(a, bb) << endl;
     cout << Minus(a, b) << endl;
     cout << Minus(b, a) << endl;
     cout << Multi(a, b) << endl;
     cout << My_Multi(aa, b) << endl;
     cout << Divide(c, a) << endl;
 
     return 0;
 }