正整数除法与加法的位运算实现

方法1：依次减去除数

最常规的是按照除法的性质，依次将被除数减去除数，直到余数小于除数为止，由于复杂度太大。不重点讨论

方法2：递归位运算

每一次递归中，将除数通过移位依次乘以2。当被除数小于除数时，退出循环，此时将除数后退一步（初以2，保证除数小于当前被除数），继续递归。

 int div2(int x, int y){
     if(y == 0 || x < y)
         return 0;
     int k = 0;
     int cur = y;
     for(; x >= cur; cur <<= 1, ++k){
         if(x - cur < y)//只比原除数大一倍不到，直接返回移位除数
             return 1<<k;
     }
     return div2(x-(cur>>1), y) + (1 << (k-1));
 }

方法3：迭代位运算

思路与方法2相同，不过是用迭代实现的。

 int div3(int x, int y){
     int left = x;  //剩余的被除数
     int res = 0;  //结果
     while(left >= y){
        int multi = 1;
        while(y * multi <= (left >> 1) ){
            multi = multi<<1;
        }  //退出循环时，left/2 < y*multi <=left
        res += multi;
        left -= y*multi;
     }
     return res;
 }

引申：如何用逻辑运算实现加法

递归求解，当进位为0时，退出递归。

int add(int x, int y){
    if(y == 0)
        return x;
    int sumTemp = x ^ y;
    int carry = (x & y) << 1;
    return add(sumTemp, carry);
}