overflow handle in Python

Question

Working on below algorithm puzzle and it requires to handle situation of overflow. I am confused by this line, min(max(-2147483648, res), 2147483647), if anyone could comment how it handles overflow, it will be great. :)

BTW, I am still confused why there will be overflow in Python when we are doing two integer divide calculation?

Post detailed problem statement and solutions,

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

class Solution:
# @return an integer
def divide(self, dividend, divisor):
    positive = (dividend < 0) is (divisor < 0)
    dividend, divisor = abs(dividend), abs(divisor)
    res = 0
    while dividend >= divisor:
        temp, i = divisor, 1
        while dividend >= temp:
            dividend -= temp
            res += i
            i <<= 1
            temp <<= 1
    if not positive:
        res = -res
    return min(max(-2147483648, res), 2147483647)

It doesn't. It just clamps the result between min and max value of a 32-bit integer. — Caramiriel, Dec 14 '15 at 07:56
@LinMa [There's no integer overflow in Python](http://stackoverflow.com/questions/4581842/python-integer-ranges) like that you may have seen in other programming languages. The final line of your given code simply ensures that the returned value will fit within a 32-bit integer. — FThompson, Dec 14 '15 at 08:01
@Vulcan, thanks, but I am still confused, why in other programming language, integer division (if return results are also integer) will cause overflow? — Lin Ma, Dec 14 '15 at 08:05
@LinMa In Java, for example, `int` values are strictly limited to a 32-bit value. Similarly, `long` values are strictly 64-bit. Any arithmetic that would lead to a value larger than allowed, therefore, results in overflow. Python integers, meanwhile, have arbitrary precision (see previous linked question) and thus no arithmetic will exceed the range of values, meaning overflow cannot occur in Python. — FThompson, Dec 14 '15 at 08:08
@Vulcan, good catch, and understand Java integer is 32 bit. But I cannot think about an example, where two 32-bit integer divide, which will cause an integer larger than 32 bit, which will cause overflow. If you could show an example, it will be great. :) — Lin Ma, Dec 14 '15 at 08:18
@LinMa As far as I know, there's no way for overflow to occur through division. I don't see how limiting discussion to division is relevant, though; your question's problem appears to define overflow as anything beyond the 32-bit register, but that doesn't mean that overflow, in the general sense of the term, can occur through division. — FThompson, Dec 14 '15 at 17:37
@Vulcan, thanks for the clarification, for your comments, "as anything beyond the 32-bit register", I am still a bit confused, could you clarify what you mean by an example? Thanks. — Lin Ma, Dec 14 '15 at 20:00
@LinMa Anything beyond the 32-bit register = any integer larger than 32 bits. — FThompson, Dec 14 '15 at 20:15
@Vulcan, thanks for the clarification, but how could it happen for 32-bit integer divide operation? Could you show me an example, what are numerator and denominator? Thanks. — Lin Ma, Dec 14 '15 at 22:29
@LinMa It's not possible for overflow to occur when dividing two 32-bit integers, as far as I know. — FThompson, Dec 15 '15 at 00:38
@Vulcan, understand, and my question is not on my original question, but for your comments, "overflow as anything beyond the 32-bit register", what means overflow a 32-bit register? Could you show an example? Thanks. If I catch your points not correctly, please feel free to correct me. :) — Lin Ma, Dec 15 '15 at 01:07
@LinMa `2147483647 + 1` would cause overflow between two 32-bit integers. By "the 32-bit register" I simply mean the available 32-bits. — FThompson, Dec 15 '15 at 01:24
@Vulcan, thanks for the clarification, but `2147483647 + 1` will not happen when divide two 32-bit integers, correct? :) — Lin Ma, Dec 15 '15 at 01:30
@LinMa Correct. I don't see how division is relevant to this discussion. — FThompson, Dec 15 '15 at 01:38
@Vulcan, thanks a lot. If you could add a reply to my question, I will mark it as answered to benefit other people. :) — Lin Ma, Dec 15 '15 at 01:54

score 2 · Accepted Answer · answered Dec 14 '15 at 07:59

2

min(max(-2147483648, res), 2147483647)

This is a combination of these two things:

result = max(-2147483648, res)
min(result, 2147483647)

The functions max and min return the maximum and minimum number respectively of those that are passed to them.

In the case of the max() call, if res is above -2147483648, then the value of res is returned. Otherwise, if the number is lower, then that big negative number is returned. This ensures that the lowest number that is returned from the max() call is -2147483648. If res is larger, fine, otherwise it will take that number as the lowest boundary.

The min() call does exactly the opposite. It establishes a maximum boundary of 2147483647 by returning that number if res is larger than it.

Combined, those function calls make sure that -2147483648 <= res <= 2147483647.

Finally note, that in Python, integers are not really limited in size. So those boundaries are just enforced without actually being needed (at least for Python), so if this is required for the puzzle solution, it’s probably a requirement by the puzzle.

answered Dec 14 '15 at 07:59

poke

369,085
72
557
602

Thanks poke, wondering why in other programming language, integer division (if return results are also integer) will cause overflow? An example is appreciated. Either Java or C/C++ is fine. :) – Lin Ma Dec 14 '15 at 08:06
1

In most other languages, the integer types have a fixed size. For example in Java, `int` is a 32bit integer, so it’s pretty simple to get an overflow there. But Python does have unlimited integers, so there is no overflow that could happen (at least not from Python integers). – poke Dec 14 '15 at 08:14
Thanks poke, good catch, and understand Java integer is 32 bit. But I cannot think about an example, where two 32-bit integer divide, which will cause an integer larger than 32 bit, which will cause overflow. If you could show an example, it will be great. :) – Lin Ma Dec 14 '15 at 08:18
1

@LinMa Judging by other solutions in other languages when googling your problem statement, it seems that you should check whether `divisor` is zero (otherwise your solution will not complete) and in that case return that constant number. But then again, that task seems very specific to other languages that have to deal with certain problems Python simply doesn’t have, so trying to apply the restrictions from those other languages into your Python solution seems like a bad idea anyway. – poke Dec 15 '15 at 19:08

overflow handle in Python

1 Answers1