C ++ La mejor manera de obtener división y resto de enteros

103

Solo me pregunto, si quiero dividir a por b, y estoy interesado tanto en el resultado c como en el resto (por ejemplo, digo que tengo un número de segundos y quiero dividirlo en minutos y segundos), ¿cuál es la mejor manera de hacerlo?

Podría ser

int c = (int)a / b;
int d = a % b;

o

int c = (int)a / b;
int d = a - b * c;

o

double tmp = a / b;
int c = (int)tmp;
int d = (int)(0.5+(tmp-c)*b);

o

tal vez hay una función mágica que le da a uno a la vez?

Galleta
fuente
5
todas las respuestas a continuación parecen razonables, solo me gustaría agregar que cualquier tontería con double(su último elemento) me parece una mala idea, terminará con números que no se alinean y pueden costarle rendimiento y tamaño ejecutable (siempre fue un problema para mí en ciertos sistemas integrados).
2011
2
La tercera es una opción MALA: ¿y si tmp = 54,999999999999943157? Dicho esto, el casting al estilo antiguo nunca es algo inteligente.
jimifiki

Respuestas:

98

En x86, el resto es un subproducto de la división en sí, por lo que cualquier compilador medio decente debería poder usarlo (y no divvolver a realizarlo ). Probablemente esto también se haga en otras arquitecturas.

Instrucción: DIVsrc

Nota: división sin firmar. Divide el acumulador (AX) por "src". Si el divisor es un valor de byte, el resultado se coloca en AL y el resto en AH . Si el divisor es un valor de palabra, entonces DX: AX se divide por "src" y el resultado se almacena en AX y el resto se almacena en DX .

int c = (int)a / b;
int d = a % b; /* Likely uses the result of the division. */
cnicutar
fuente
9
Creo que mucha gente sabe de la escuela primaria que al hacer una división se obtiene el resto gratis. La verdadera pregunta es: ¿nuestros compiladores son lo suficientemente inteligentes como para aprovechar esto?
1
@jdv: No me sorprendería. Es una optimización muy simple.
Jon Purdy
68
Probé una prueba rápida. Con g ++ 4.3.2 usando -O2, la salida del ensamblador lo muestra claramente usando una idivlinstrucción y usando los resultados en eax y edx. Me habría sorprendido si no fuera así.
Fred Larson
2
@EuriPinhollow De acuerdo, esto no es una pregunta sobre x86. Solo lo di como ejemplo, con el supuesto muy dudoso de que otras arquitecturas probablemente hagan algo similar.
cnicutar
3
Sin embargo, necesita decirle al compilador que optimice, al menos para g ++. Un simple experimento con g ++ 6.3.0 en x86_64 reveló que sin optimización alguna, obtienes dos idivlinstrucciones, pero con -O1o más, obtienes una. Como dice el manual, “Sin ninguna opción de optimización… las declaraciones son independientes” .
Tom Zych
80

std::div devuelve una estructura con resultado y resto.

pezcode
fuente
5
Tengo curiosidad por saber si esto es realmente más eficiente que, digamos, la opción 1 en un compilador moderno.
Greg Howell
2
Bien, no lo sabía. Es mas rapido?
Agradable. ¿Sabría usted si uno se implementa durante mucho tiempo en algún lugar?
Cookie
@Cookie: C ++ 03 no tiene el concepto de long long, pero es muy probable que su compilador tenga una long longsobrecarga std::divcomo extensión.
ildjarn
@Greg: No creo que lo sea, dado que lo más probable es que tenga que escribir resultados en una estructura en la memoria y devolverlo, lo cual (a menos que se compile como en línea y el acceso a la estructura esté optimizado) es una penalización mayor que hacer una instrucción de división adicional.
pezcode
28

En x86 al menos, g ++ 4.6.1 solo usa IDIVL y obtiene ambos de esa única instrucción.

Código C ++:

void foo(int a, int b, int* c, int* d)
{
  *c = a / b;
  *d = a % b;
}

código x86:

__Z3fooiiPiS_:
LFB4:
    movq    %rdx, %r8
    movl    %edi, %edx
    movl    %edi, %eax
    sarl    $31, %edx
    idivl   %esi
    movl    %eax, (%r8)
    movl    %edx, (%rcx)
    ret
Peter Alexander
fuente
¿Importa el orden? Por ejemplo, si está iterando sobre un /=, es posible que deba usar una variable temporal para mantener la división primero.
AnnanFay
@Annan No importaba en ese entonces, y no importa hoy en día. Los compiladores son lo suficientemente inteligentes como para reordenarlo.
Sahsahae
10

Ejemplo de prueba de código div () y división y mod combinados. Los compilé con gcc -O3, tuve que agregar la llamada a doNothing para evitar que el compilador optimizara todo (la salida sería 0 para la solución division + mod).

Tómelo con un grano de sal:

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>

extern doNothing(int,int); // Empty function in another compilation unit

int main() {
    int i;
    struct timeval timeval;
    struct timeval timeval2;
    div_t result;
    gettimeofday(&timeval,NULL);
    for (i = 0; i < 1000; ++i) {
        result = div(i,3);
        doNothing(result.quot,result.rem);
    }
    gettimeofday(&timeval2,NULL);
    printf("%d",timeval2.tv_usec - timeval.tv_usec);
}

Salidas: 150

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>

extern doNothing(int,int); // Empty function in another compilation unit

int main() {
    int i;
    struct timeval timeval;
    struct timeval timeval2;
    int dividend;
    int rem;
    gettimeofday(&timeval,NULL);
    for (i = 0; i < 1000; ++i) {
        dividend = i / 3;
        rem = i % 3;
        doNothing(dividend,rem);
    }
    gettimeofday(&timeval2,NULL);
    printf("%d",timeval2.tv_usec - timeval.tv_usec);
}

Salidas: 25

Greg Howell
fuente
3

En igualdad de condiciones, la mejor solución es aquella que exprese claramente su intención. Entonces:

int totalSeconds = 453;
int minutes = totalSeconds / 60;
int remainingSeconds = totalSeconds % 60;

es probablemente la mejor de las tres opciones que presentó. Sin embargo, como se señaló en otras respuestas, el divmétodo calculará ambos valores a la vez.

Jon
fuente
3

No puede confiar en g ++ 4.6.3 aquí con enteros de 64 bits en una plataforma Intel de 32 bits. a / b se calcula mediante una llamada a divdi3 y a% b se calcula mediante una llamada a moddi3. Incluso puedo ofrecer un ejemplo que calcule a / by ab * (a / b) con estas llamadas. Entonces uso c = a / by ab * c.

El método div da una llamada a una función que calcula la estructura div, pero una llamada de función parece ineficaz en plataformas que tienen soporte de hardware para el tipo integral (es decir, enteros de 64 bits en plataformas Intel / amd de 64 bits).

brac37
fuente
-4

Puede usar un módulo para obtener el resto. Aunque la respuesta de @cnicutar parece más limpia / más directa.

Sinthet
fuente
2
Sí, el póster original usó el operador de módulo, la pregunta es cómo hacerlo eficiente.
Mark Lakata