Divide two integers without using multiplication, division and mod operator.
A:
18年最新一遍。 思路是: 递归调用,然后核心在最后3行。
class Solution {
public:
int divide(int dividend, int divisor) {
if( divisor == 0 || (dividend == INT_MIN && divisor == -1) ){
return INT_MAX;
}
int sign = 1;
if( (dividend > 0 && divisor < 0) || (dividend <0 && divisor > 0)) {
sign = -1;
}
if( dividend > 0){
dividend = - dividend;
}
if (divisor > 0){
divisor = - divisor;
}
int res = helper(dividend, divisor);
return sign > 0? res: -res;
}
int helper(int& a , int b){// a<0 and b < 0
if(a>b){
return 0;
}else if(a -b > b ){
a -= b;
return 1;
}else{ // a <= 2*b
int res = helper(a, b+b); // this time, delete the top result
res += res;
return res + helper(a,b); // recall this result
}
}
};
------------------------------第3遍----------------------------------一上来, 还是按照了老的思路--------------哎,Tiger,你白白地搞了第一遍啊, 没有学到东西啊----------------这里,我还是用了学的思路, 做两两对比,然后做减法 ---------------
public class Solution { public int divide(int dividend, int divisor) { assert(divisor != 0): "divisor cannot be zero"; long a = dividend, b = divisor; int sign = -1; if( (a>=0 && b >0) || ( a<0 && b<0) ) // if both positive or negative sign = 1; if(a<0) a = -a; if(b<0) b = -b; b = b<<31; int result = 0; for(int i =0;i<=31;i++){ int tmp = 0; if(a>=b ){ tmp = 1; a -= b; } b = b>>1;// shift first, assume the case 1 / 1 result = ( result<<1 ) + tmp; } return result*sign; } }
Error:
1: after chaning a --> aa(long) and b--> bb(long), but in the while loop, we forget to use aa and bb .
2: 不管a b的大小关系如何,都要先把结果移位后,再加1或者加0.
3: when result == 0, tmp == 1, what is the result of the following code ???
result = result<<1 + tmp; (see the end of this page)
4: divisor = -2147483648, when , fuck, 问题处在这里。 原本现搞成int a, b, 再转换正负号。然后再转换成long类型。
后来,直接转换成long类型,没有先判断正负号。 导致b <<32之后,变成负的了。
哦,不是这个问题, 问题是这样:
divisor = -2147483648
divisor = Math.abs(divisor); 的结果,会是什么呢?????(见本页最后)
********************************************************************
思路就是,按照手算的过程, 写入----------------------搞了TMD一个晚上,Tiger,你行不行啊??? 磨磨蹭蹭, 犹犹豫豫,婆婆妈妈,不是男人!!!!!!肏!!!!
public class DivideTwoIntegers { public int divide(int dividend, int divisor) { // Use the way, just like hand-written assert (divisor != 0); // get sign long longDividend = dividend; long longDivisor = divisor; int sign = 1; if ((longDividend < 0 && longDivisor > 0) || (longDividend > 0 && longDivisor < 0)) { sign = -1; } if (longDividend < 0) { // get inverse and add 1 long tmp = ~longDividend; longDividend = tmp + 1; } if (longDivisor < 0) { // get inverse and add 1 long tmp = ~longDivisor; longDivisor = tmp + 1; } // NOW, both divisor and dividend are non-negative // and the 31th bits are both zero // find the i_{th} shift that would make divisor > dividend int nLeftShift = 0; while (longDivisor <= longDividend ) { longDivisor = longDivisor << 1; nLeftShift++; } int result = 0; longDivisor = longDivisor >> 1; // now divisor is less than zero nLeftShift--; // following while loop is the hand written step for (int i = nLeftShift; i >= 0; i--) { if (longDividend >= longDivisor) { result += 1 << i; longDividend -= longDivisor; } longDivisor = longDivisor >> 1; } if (sign < 0) { result = -result; } return result; } }
Mistakes:
1: 第一遍是思路不对,用了复杂的数据结构来存储临时的2的次幂。
2: 第二遍呢, 是自己知道,手动怎么做,但是,缺傻了吧唧的, 磨磨蹭蹭,头脑不清醒,不知道怎么做。
3: 最后,还是在网上找了简介,重新学习了, 怎么用手去做除法, TNND。 时间就是生命啊, Tiger
4: 在编程的时候,没有检测,当 二者相等的时候, 也是商1 的。
即: if(dividend >= divisor){ 这里要有等号。
5: 当输入相等的时候, 结果是0 , ???????
原因在于,开始的时候,头脑不清醒。
当寻找nLeftShift以使之大于 dividend , 以备后面右移一位。 应该加上 相等的条件。
while (divisor <= dividend && nLeftShift < 31) {
divisor = divisor << 1;
nLeftShift++;
}
6: 情况考虑的不周。 有可能是已经divisor用力左移,也无法比dividend大。 这个时候,是可以达到nLeftDividend = 31的。
7: 对于 int 类型的最小数 -2147483648, 将之取反加一之后,还是这个数儿啊。 郁闷~~~
为解决这个问题,我们将int 类型,改成long类型。 哎,都是泪啊~~~
(--------由于扩充了范围,就不存在右移divisor ,却不能大于dividend的问题了)
----------------第二遍-------------------------
8: result << 1 + curResult; 这样一句,是先计算 加法,再计算 移位。 哎~~~~~~~~~~
9 :
for (int i = 0; i <= nShift; i++) { 这里,应该是<= 符号的, 自己仔细想想吧。 Tiger
Learned:
比如在十进制中,从十位借一位到个位,用在个位减的时候,就是10+个位上的数,二进制,从十位借一位到个位,用在个位减的时候,就是2+个位上的数
比如说:101-11,个位够减,为0,十位不够,从百位上借1,所以十位就为2,被减数十位-减数十位,为2-1=1,所以结果为10
二进制除法中,除到最后有余数怎么办?
如果是定点数(整数),那就舍掉了。
如果是浮点数,则继续加位运算,直到精度达到后舍掉。
二进制的乘法远比十进制简单,比如乘数是1011,只需将将被乘数分别左移3位、1位,移动后补入0,并将这三个数(被乘数左移3位的、被乘数左移1位的及未移位的被乘数)在累加器中相加,所得总和就是积,根据需要积可再转化为十进制。
除法与乘法类似,只不过将左移改为右移,加改成减。实际上减也是通过取补码后再加
除法一般不好优化,直接按照笔算步骤来算就可以了:
1、根据被除数(余数)和除数的大小来上商;
2、被除数(余数)低位补0,再减去右移后的除数,也可以改为左移余数,减去除数,这样可以确保参与运算的寄存器具有相同的位数;
3、商写到寄存器的最低位,然后商左移1位。
连续做减法,现在公认的就是这个,让被除数连续减去n个除数,直到差小于除数时为止,这样减去的次数就是商,剩下的差就是余数。
--------------------第二遍-----------------------思路同上, 只不过是for循环更改了-----------
public class Solution { public int divide(int dividend, int divisor) { long a = dividend; // in case overflow for negative input long b = divisor; int sign = 1; if ((a < 0 && b > 0) || a > 0 && b < 0) sign = -1; if (a < 0) a = -a; if (b < 0) b = -b; if (b == 0) if (sign == 1) return Integer.MAX_VALUE; else return Integer.MIN_VALUE; int nShift = 0; while (a >= b) { b = b << 1; nShift++; } b = b >> 1; nShift--; // now b is right less than a int result = 0; for (int i = 0; i <= nShift; i++) { int curResult = 0; if (a >= b){ curResult = 1; a -= b; } b = b >> 1; result = (result << 1 ) + curResult; } if (sign > 0) return result; else return -result; } }
------------------下面的做法, 会memory limit exceed ---------
public class Solution { public int divide(int dividend, int divisor) { // using two time of the divisor, int a = dividend; int b = divisor; int sign = 1; if( a<0 && b<0 ){ a = -a; b = -b; }else if( a>0 && b <0 ){ b = -b; sign = -1; }else if ( a<0 && b>0 ){ a=-a; sign = -1; } // else both are positive if(b == 0) return Integer.MAX_VALUE; // use to build list to use DP ArrayList<Integer> al = new ArrayList<Integer>(); int doubledValue = b; while(doubledValue < a ){ al.add(doubledValue); doubledValue += doubledValue; } al.add(Integer.MAX_VALUE);// add max value to avoid end testing if(sign >0 ) return getDivide(a,b,al); else return 0 - getDivide(a,b,al); } private int getDivide(int a, int b , ArrayList<Integer> al){ // both a and b are positive if(a<b) return 0; int powerof2 = 1; int i=1; for( i =1;i< al.size();i++ ){ if( al.get(i) > a ){ break; }else{ powerof2 += powerof2; } } return powerof2 + getDivide(a - al.get(i-1) ,b,al); } }*****************************************************
answer:
1:
when result == 0, tmp == 1, what is the result of the following code ???
result = result<<1 + tmp; (see the end of this page)
==> 0
因为 加法的优先级比移位高
2:
divisor = -2147483648
divisor = Math.abs(divisor); 的结果 --> divisor保持不变。
因为,
int k = -2147483648;
System.out.println(Integer.toBinaryString(k));
会打印: 10000000000000000000000000000000
No comments:
Post a Comment