This is the 29th day of my participation in the August Wenwen Challenge.More challenges in August

The title

Leetcode-cn.com/problems/di…

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

10/3 = truncate(3.33333..) = truncate(3) = 3

Example 2:

Input: Dividend = 7, Divisor = -3

Output: – 2

7/-3 = truncate(-2.33333..) = 2 –

 

Tip:

  • Both dividend and divisor are 32-bit signed integers.
  • The divisor is not 0.
  • Assume that our environment can store only 32-bit signed integers with values in the range of [−231, 231 − 1]. In this case, 231 − 1 is returned if the division result overflows.

Their thinking

Two pit

  1. Math.abs

    Be careful with absolute values in this case, because abs(INT_MIN) overflows for 32-bit signed integers. That is, the number -2147483648, itself INT_MIN, is in the range of 32-bit signed integers, but its absolute value 2147483648 is not in the range of 32-bit signed integers.

    Math.abs(dividend) = math.abs (dividend) = math.abs (dividend) = math.abs (Dividend) = math.abs (Dividend) = Math.abs(Dividend) = Math.abs(Dividend)

    The solution is to convert both the dividend and the divisor to negative integers, so that you only need to determine whether the result overflows at the end.

  2. On overflow judgment

    It is also illegal to use integer types whose values exceed Int32, such as unsigned, long, etc. I think this is actually circumventing the question limit. If, in the real world, we don’t have a larger data type to deal with, we can’t get around it.

    So I think there is a problem with the size of int_min as long as the result is directly compared to int_max, such as Max (min), or result>int_max, result<int_min. If result is a 32-bit integer, it cannot be greater than int_max or less than int_min

Principle of displacement operation calculation

The displacement operation can simulate multiplication:

For example, 7 * 13 = 7 * (8 + 4 + 1) = 7 * 8 + 7 * 4 + 7 * 1

Where 8,4, and 1 are 2 to the power 3,2,0, so

= 7 << 3 + 7 << 2 + 7 << 0

When a * x is equal to b (ignoring the remainder for the moment), find x. By the logic of the displacement operation that simulates multiplication above, you can think of X as an array of exponential parts of an integer power of two. If 7 * 13, 13 can be thought of roughly as [3,2,0]. So we can just take this array, and then exponentiate it by 2.

algorithm

Goal:

A times x is equal to b. Find x

Logic:

First find the largest y, the exponential part of y to the power of 2, such that a << y is closest to B, and then set b = b – (a << y) to find the next y. Until all the y’s have been calculated, return an array of all the above y’s and add them together to get the answer.

Example: 3 * x = 10

3 << 1 = 6 and 3 << 2 = 12 because 12 is out of the range of 10, y1 = 1.

And then, 3 times x is equal to 10 minus 3 is less than 1, so 3 times x is equal to 4

Y2 is 0, because 3 is less than 1 is 6, which is more than 4.

And then 4 – (3 << 0) = 4-3 = 1. Since 1 is less than 3, we don’t have to keep looking for y3.

Therefore, the final y-related array is [1,0], then x = 2^1 + 2^0 = 2 + 1 = 3 (note: 2^1 = 1<<1, and 2^ n = 1<< n without overflow, which will not be described below).

next

As you can see from the example above, our ultimate goal is to get an array of y, where each y in the array is actually an exponential of 2. Since we are using 32-bit integers, y is at most 31 (it can be 31, but not 32). So for each y, you’re essentially finding a number between 0 and 32, so that a << y is as close to B as possible. So you can use a dichotomy here, take (32,0) as the upper and lower limits, and then calculate y such that (a << y) <= b and (a << (y+1)) > b. Thus, for any y, at most 5 comparisons can be made to find the value of y (since 32 = 2^5).

legacy

The basic idea is already there, in addition to some boundary logic to deal with, mainly the following:

  1. Final symbol

    The notation actually was mentioned in the comments, but I’m using the divisor and the dividend moved 31 places to the right. You’re essentially taking the sign bit, so 0 is positive, and 1 is negative.

  2. What if overflow occurs when calculating a << y?

    Suppose we now need to compute a << t, and a << t might actually overflow. Here we need to ensure that:

    (a) < < t < 1 < < (31) (if a negative values are used, (a < < t > (1 < < 31), convenient here to understand and adopt positive)

    That is, a should be smaller than 0x80000000 after t bit shift to the left to ensure no overflow. A < (1 << (31-t)) If the value of A is too large, it means that a will overflow if it moves t bits to the left, then t is directly set as the upper limit of the dichotomy.

  3. What if the final results overflow

    The resulting overflow typically occurs only at INT_MIN / -1. The easiest way to do this is to judge the divisor and dividend directly, and short-circuit INT_MAX at the beginning of the program. In view of the above algorithm, in fact, y = 31 is solved, for y = 31, according to the symbol short circuit processing.

  4. Because of the math.abs problem described at the beginning of this article, negative numbers are required for calculation.

    I won’t repeat it here

code

/ * * *@param {number} dividend
 * @param {number} divisor
 * @return {number}* /
var divide = function (dividend, divisor) {
    var INT_MAX = 0x7FFFFFFF;
    var INT_MIN = 1 << 31;

    // check the symbol first
    var symbol = (dividend ^ divisor) >> 31;
    // Due to math.abs (INT_MIN) overflow problem
    // Therefore, both the dividend and divisor are treated as negative numbers
    var _dividend = dividend > 0 ? -dividend : dividend;
    var _divisor = divisor > 0 ? -divisor : divisor;

    var times = divided_negtive(_dividend, _divisor);

    var output = 0;
    for (var i = 0; i < times.length; i++) {
        if (times[i] === 31) {
            // I =31 indicates INT_MIN, times has no second element, and is short-circuited directly
            if (symbol === 0) {
                // if INT_MIN becomes positive, INT_MAX is returned
                return INT_MAX;
            }
            return INT_MIN;
        }
        output += (1 << times[i]);
    }
    return symbol ? -output : output;

};

function divided_negtive(dividend, divisor) {
    // Divide two negative numbers
    When the divisor is less than the dividend, the quotient is 0
    if (divisor < dividend) {
        return [];
    }

    var timesMax = 32;
    var timesMin = 0;
    while(timesMax ! == timesMin +1) {
        // Binary search
        var mid = (timesMax + timesMin) >> 1;
        // Divisor <
        // Check whether the divisor is greater than or equal to -1<<(31-mid)
        if (divisor < (-1< < (31 - mid))) {
            // If mid is too large, assign mid to timesMax for the next half-cut search
            timesMax = mid;
            continue;
        }

        var testVal = divisor << mid;
        if (testVal < dividend) {
            timesMax = mid;
        } else{ timesMin = mid; }}return [timesMin].concat(divided_negtive(dividend - (divisor << timesMin), divisor));
}
Copy the code

The last

I dreamed of traveling with swords

Look at the prosperity of the world

Young heart always some frivolous

Just a man after all

No regrets I go my way

“Front-end brush” No.29