I've been learning a little bit of assembly, and I know that compilers can optimize. I know that a compiler can optimize something like
int i;
i /= 2;
to
; suppose i is in eax
sar eax, 1
Not knowing about more optimizations, I assume that
int i;
i /= 3;
would become
; suppose i is in eax
xor edx, edx
mov ecx, 3
idiv ecx
but instead, I get an interesting chain of multiplications and shifts:
; copied from Compiler Explorer, number is in rsi
mov rax, rsi
imul rsi, rsi, 1431655766
sar eax, 31
shr rsi, 32
sub esi, eax
How does this optimization work? Here's the link to Compiler Explorer.