Difference of arithmetic and logical shifts (illustrated in rust)

✍️ Written on 2020-09-16 in 1779 words.
Part of cs software-development programming-languages rustlang

Motivation

Most programmers eventually learn that “shifts by n” move bit positions to the left or right by n positions. Fundamentally, zeros are inserted in the empty spots, unlike “rotation by n” where the empty spots are fill with the dropped bits. But fewer programmers know the arithmetic shift.

Example in rust

The following rust source code illustrates arithmetic shifting. Recognize that variable a has signed type i8 (arithmetic shift) whereas variable b has unsigned type u8 (logical shift).

fn main() {
  let a = -1i8;
  let b = a as u8;

  println!("{:08b} {:08b}", a, b);
  println!("{:08b} {:08b}", a >> 1, b >> 1);
  println!("{:08b} {:08b}", a >> 2, b >> 2);
}

The output is given by

11111111 11111111
11111111 01111111
11111111 00111111

Rust specifies the behavior in “Arithmetic and Logical Binary Operators”.

Arithmetic right shift on signed integer types, logical right shift on unsigned integer types.

Example in C

#include <stdio.h>
#include <stdint.h>

void print_i(int8_t val) {
    printf("0b");
    for (int i = 8; i > 0; i--) {
        if (i % 4 == 0 && i != 8)
            printf(" ");
        printf("%u", (val & (1 << (i - 1))) > 0);
    }
    printf(" ");
}
void print_u(uint8_t val) {
    printf("0b");
    for (int i = 8; i > 0; i--) {
        if (i % 4 == 0 && i != 8)
            printf(" ");
        printf("%u", (val & (1 << (i - 1))) > 0);
    }
    printf(" ");
}

void li_shift(int8_t a, int8_t b) {
    print_i(a);
    printf("<< %u = ", b);
    print_i(a << b);
    printf(" [%d << %d = %d]\n", a, b, a << b);
}

void lu_shift(uint8_t a, uint8_t b) {
    print_u(a);
    printf("<< %u = ", b);
    print_u(a << b);
    printf(" [%u << %u = %u]\n", a, b, a << b);
}

void ri_shift(int8_t a, int8_t b) {
    print_i(a);
    printf(">> %u = ", b);
    print_i(a >> b);
    printf(" [%d >> %d = %d]\n", a, b, a >> b);
}

void ru_shift(uint8_t a, uint8_t b) {
    print_u(a);
    printf(">> %u = ", b);
    print_u(a >> b);
    printf(" [%u >> %u = %u]\n", a, b, a >> b);
}

int main() {
    printf("unsigned\n");
    printf("========\n\n");

    lu_shift(1, 1);
    lu_shift(2, 1);
    lu_shift(127, 1);
    lu_shift(128, 1);
    lu_shift(255, 1);

    ru_shift(1, 1);
    ru_shift(2, 1);
    ru_shift(127, 1);
    ru_shift(128, 1);
    ru_shift(255, 1);

    printf("\n");
    printf("signed\n");
    printf("======\n\n");

    li_shift(1, 1);
    li_shift(2, 1);
    li_shift(127, 1);
    li_shift(-128, 1);
    li_shift(-1, 1);

    ri_shift(1, 1);
    ri_shift(2, 1);
    ri_shift(127, 1);
    ri_shift(-128, 1);
    ri_shift(-1, 1);
}

The output is given by:

unsigned
========

0b0000 0001 << 1 = 0b0000 0010  [1 << 1 = 2]
0b0000 0010 << 1 = 0b0000 0100  [2 << 1 = 4]
0b0111 1111 << 1 = 0b1111 1110  [127 << 1 = 254]
0b1000 0000 << 1 = 0b0000 0000  [128 << 1 = 256]
0b1111 1111 << 1 = 0b1111 1110  [255 << 1 = 510]
0b0000 0001 >> 1 = 0b0000 0000  [1 >> 1 = 0]
0b0000 0010 >> 1 = 0b0000 0001  [2 >> 1 = 1]
0b0111 1111 >> 1 = 0b0011 1111  [127 >> 1 = 63]
0b1000 0000 >> 1 = 0b0100 0000  [128 >> 1 = 64]
0b1111 1111 >> 1 = 0b0111 1111  [255 >> 1 = 127]

signed
======

0b0000 0001 << 1 = 0b0000 0010  [1 << 1 = 2]
0b0000 0010 << 1 = 0b0000 0100  [2 << 1 = 4]
0b0111 1111 << 1 = 0b1111 1110  [127 << 1 = 254]
0b1000 0000 << 1 = 0b0000 0000  [-128 << 1 = -256]
0b1111 1111 << 1 = 0b1111 1110  [-1 << 1 = -2]
0b0000 0001 >> 1 = 0b0000 0000  [1 >> 1 = 0]
0b0000 0010 >> 1 = 0b0000 0001  [2 >> 1 = 1]
0b0111 1111 >> 1 = 0b0011 1111  [127 >> 1 = 63]
0b1000 0000 >> 1 = 0b1100 0000  [-128 >> 1 = -64]
0b1111 1111 >> 1 = 0b1111 1111  [-1 >> 1 = -1]

Arithmetic shift

In essence,

  1. A logical right shift by n moves bits from right to left by n positions and the first n leftmost bits become zero.

  2. The right column in the rust output and the first block in the C output show a logical shift.

  3. But signed types use the leftmost bit to store the sign bit. 1 defines a negative number. 0 defines a positive number.

  4. Instead of inserting a zero on the left-hand side, some 1 inserted for negative numbers. This retains the sign of the number and hence its name “arithmetic”.

  5. The left column in the rust output and the second block in the C output shows an arithmetic shift.