来源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等等情况。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93
| int getBits(int num){ int numLen = 0; while(num){ numLen++; num = num>>1; } return numLen; }
int getBit(int num,int pos){ 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; } 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了的代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| 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)){ if(temp <= (Integer.MIN_VALUE >> 1)){ break; } i = i << 1; temp = temp << 1; } dividend = dividend - temp; result += i; } if(flag == 0){ if(result <= Integer.MIN_VALUE) return Integer.MAX_VALUE; result = -result; } return result; } }
|