Cacher is the code snippet organizer for pro developers

// solution 1, better. 
// 思想，先去掉符号，最后再考虑符号。一定要找到一个k, 使 b << k 一定是大于a的，之后再k--
int divide_two_integers(int up, int down) {
    long long a = abs((long long)up);
    long long b = abs((long long)down);
    
    long long result = 0;
    while(a >= b) {
        int k = 0;
        while(a >= (b << k) ) k++;  // gist, should be >= not >
        k--;
        a -= b << k;
        result += 1 << k;
    }
    return ((up^down)>>31) ? -result : result;
}

// solution 2
int divide_two_integers2(int up, int down) {
    long long a = abs((long long)up);
    long long b = abs((long long)down);
    long long result = 0;
    while(a >= b) {
        int k = 0;
        while(a >= (b << k)) {
            result += 1 << k;
            a -= b << k;
            k++;
        }
    }
    return ((up^down)>>31) ? -result : result; 
}