Subtracting NULL pointer from a normal pointer generates arithmetic right shift

Question

Here is the C code.

int main() {
  int i = 10, *p = &i;
  printf("%ld", p - (int *) NULL);
}

For the pointer arithmetic part, both 'gcc' and 'clang' generate an 'sar rax, 2' instruction in their assembly output. Could someone explain how pointer arithmetic in this case is related to an arithmetic right shift.

Answer 1

Right-shifting by 2 is a fast way to do division by 4. 4 is your int size.

The distance of two pointers to int is the distance of two char pointers corresponding to the int pointers divided by int size (remember, when adding an integer to a pointer,the integer is scaled by pointer-target size, so when you do diffing, you need to undo this scaling).

Technically, you shouldn't be subtracting two unrelated pointers (or printing the difference with "%ld" instead of the proper "%zd") as that's undefined behavior—the standard only allows you to diff pointers pointing to the same object or just past it. Nevertheless, a generic int*-diffing function that doesn't have such undefined behavior by itself:

#include <stddef.h>

ptrdiff_t diff_int_ptr(int *A, int *B)
{
    return A-B;
}

will still translate to the equivalent of

ptrdiff_t diff_int_ptr(int *A, int *B)
{
    return ((char*)A - (char*)B) >> lg2(sizeof(int));
    //strength reduced from: return ((char*)A - (char*)B) / sizeof(int)
    //which is possible iff sizeof(int) is a power of 2
}

on an optimizing compiler (godbold link for x86-64 gcc and clang) as shifting is usually over 10 times faster than division on a modern machine.