Logical shifts and Arithmetic shifts

Here’s a small exercise for you. What’s the output for the following piece of Go code:

n := int64(1)
fmt.Println((n<<63) >> 63)

Take your time. Think about this hard. Ready?

Wait what? You don’t believe me? Check it out yourself on the Go playground.

This should have been a no-op. Then why didn’t we get 1?

So, what’s happening?

Let’s do this again, but this time with uint64 instead of int64.

u := uint64(1)
fmt.Println((u<<63) >> 63) // 1

The different behaviour between uint and int is because Go does a logical shift for unsigned integers, but an arithmetic shift for signed integers.

Logical shifts

Let’s first understand the simple logical shift in unsigned integers.

u := uint8(129) // 0b10000001
u <<= 7         // 0b10000000
u >>= 1         // 0b01000000
u >>= 6         // 0b00000001

Right-shifts “empty” the most significant bits, which are then filled in with 0. Similarly, left-shifts “empty” the least significant bits which are then filled in with 0.

Everything as expected.

Arithmetic shifts

Simply put, arithmetic shifts “preserve”^[*] signedness, whereas logical shifts don’t.

Before we follow along an example, first thing to note is that a right-shift is essentially a division by 2, and a left-shift is multiplication by 2.

Second is to remember that signed integers are stored in two’s complement^[1] form in which the most significant bit is the sign bit.

For a positive integer, the sign bit is 0 and an arithmetic right-shift “preserves” this sign bit. The behaviour ends up being the same as logical right-shift — emptied bits are filled in with 0.

n := int8(15) // 0b00001111 (sign bit is 0)
n >>= 2       // 0b00000011 (sign bit is 0. n = 3, 15/2² = 3)

For a negative integer, the sign bit is 1 and an arithmetic right-shift “preserves” it — emptied bits are filled in with 1.

n := int8(1) // 0b00000001 (sign bit is 0. n = 1)
n <<= 7      // 0b10000000 (sign bit is 1. n = -128)

// sign bit "preserved" on right-shift
n >>= 1      // 0b11000000 (sign bit is 1. n = -64)
n >>= 6      // 0b11111111 (sign bit is 1. n = -1)

1 * 2⁷ = 128

128 is outside of int8 range and the value overflows to -128.

Then, 7-bit right-shift is equivalent to division by 2⁷, and we get:

-128 / 2⁷ = -1

That’s why (1<<63) >> 63 in our original example gives -1.

What about left shifts?

There are arithmetic left-shifts and logical left-shifts as well, but the behaviour ends up being the same.

// unsigned
n := uint8(193) // 0b11000001
n <<= 1         // 0b10000010 (n = 130)
n <<= 1         // 0b00000100 (n = 4)

// signed
n := int8(-63) // 0b11000001
n <<= 1        // 0b10000010 (n = -126)
n <<= 1        // 0b00000100 (n = 4)

In both cases, the sign bit is lost after the second left-shift. The values overflow as intended.

[*] So, technically, arithmetic shifts don’t “preserve” the sign bit in a right-shift. The behaviour is simply the outcome of signed integer arithmetic in two’s complement form.

[1]: Two’s complement