Wednesday, October 16, 2013

Divide Two Integers !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Q:
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