Difference of arithmetic and logical shifts (illustrated in rust)

✍️ → Written on 2020-09-16 in 596 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 whereas variable b has unsigned type u8.

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);
}

Arithmetic shift

In essence,

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

  2. The right column in the source code above shows a logical right shift.

  3. But signed types use the leftmost bit to store the sign bit. 1 defines a negative number. 0 defines a positive number. Above, all numbers in the left column are negative.

  4. The left column in the source code above shows an arithmetic right shift.

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