29. Divide Two Integers 实现除法

int divide(int a, int b) {
    if (a == INT_MIN && b == -1) {
        return INT_MAX;
    } else if (a == 0) {
        return 0;
    } else if (b == 1) {
        return a;
    }

    int neg=(a>>31)^(b>>31);
	// 范围 -2的31次方 ~ 2的31次方-1
	// 负数的范围更大，全部转成负数来处理
    if (a>0) a=-a;
    if (b>0) b=-b;
    if (b<a) return 0;
    int sub=b;
    int step=1;
    int res=0;

    while(true) {
		// 采用步长倍增的方式使得一大一小的时候能够显著减少计算次数
        while(sub >= (INT_MIN/2) && a - (sub+sub) < 0) {
            sub+=sub;
            step<<=1;
        }
        a-=sub;
        res+=step;
		// 恢复原始步长
        step=1;
        sub=b;
        if (a > b) {
            break;
        }
    }

    return neg ? -res : res;
}