trjhtr

I am trying to write a function in Go which adds an uint64 value and an int64 value and which detects whether the result can be represented as an uint64.

func addUintInt64(x uint64, y int64) (uint64, bool) 
 if y >= 0 
 z := x + uint64(y)
 if z < x 
 return 0, false
 
 return z, true
 else if y == -(1 << 63) 
 if x < 1<<63 
 return 0, false
 
 return x - 1<<63, true
 else 
 negY := uint64(-y)
 if x < negY 
 return 0, false
 
 return x - negY, true
 

(Also on the Go Playground)

The second argument indicates whether the result is in the range of an int64. If this is true, the first argument is the sum of x and y.

My questions:

1. Is this code correct? I tested all boundary cases I could think of, but maybe I overlooked something?




2. Is there a nicer or more obvious looking way to write this code? The fact that I'm not sure whether the code is correct probably indicates that it is not well written.




3. Is there a more efficient way to perform this task? In particular, I would love to get rid of the special case for y == -(1<<63). Note that I don't care about the first result, in cases where the second result is false. Maybe this offers some potential for optimisations?

I really like that you put those tests together in the playground, thanks!

I am not a fan of losing information that may be useful. You will always need to check 0-value results to see if they indicate an overflow/underflow condition, so it's just simpler to return a useful result for those times when overflow is OK.... why return 0 when the actual remaining result is just as good?

More specifically, you will always have code like:

value, ok := addUintInt64(x, y)
if !ok 
 ....

so why force the 0 in to the value for !ok?

In addition, the magnitude of an int64 is never going to exceed half the magnitude of a uint64, so a double-overflow is not possible, and the logic required to check an overflow condition is a case of checking the change, or the direction of the change, of the sign-bit of the equivalent int64 value.

Perhaps this is best described if you handle the complete calculation in int64 space, and convert the result to uint64 - and realize that the MSB of the uint is the sign bit of the int.

The following conditions are all OK:

• the sign bit does not change after the addition, then there's no overflow condition (no possibility of wrap)


• the sign bit changes, but the int value was positive and the source sign bit was not set


• the sign bit changes, but the int value was negative and the source sign bit was set

This is easy to codify in Go as:

result := uint64(int64(x) + y)
before := x >> 63
after := result >> 63
ok := before == after || (before == 0 && y >= 0) || (before == 1 && y < 0)

The above calculates in int64 space, wraps back to uint64 space, and computes the overflow conditions....

Using your same test cases (with the 0 return value for !ok) you can see this in the playground.

I would rather return the result though even if !ok, to avoid the additional check, so it would be the function:

func addUintInt64(x uint64, y int64) (uint64, bool) (before == 0 && y >= 0)