[Python] Detecting Unsigned Addition Overflow with Signed Integers in 2's complement

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.

Continue reading...