Así que sé que cuando haces x mod 2^n para operaciones sin firmar, el compilador simplemente convertirá esa operación en x & (2^n - 1) .
Pero cuando miro la implementación del compilador usando números con signo, por ejemplo
int signed_rem8(int x) { return x %8; }Me sale algo como esto ( https://godbolt.org/z/xY3Ef6WEc ):
movl -4(%rbp), %eax cltd shrl $29, %edx addl %edx, %eax andl $7, %eax subl %edx, %eax¿Cuál es la lógica detrás de esto?
Esto se debe al comportamiento del operador módulo con números negativos.
El comportamiento de este operador es tal que a/b se redondea hacia cero y a%b devuelve un número tal que (a/b)*a + a%b es igual a a (cf. ISO/IEC 9899:2011 §6.5 .5 ¶6). Como “redondear hacia cero” significa redondear hacia arriba para resultados negativos y hacia abajo para resultados positivos, esto significa que el resto toma el signo del numerador.
Para implementar este comportamiento correctamente, el compilador hace uso de la instrucción cltd ( eax que extiende el signo a edx:eax ) de la siguiente manera:
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) - 7Entonces, en el caso de un número positivo, obtenemos un resto positivo en el rango de 0 a 7, mientras que en el caso de un número negativo, obtenemos un resto negativo en el rango de −7 a 0.
En ambos casos, el resto es numéricamente correcto ya que se supone que el resto es un representante de la clase de residuo x mod 8, y tanto el resto positivo como el negativo lo son.
Es posible que vea que otros compiladores resuelven esto con un código ligeramente diferente, pero la idea general es similar.