0

I'm trying to detect if there is unsigned overflow when adding the 2's complement representation of 2 signed integers (using a custom SignedInteger class that wraps modulo 2**bits if the value leaves range(-2**(bits - 1), 2**(bits - 1))). My current algorithm looks like

def algorithm(a: SignedInteger, b: SignedInteger, c: SignedInteger) -> bool:
    if (a < 0) == (b < 0): # Are the MSBs the same?
        return a < 0 # Is it 1?
    return c >= 0 # Is the MSB of the sum 0?

used like

c = a+b
algorithm(a, b, c)
# use c for something else

I'm wondering if there is some great optimization to be made, like how this code detects unsigned overflow:

def algorithm(a: UnsignedInteger, b: UnsignedInteger, c: UnsignedInteger) -> bool:
    if (a < 2**bits) == (b < 2**bits):
        return a >= 2**bits
    return c < 2**bits

But this does it much faster, and is easier to understand:

def algorithm(a: UnsignedInteger, b: UnsignedInteger, c: UnsignedInteger) -> bool:
    return c < a

Is there a simpler and more efficient way to do this, analogous to the the c<a trick?

Note that this question is not about detecting signed overflow.

8
  • I don't get the algorithm in your signed version. However, I believe you can do the c < a comparison using the same bit hacks that java users had to use for unsigned comparison before they had a builtin function for that. stackoverflow.com/a/42484776/17167312 Commented Sep 14 at 8:23
  • I think this is a good solution, since there is only 1 comparison, but a 0-comparison solution would be even better. By the way, both adding or subtracting 2**(bits-1) works just as well. Commented Sep 15 at 12:12
  • What do you mean by 0-comparison? Commented Sep 15 at 12:33
  • @Homer512 One without comparisons Commented Sep 15 at 20:53
  • How? I mean, if this was assembly, we'd obviously have the flag register and don't need any extra operation to detect wrap-around. And if you make the overflow detection part of your custom type's addition, then of course you can cause an exception or other callback just like numpy does for its fixed-size types. But then even that, if written in Python, requires a comparison or boolean test of some sort. Commented Sep 15 at 20:59

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.