Detect signed int overflow in Go

Question

I'm building a Lisp, and I want 32 bit integers to automatically switch to 64 bit integers if a computation would cause them to otherwise overflow. And likewise, for 64 bit overflows, switch to arbitrarily sized integers.

The problem I have is that I don't know what the "correct" way is to detect an integer overflow.

a, b := 2147483647, 2147483647
c := a + b

How can I efficiently check if c overflowed?

I have considered always converting to 64 bit values to do the calculation, then down-sizing again afterwards when possible, but that seems expensive and memory wasteful for something that is as primitive and core to the language as basic arithmetic.

Solution 1

For example, to detect 32-bit integer overflow for addition,

package main

import (
    "errors"
    "fmt"
    "math"
)

var ErrOverflow = errors.New("integer overflow")

func Add32(left, right int32) (int32, error) {
    if right > 0 {
        if left > math.MaxInt32-right {
            return 0, ErrOverflow
        }
    } else {
        if left < math.MinInt32-right {
            return 0, ErrOverflow
        }
    }
    return left + right, nil
}
func main() {
    var a, b int32 = 2147483327, 2147483327
    c, err := Add32(a, b)
    if err != nil {
        // handle overflow
        fmt.Println(err, a, b, c)
    }
}

Output:

integer overflow 2147483327 2147483327 0

Solution 2

For 32 bit integers, the standard way is as you said, to cast to 64 bit, then down size again [1]:

package main

func add32(x, y int32) (int32, int32) {
   sum64 := int64(x) + int64(y)
   return x + y, int32(sum64 >> 31)
}

func main() {
   {
      s, c := add32(2147483646, 1)
      println(s == 2147483647, c == 0)
   }
   {
      s, c := add32(2147483647, 1)
      println(s == -2147483648, c == 1)
   }
}

However if you don't like that, you can use some bit operations [2]:

func add32(x, y int32) (int32, int32) {
   sum := x + y
   return sum, x & y | (x | y) &^ sum >> 30
}

1. https://github.com/golang/go/blob/go1.16.3/src/math/bits/bits.go#L368-L373
2. https://github.com/golang/go/blob/go1.16.3/src/math/bits/bits.go#L380-L387

Comments

[d11wtq]

Thanks! I think I might have a shorter solution, but not sure if there are edge cases where it doesn't work: ((c < a) != (b < 0)), where c := a + b.