So I know when you do x mod 2^n for unsigned operations, the compiler will simply convert that operation into x & (2^n - 1).
But when I look at the compiler implementation using signed numbers, e.g.
int signed_rem8(int x) { return x %8; }
I get something like this (https://godbolt.org/z/xY3Ef6WEc):
movl -4(%rbp), %eax
cltd
shrl $29, %edx
addl %edx, %eax
andl $7, %eax
subl %edx, %eax
What is the logic behind this?
This is due to the behaviour of the modulo operator with negative numbers.
The behaviour of this operator is such that a/b is rounded towards zero and a%b returns a number such that (a/b)*a + a%b is equal to a (cf. ISO/IEC 9899:2011 §6.5.5 ¶6). As “rounding towards zero” means to round up for negative results and down for positive results, this effectively means that the remainder takes the sign of the numerator.
To implement this behaviour correctly, the compiler makes use of the cltd instruction (sign-extending eax into edx:eax) as follows:
movl -4(%rbp), %eax # load numerator x
cltd # edx = x >= 0 ? 0 : -1
shrl $29, %edx # edx = x >= 0 ? 0 : 7
addl %edx, %eax # eax = x >= 0 ? x : x + 7
andl $7, %eax # eax = x >= 0 ? x&7 : x-1 & 7
subl %edx, %eax # eax = x >= 0 ? x&7 : (x-1 & 7) - 7
So in case of a positive number, we get a positive remainder in the range 0 to 7 while in case of a negative number we get a negative remainder in the range −7 to 0.
In both cases, the remainder is numerically correct as the remainder is supposed to be a representant of the residue class x mod 8, and both the positive and the negative remainders are that.
You might see other compilers solve this with slightly different code, but the general idea is similar.