simple division

递归版本

#include <cstdio>
struct res{
    long long q;
    long long r;
};
struct res divide_t(long long divided,long long divisor){
    struct res zeroRes;
    zeroRes.q=0;zeroRes.r=0;
    if(divided==0) return zeroRes;
    struct res tmpRes_t=divide_t(divided>>1,divisor);
    tmpRes_t.q<<=1;
    tmpRes_t.r<<=1;
    if(divided&1) tmpRes_t.r++;
    if(tmpRes_t.r>=divisor){
        tmpRes_t.r-=divisor;
        tmpRes_t.q++;
    }
    return tmpRes_t;
}
int divide(long long divided,long long divisor){
    //if(divisor==0||(divided==INT_MIN&&divisor==-1)) return INT_MAX;
    bool isNegative=false;
    if(divided<0) {isNegative=!isNegative;divided=-divided;}
    if(divisor<0) {isNegative=!isNegative;divisor=-divisor;}
    struct res tmpRes_t=divide_t(divided,divisor);
    if(isNegative) return -tmpRes_t.q;
    else return tmpRes_t.q;
}
int main(){
    int divided,divisor;
    scanf("%d%d",&divided,&divisor);
    printf("%d\n",divide(divided,divisor));
}

emmm...基本上就是照着slide的代码翻译一下。
说一下理解吧。
1. 关于递归的临界条件，除数为0就返回0..emmm没毛病。
2. 递归下一层的时候除数除于2，被除数不变，再把结果翻倍。这个也好理解，

$$∵a/b=c...d\\∴a=bc+d\\即2a=2bc+2d\\故2a/b=2c...2d$$
3. 然后是递归调用前的divided为奇数，那么位移操作会把尾数舍去，再余数部分加回即可
4. 最后判断余数和被除数的关系，返回最后结果。

看完代码有种感觉是：这都能得出结果？分析一下好像又没有哪里不对..颠覆常识了2333
还有一个,leetcode交的时候没有注意数据范围..abs后溢出了T.T

迭代版本

#include <cstdio>
using namespace std;
typedef long long LL;
int divide(LL divided,LL divisor){
    //if(divisor==0||(divided==INT_MIN&&divisor==-1)) return INT_MAX;
    bool isNegative=false;
    if(divided<0) {isNegative=!isNegative;divided=-divided;}
    if(divisor<0) {isNegative=!isNegative;divisor=-divisor;}
    if(divided==0) return 0;
    LL q=0,r=0;
    LL tmpDivided=0;
    int count=0;
    int countAll=0;
    LL toCountBit=divided;
    //计算一共有多少位
    while(toCountBit>0){
        toCountBit>>=1;
        countAll++;
    }
    //printf("%d\n",countAll);
    while(tmpDivided<divided){
        tmpDivided<<=1;
        //因为要从最高位开始计算，所以要1<<(countAll-count-1)
        if((1<<(countAll-count-1))&divided){
            tmpDivided++;
        }
        q<<=1;
        r<<=1;
        if(tmpDivided&1) r++;
        if(r>=divisor){
            q++;
            r-=divisor;
        }
        count++;
    }
    if(isNegative) return -q;
    else return q;
}
int main(){
    int divided,divisor;
    scanf("%d%d",&divided,&divisor);
    printf("%d\n",divide(divided,divisor));
}

改写的思路就是把自顶向下改成自底向上，emmmm..先从递归的临界条件开始，逐步往上推，思路是不变的。leetcode交了一下过了，应该没有问题（如果它的数据不水的话）。