Why doesn't left bit shifting by 64 overflow in golang?

Question

I was taking a look at A Tour of Go and I was confused by something in their basic-types.go example:

MaxInt uint64     = 1<<64 - 1

Shouldn't shifting a 1 64 positions to the left in an unsigned 64 bit integer cause overflow (a.k.a. shifting a bit past the MSB)?

However, the compiler doesn't complain until the line is changed to:

MaxInt uint64     = 1<<65 - 1

./basic-types.go:5: constant 36893488147419103231 overflows uint64

If I write some code to iterate over left shifts of varying lengths, including shifting by 65 as in the above example that causes the compiler to barf, I see two things:

1. It behaves as I expected, in that 1<<63 places the 1 in the MSB possible for an uint64

2. It doesn't overflow anymore (huh?!?!)

code:

package main

import "fmt"

func main() {
    for i := 60; i < 66; i++ {
        var j uint64 = 1 << uint64(i) - 1
        fmt.Printf("%2d | %64b | %#18x\n", i, j, j)

    }

output:

60 |     111111111111111111111111111111111111111111111111111111111111 |  0xfffffffffffffff
61 |    1111111111111111111111111111111111111111111111111111111111111 | 0x1fffffffffffffff
62 |   11111111111111111111111111111111111111111111111111111111111111 | 0x3fffffffffffffff
63 |  111111111111111111111111111111111111111111111111111111111111111 | 0x7fffffffffffffff
64 | 1111111111111111111111111111111111111111111111111111111111111111 | 0xffffffffffffffff
65 | 1111111111111111111111111111111111111111111111111111111111111111 | 0xffffffffffffffff

Answer 1

When you write

1<<64

The 1 above is not an int64. It is a constant literal. From the language specs:

Constant expressions are always evaluated exactly; intermediate values and the constants themselves may require precision significantly larger than supported by any predeclared type in the language.

Thus, a constant literal is evaluated at compile time and can be very large because it is not a specific type of the language implementation.

Below will in fact give an overflow error:

var i int64
i = 1<<65 - 1

Because now the constant literal expression evaluates to a value greater than that an int64 can contain.

Read more about this here.

To know why your example code works for i = 65, refer to the below specification from the Golang specs:

The right operand in a shift expression must have unsigned integer type or be an untyped constant that can be converted to unsigned integer type. If the left operand of a non-constant shift expression is an untyped constant, it is first converted to the type it would assume if the shift expression were replaced by its left operand alone.

The blod part above concerns your code. Consider the code below:

a := 66
var j uint64 = 1<<uint64(a) - 1

Here in the shift operator, the right operand is a non-constant exrpession. So the whole shift operation becomes non-constant shift expression. Thus, as described above, the left operand, 1 is converted to a uint64.

Now, the shift is being done on uint64(1), which can be shifted using << to as many places as you want. You can shift it beyond 64 bits, and the implementation will easily allow it. But in this case the memory that's holding the uint64(1) above will contain all zeros.

Note that this behavior is not the same thing as an overflow as per the language specifications. Again, the language implemntation allows for as many shifts as long as the right operator is not a constant expression. So for example, this will work:

a := 6666
var j uint64 = 1<<uint64(a) - 1 // non-constant shift expression

Think about it this way. Earlier, the 1 was untyped. It had an arbitrary precision (implementation dependent) and the whole number was being returned (all the bits). Now, since it is a uint64, only the first 64 bits are being taken into consideration.

This still causes an overflow because the left operand 1 is untypes and can contain a large number of bits, returning a value too large for a uint64:

var j uint64 = 1<<uint64(66) - 1 // overflow. Note that uint64(64)
fmt.Println(j)                   // is typed, but it's still a constant