两数相除

来源Leetcode第29题两数相除

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

示例 1:

输入: dividend = 10, divisor = 3
输出: 3

说明:

• 被除数和除数均为 32 位有符号整数。
• 除数不为 0。
• 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回 2^31 − 1。

Wrong Answer

除法的话，第一思路是移位。
对形如B(10)= 2^n + 2^n-1 + …… + 2^0
但是如果不是2^n的话，那么单靠移位操作是完成不了的。
考虑实际上计算机的除法是模二除法，可参考组原课本的 基于不恢复余数的补码除法。

这代码目前AC不了，因为还没考虑到各种边界值，例如被除数为-2147483648;除数为：-2147483648；或者为+1,-1等等情况。

int getBits(int num){
    //获取操作数的位长
    int numLen = 0;
    while(num){
        numLen++;
        num = num>>1;
    }
    return numLen;
}

int getBit(int num,int pos){
    //获取从右到左的第pos位置的值1/0
    pos = pos-1;
    int index = 1<<pos;
    if((num&index)>>pos)
        return 1;
    else
        return 0;
}

int divide(int dividend, int divisor) {
    int divide = 0;
    int res = 0;
	int dividend2 = dividend;
	
    int minus = (dividend >> 31) ^ (divisor >> 31);  //取符号位判断是否同号或异号
    bool minValue = false;
	
	if(dividend == -2147483648 && divisor == -1) return 2147483647;
	
	if(dividend == -2147483648 && divisor == 1) return -2147483648;
	
	if(dividend < divisor)
        return 0;
	
	if(dividend==-2147483648){
        minValue = true;
        dividend = dividend-1;  //转成了2147483647
        }
		
    if(divisor==-2147483648){
        if(minValue)//被除数与除数相同
                return 1;
            return 0;
        }
		
    if(dividend < 0||divisor < 0){
        if(dividend < 0 && divisor < 0)
        {
            dividend = -dividend;
            divisor = -divisor;
        }else{
            dividend = dividend<0?-dividend:dividend;
            divisor = divisor<0?-divisor:divisor;
            minus = 1;
        }
    }
	


    if(divisor==1){
        if(minus){
            if(minValue)//被除数为最大值
                return -2147183648;
            else
                return dividend2;
        }
        else
            return dividend2;
    }


    int index = getBits(dividend);
    while(index>0){
        int val = getBit(dividend,index--);
        divide = (divide<<1)+val;

        if(divide<divisor)
            res = res<<1;
        else{
            res = (res<<1)+1;
            divide = divide-divisor;
        }
    }
    if(minValue&&(divide+1)>=divisor){
        res++;
        divide = divide+1-divisor;
    }
    if(minus){
         return -res;
    }
    return res;
}

移位除法

停电了，这题我写了2个小时了，估计是在判断-2147483648出了点问题，明天有空把这一块重写下。
最后附上AC了的代码:

class Solution {
    public int divide(int dividend, int divisor) {
        if(dividend == -2147483648 && divisor == -1) return 2147483647;
        int flag = (dividend >> 31) ^ (divisor >> 31);  //取符号位判断是否同号
        int result = 0;
        if((dividend >> 31) == 0) dividend = -dividend;  //用负数进行除法运算
        if((divisor >> 31) == 0) divisor = -divisor;
        while(dividend <= divisor){ //被除数在负数情况下比除数小，即在正数情况下比除数大
        //执行除法(减法运算)，直到被除数和除数相等或者小于除数
            int i = -1;  
            int temp = divisor;
            while(dividend <= (temp << 1)){  // 被除数小于(除数 * 2)
            if(temp <= (Integer.MIN_VALUE >> 1)){  //负除数小于0xC0000000 ，即产生了溢出
                break;
            }
            i = i << 1;  //结果*2
            temp = temp << 1; //除数*2 以毕竟被除数
            }
            dividend = dividend - temp;  //被除数减去(除数*2^n)
            result += i;  //结果加上2^n
        }
        if(flag == 0){
            //符号相同，则会可能产生除法溢出
            if(result <= Integer.MIN_VALUE) return Integer.MAX_VALUE;
            result = -result;
        }
        return result;
    }
}