267 votos

Techo rápido de una división de enteros en C / C++

Dado valores enteros x y y, C y C++ tanto el retorno como el cociente q = x/y el piso de la de punto flotante equivalente. Estoy interestd en un método de devolver el techo en su lugar. Por ejemplo, ceil(10/5) = 2 y ceil(11/5) = 3.

La solución obvia consiste en algo así como:

q = x / y;
if (q * y < x) ++q;

Esto requiere un extra de comparación y la multiplicación; y otros métodos que yo he visto (utilizados en) involucrar a los casting como float o double. Hay un método más directo que evita el adicional de la multiplicación (o una de segunda división y de las sucursales, y que también se evita la fundición como un número de punto flotante?

402voto

Sparky Puntos 4660

Para redondear...

q = (x + y - 1) / y;

o (evitando el desbordamiento en x + y)

q = 1 + ((x - 1) / y); // if x != 0

82voto

Para números positivos:

    q = x/y + (x % y != 0);

59voto

Jørgen Fogh Puntos 3579

Sparky respuesta de una forma estándar para resolver este problema, pero como también escribí en mi comentario, se corre el riesgo de desbordamientos. Esto puede ser resuelto mediante el uso de un amplio tipo, pero lo que si queremos dividir long longs?

Nathan Ernst respuesta proporciona una solución, pero implica una llamada a una función, una declaración de variable y de un condicional, que le hace no más corta que la OPs código y, probablemente, aún más lento, debido a que es más difícil de optimizar.

Mi solución es esta:

q = (x % y) ? x / y + 1 : x / y);

Va a ser un poco más rápida que la OPs código, debido a que el modulo y la división se realiza utilizando la misma instrucción en el procesador, ya que el compilador puede ver que son equivalentes. Al menos gcc 4.4.1 lleva a cabo esta optimización con-O2 bandera en x86.

En teoría, el compilador podría en línea de la llamada a la función en Nathan Ernst código y emiten la misma cosa, pero gcc no que cuando lo probé. Esto podría ser debido a que atar el código compilado para una única versión de la biblioteca estándar.

Como nota final, nada de esto importa en una moderna máquina, excepto si usted está en un muy apretado lazo y todos sus datos en los registros o de la L1-cache. De lo contrario, todas de estas soluciones va a ser igual de rápida, excepto, posiblemente, Nathan Ernst, que podría ser significativamente más lento si la función tiene que ser recuperado de la memoria principal.

18voto

Nathan Ernst Puntos 3079

Podrías usar el div función en cstdlib para obtener el cociente y el resto en una sola llamada y luego manejar el techo por separado, como en la continuación

#include <cstdlib>
#include <iostream>

int div_ceil(int numerator, int denominator)
{
        std::div_t res = std::div(numerator, denominator);
        return res.rem ? (res.quot + 1) : res.quot;
}

int main(int, const char**)
{
        std::cout << "10 / 5 = " << div_ceil(10, 5) << std::endl;
        std::cout << "11 / 5 = " << div_ceil(11, 5) << std::endl;

        return 0;
}

12voto

Ben Voigt Puntos 151460

¿Qué hay de esto? (requiere y no negativo, así que no lo uso esta en el raro caso en que y es una variable con el no-negatividad de garantía)

q = (x > 0)? 1 + (x - 1)/y: (x / y);

He reducido y/y a uno, eliminando el término x + y - 1 y con ella cualquier posibilidad de desbordamiento.

I evite x - 1 envoltura alrededor cuando x es un entero de tipo y contiene cero.

Para firmada x, negativa y cero combinar en un único caso.

Probablemente no es un beneficio enorme en un moderno de propósito general de la CPU, pero esto sería mucho más rápido en un sistema embebido que cualquiera de las otras respuestas correctas.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X