LeetCode 문제 풀이 day 029 (Jieky)

/*
Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.

Example 1:
Input: dividend = 10, divisor = 3
Output: 3

Example 2:
Input: dividend = 7, divisor = -3
Output: -2

Note:
Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31, 2^31 − 1]. For the purpose of this problem, assume that your function returns 2^31 − 1 when the division result overflows.
*/
import java.util.*;
import java.lang.*;
public class DivideTwoIntegers{
     
    public static void main(String[] args){
     
        DivideTwoIntegers dti = new DivideTwoIntegers();
        int result = dti.divide(2147483647,1);
        System.out.println(result);
    }

	//           ，              
    public int divide(int dividend, int divisor) {
     
        int binary = 0b10000000000000000000000000000000;
        //    0，    0
        if (dividend == 0) return 0;
        //   、     。    1
        if (dividend == divisor) return 1;
        //        ，    0
        int temp_dividend = (dividend&binary) == binary ? dividend : ~dividend + 1;
        int temp_divisor = (divisor&binary) == binary ? divisor : ~divisor + 1;
        if (temp_dividend > temp_divisor) return 0;

        //          
        int flag = (dividend&binary) == (divisor&binary) ? 0 : 1;

		//    1        ，        
        if (temp_divisor == -1) return flag == 0 ? (temp_dividend == Integer.MIN_VALUE? Integer.MAX_VALUE:~temp_dividend+1) : temp_dividend;

        //       ：https://zhuanlan.zhihu.com/p/108566985
        int base = temp_divisor;
		//        -2147483648   
        int left = temp_dividend;
        int result = 0;
        int count = 1;
        while (left <= temp_divisor){
     
            // base >= (Integer.MIN_VALUE >> 1)  base  
			// >>   2，<
            while ((base >= (Integer.MIN_VALUE >> 1)) && ((base << 1)  >= left)) {
     
                // 2 4 8 16,            1 
                count = count << 1;
                base = base << 1;
                System.out.println(base);
                if (base >= 0) break;
            }
            if (base >= 0) break;
            //             
            result -= count;
            //             left
            left -= base;

            //   base count，         
            base = temp_divisor;
            count = 1;
        }

        // result   ，       ，         
        return flag == 0 ? (result == Integer.MIN_VALUE? Integer.MAX_VALUE:~result+1) : result;
    }

    public int divide03(int dividend, int divisor) {
     
        int binary = 0b10000000000000000000000000000000;
        int maxInt = 0b01111111111111111111111111111111;
        //    0，    0
        if (dividend == 0) return 0;
        //   、     。    1
        if (dividend == divisor) return 1;
        //        ，    0
         int temp_dividend = (dividend&binary) == binary ? dividend : ~dividend + 1;
         int temp_divisor = (divisor&binary) == binary ? divisor : ~divisor + 1;
         if (temp_dividend > temp_divisor) return 0;

        //          
        int flag = (dividend&binary) == (divisor&binary) ? 0 : 1;

        // -2147483648        -2147483648
        int abs_dividend = Math.abs(dividend);
        int abs_divisor = Math.abs(divisor);

        if (abs_divisor == 1){
     
            //      ， dividend     ，     
            if(dividend == binary && flag==0) return maxInt;
            //       ，  abs_dividend      ，       (      )
            return flag == 1 ? ~abs_dividend+1 : abs_dividend;
        }

        //       ：https://zhuanlan.zhihu.com/p/108566985
        int base = abs_divisor;
        //   abs_dividend -2147483648  ， -2147483648 - 2 = 2147483646
        int left = abs_dividend - base;
        int result = 1;
        int count = 1;
        while (left >= abs_divisor){
     
            // base <= (maxInt >> 1)  base  
            while ((base <= (maxInt >> 1)) && ((base << 1)  <= left)) {
     
                // 2 4 8 16,            1 
                count = count << 1;
                base = base << 1;
            }
            //             
            result += count;
            //             left
            left -= base;

            //   base count，         
            base = abs_divisor;
            count = 1;
        }

        //             
        return flag == 1 ? ~result+1 : result;
    }

    public int divide02(int dividend, int divisor) {
     
        if (dividend == 0) return 0;
        if (divisor == 0) return 100000;

        int binary = 0b10000000000000000000000000000000;
        int maxInt = 0b01111111111111111111111111111111;

        //          
        int flag = (dividend&binary) == (divisor&binary) ? 0 : 1;

        int abs_dividend = Math.abs(dividend);
        int abs_divisor = Math.abs(divisor);

        if (abs_divisor == 1){
     
            //      ， dividend     ，     
            if(dividend == binary && flag==0) return maxInt;
            //       ，  abs_dividend      ，       (      )
            return flag == 1 ? ~abs_dividend+1 : abs_dividend;
        }

        // -2147483648 - 2 = 2147483646，  abs_dividend -2147483648，       
        int count = 0;
        boolean overflow = false;
        int temp = abs_dividend - abs_divisor;
        // 3 - (-2147483648)    -2147483645，     ，       
        // -2147483648 - 3    2147483645，   2147483648 - 3  ，       
        while(abs_dividend - abs_divisor >= 0) {
     
            count++;
            abs_dividend -= abs_divisor;
        }

        //             
        return flag == 1 ? ~count+1 : count;
    }


    public int divide01(int dividend, int divisor) {
     
        if (dividend == 0) return 0;
        if (divisor == 0) return 100000;

        int binary = 0b10000000000000000000000000000000;
        int maxInt = 0b01111111111111111111111111111111;

        //          
        int flag = (dividend&binary) == (divisor&binary) ? 0 : 1;

        int abs_dividend = Math.abs(dividend);
        int abs_divisor = Math.abs(divisor);

        if (abs_divisor == 1){
     
            //      ，dividend      divisor 1，     
            if(dividend == binary && flag==0) return maxInt;
            //      ，  abs_dividend      ，       (      )
            return flag == 1 ? ~abs_dividend+1 : abs_dividend;
        }

        //           ，          
        int count = 0;
        boolean overflow = false;
        while(abs_dividend - abs_divisor >= 0) {
     
            //         
            if (count == maxInt){
     
                overflow = true;
                break;
            }
            count++;
            abs_dividend -= abs_divisor;
        }

        //             
        return overflow == false ? (flag == 1 ? ~count+1 : count) : maxInt;
    }
}