How does 1 << 64 - 1 work?

At http://tour.golang.org/#14 they show an example where the number 1 is shifted by 64 bits. This of course would result in an overflow, but then it is subtracted by 1 and all is well. How does half of the expression result in a failure while the entire expression as whole work just fine?

Thoughts:
I would assume that the setting of the unsigned to a number larger than what it allows is what causes the explosion. It would seem that memory is allocated more loosely on the right hand side of the expression than on the left? Is this true?

The result of your expression is a (compile time) constant and the expression is therefore evaluated during compilation. The language specification mandates that

> 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. The
> following are legal declarations:
>
> const Huge = 1 << 100 // Huge == 1267650600228229401496703205376 (untyped integer constant)
> const Four int8 = Huge >> 98 // Four == 4 (type int8)

https://golang.org/ref/spec#Constant_expressions

That is because the Go compiler handles constant expressions as numeric constants. Contrary to the data-types that have to obey the law of range, storage bits and side-effects like overflow, numeric constants never lose precision.

Numeric constants only get deduced down to a data-type with limited precision and range at the moment when you assign them to a variable (which has a known type and thus a numeric range and a defined way to store the number into bits). You can also force them to get deduced to a ordinary data-type by using them as part of a equation that contains non Numeric constant types.

Confused? So was I..

Here is a longer write-up on the data-types and how constants are handled: http://www.goinggo.net/2014/04/introduction-to-numeric-constants-in-go.html?m=1

I decided to try it. For reasons that are subtle, executing the expression as a constant expression (1 << 64 -1) or piece by piece at run time gives the same answer. This is because of 2 different mechanisms. A constant expression is fully evaluated with infinite precision before being assigned to the variable. The step by step execution explicitly allows overflows and underflows through addition, subtraction and shift operations, and thus the result is the same.

See https://golang.org/ref/spec#Integer_overflow for a description of how integers are supposed to overflow.

However, doing it in groups, ie 1<<64 and then -1 causes overflow errors!

You can make a variable overflow though arithmetic, but you can not assign an overflow to a variable.

Try it yourself. Paste the code below into http://try.golang.org/

This one works:

// You can edit this code!
// Click here and start typing.
package main

import "fmt"

func main() {
  var MaxInt uint64 = 1
  MaxInt = MaxInt << 64
  MaxInt = MaxInt  - 1
  fmt.Println("%d",MaxInt)
}

This one doesn't work:

// You can edit this code!
// Click here and start typing.
package main

import "fmt"

func main() {
  var MaxInt uint64 = 1 << 64
  MaxInt = MaxInt  - 1
  fmt.Println("%d",MaxInt)
}

Actually 1 << 64 - 1 does not always result in a left shift of 64 and minus 1. The - operator is applied before the << operator in most languages, at least in any I know (like C++, Java, ...). Therefore 1 << 64 - 1 <=> 1 << 63.

But Go behaves different: https://golang.org/ref/spec#Operator_precedence

The - operator comes after the << operator.

The result of a 64 Bit left shift is based on the data type. It's just like adding 64 of 0 on the right, while cutting any Bit that extend the data type on the left side. In some languages an overflow may be valid, in some other not.

Compilers may also behave different based on the interpretion when your shift is greater or equal than the actual data type size. I know that the Java compiler will reduce the actual shift as often by size of the data type until it's smaller than the size of the data byte.

Sounds difficult, but here and easy example for a long data type with 64 Bit size.

so i << 64 <=> i << 0 <=> i

or i << 65 <=> i << 1

or i << 130 <=> i << 66 <=> i << 2.

As said, this may differ with different compilers / languages. There is never a solid answer without refering to a certain language.

For learning I would suggest a more common language than Go, maybe like something from the C family.

var MaxInt uint64 = 1<<64 - 1

BITSHIFTING
In binary, 1, with 64 0s after it (10000...).
Same as 2^64.

This maxes out 64-bit unsigned integer (positive numbers only).
So, we subtract 1 to prevent the error.
Therefore, this is the maximum value unsigned integer we can write.

You can see here go constant int actually is a bigInt, so 1 << 63 won't overflow. But var a int64 = 1 << 63 will overflow, because you are a assign a value bigger than int64.