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.
c < acomparison 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