This is the 26th day of my participation in Gwen Challenge

preface

The two numbers of question 29 are divided as follows:

Given two integers, dividend and divisor. Dividing two numbers requires no multiplication, division, and mod operators.

Returns the quotient of dividend divided by divisor.

The result of integer division should truncate the decimal part, for example, TRUNCate (8.345) = 8 and TRUNCate (-2.7335) = -2

Example 1:

Input: Dividend = 10, Divisor = 3 Output: 3 Interpretation: 10/3 = TRUNCate (3.33333..) = truncate(3) = 3

Example 2:

Input: Dividend = 7, Divisor = -3 Output: -2 Explanation: 7/-3 = TRUNCate (-2.33333..) = 2 –

A, thinking

How do you know the result of division if you don’t multiply? And it’s really easy to just add them up. For example, to get 9/4 and so on, just keep adding up the 4, 4 + 4 = 8 < 9 and 4 + 4 + 4 = 12 > 9, so 9/4 = 2

But there’s a problem with doing this over and over again, is that it’s a lot of times. For example, to calculate 100/2 you have to keep adding it up 50 times to get the right answer. In order to reasonably reduce the number of sums, you can use multiplication, which is the result of the next sum multiplied by two. If the sum is larger than the dividend, it gets smaller.

For example

Here, 100/2 is used as an example. The specific steps are as follows:

Ret indicates the returned result. Ret = 0

  1. The first step:2 < 100Ret = 1
  2. The second step:2 + 4 < 100, ret = 1 + 2 = 3
  3. Step 3:2 plus 4 plus 8 is less than 100, ret = 3 + 4 = 7
  4. Step 4:2 plus 4 plus 8 plus 16 is less than 100, ret = 7 + 8 = 15
  5. Step 5:2 plus 4 plus 8 plus 16 plus 32 is less than 100, ret = 15 + 16 = 31
  6. Step 6:2 + 4 + 8 + 16 + 32 + 64 is greater than 100, ret = 31. It’s greater than, and the next time you add it up you have to shrink it down to the point where you can’t add it up
  7. Step 7: At this point, we will try to find the appropriate summation number until we find the appropriate summation number 322 + 4 + 8 + 16 + 32 + 32 is less than 100, ret = 31 + 16 = 47
  8. Step 8: Adding 32 again will be greater than the situation, so it will again look for the appropriate summation number 4, i.e2 + 4 + 8 + 16 + 32 + 32 + 4 is less than 100, ret = 47 + 2 = 49
  9. Step 9: Adding 4 again will be greater than the situation, so it will again look for the appropriate sum of 2,(2 + 4 + 8 + 16 + 32 + 32 + 4) + 2 = 100, ret = 49 + 1 = 50
  10. Finally, the result is returnedret = 50

In the actual implementation process, the comparison value will be converted to long, which is easy to process.

Second, the implementation

The implementation code

To facilitate processing, we first judge the positive and negative values of the final results. The dividend and divisor are then converted to positive numbers for subsequent processing.

/**
     * 倍增法
     */
    public int divide(int dividend, int divisor) {
        // Special circumstances
        if(dividend == 0) return 0;
        if(divisor == 1) return dividend;
        if(divisor == -1) {if(dividend> Integer.MIN_VALUE) return -dividend;
            return Integer.MAX_VALUE;
        }

        / / the result
        int ret = 0;
        / / to long
        long d = dividend;
        long r = divisor;
        // Check the signs
        boolean flag = true;
        if (d > 0 && r < 0 || d < 0 && r > 0) {
            flag = false;
        }
        // Ensure two positive numbers
        d = d < 0 ? -d : d;
        r = r < 0 ? -r : r;
        // Start multiplying
        long temp = 0;
        long add = r;  / / accumulated value
        int multiple = 1;   / / multiple
        while (temp < d || add > r) {
            if (temp == d) {
                break;
            }
            // Select the appropriate summation
            while (temp + add > d) {
                add = add >> 1;
                multiple = multiple >> 1;
            }
            ret += multiple;
            temp += add;
            add += add;
            multiple += multiple;
        }
        // Return the result
        return flag ? ret : -ret;
    }
Copy the code

The test code

    public static void main(String[] args) {
        int ret = new Number29().divide(100 , 2);
        System.out.println(ret);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥