Which kind of signed integer division corresponds to bit shift?

Question

It is a familiar fact that when dividing integers by a power of two, a good compiler will strength-reduce this to bit shift.

For example:

int main(int argc, char **argv) {
    return argc/2;
}

Clang -O2 compiles this to:

movl    %ecx, %eax
shrl    $31, %eax
addl    %ecx, %eax
sarl    %eax
retq

It is worth noting that while this sequence of instructions is much faster than an actual divide instruction, it is not just a single bit shift as one would hope. Presumably that is because typical CPUs, along with C, ended up settling on truncating division (quotient rounds towards zero), and this happens not to exactly match arithmetic right shift (and the strength reduction is required to exactly preserve the semantics).

Which flavor of signed integer division would exactly match arithmetic right shift?

Answer 1

In case arithmetic shift right is performed, floor by power of 2 is the best suitable operation which matches signed integer shift right (rounding toward -inf).

Note that shift right of signed integer is implementation defined. It may be either arithmetic shift right (implemented by most of the well known compilers) or logical shift right. More about the difference between those two operations can be found here.

Example with arithmetic shift right: https://godbolt.org/z/zhhfbc

#include <stdio.h>
#include <math.h>

int main(void)
{
    int val1 = 7;
    int val2 = -7;
    
    printf("Value1 = %.1lf\n", floor(val1/2.0));
    printf("Value2 = %.1lf\n", floor(val2/2.0));

    printf("Value1 = %d\n", val1 >> 1);
    printf("Value2 = %d\n", val2 >> 1);  

    return 0;
}

And the output is:

Value1 = 3.0

Value2 = -4.0

Value1 = 3

Value2 = -4