位运算实现加减乘除

一. 位运算的基本操作

A = 0011 1100
B = 0000 1101

操作符	描述	例子
＆	如果相对应位都是1，则结果为1，否则为0	（A＆B），得到12，即0000 1100
|	如果相对应位都是0，则结果为0，否则为1	（A | B）得到61，即 0011 1101
^	如果相对应位值相同，则结果为0，否则为1	（A ^ B）得到49，即 0011 0001
〜	按位取反运算符翻转操作数的每一位，即0变成1，1变成0	（〜A）得到-61，即1100 0011
<<	按位左移运算符。左操作数按位左移右操作数指定的位数。	A << 2得到240，即 1111 0000
>>	按位右移运算符。左操作数按位右移右操作数指定的位数。	A >> 2得到15即 1111
>>>	按位右移补零操作符。左操作数的值按右操作数指定的位数右移，移动得到的空位以零填充。	A>>>2得到15即0000 1111

二. 加法

1. 不考虑进位的按位求和, 异或
2. 只考虑进位，只有(1,1)才会产生进位，使用按位与可以满足要求。 当前位产生进位，要参与高一位的运算，因此按位与后要向左移动一位。
3. 递归求和，直到进位为0

int add(int a,int b) {
  int carry,add;
  do{
    add = a^b;
    carry = (a&b)<<1;
    a = add;
    b=carry;
  }while(carry!=0);
  return add;
}

三. 减法

先转换为加法: a-b = a+(-b) = a+(~b+1)

int subtract(int a,int b){
    return add(a,add(~b,1));
}

四. 乘法

乘法的实现可以转换成：k₃₁(2^31)+k₃₀(2^30)+...+k₂(2^2)+k₁(x^1)+k₀*(x^0); 其中k₀~k₃₁取0或者1
我也没看懂, 抄的.

// 正整数的乘法
int multiply(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 count=0;
    while(a>=b){
        a = subtract(a,b);
        count = add(count,1);
    }
    return count;
}
// 改进的除法：
int div(const int x,const int y){
    int left_num=x;
    int result=0;
    while(left_num>=y){
        int multi=1;
        while(y*multi<=(left_num>>1))
        {
            multi=multi<<1;
        }
        result+=multi;
        left_num-=y*multi;
    }
    return result;
}