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

Dados los valores enteros xy y, C y C ++, ambos devuelven como cociente q = x/yel piso del equivalente de coma flotante. Estoy interesado en un método para devolver el techo en su lugar. Por ejemplo, ceil(10/5)=2y ceil(11/5)=3.

El enfoque obvio implica algo como:

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

Esto requiere una comparación y multiplicación extra; y otros métodos que he visto (de hecho) involucran la conversión como floato double. ¿Existe un método más directo que evite la multiplicación adicional (o una segunda división) y la ramificación, y que también evite la conversión como un número de coma flotante?

Para números positivos

unsigned int x, y, q;

Para resumir ...

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

o (evitando el desbordamiento en x + y)

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

Para números positivos:

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

La respuesta de Sparky es una forma estándar de resolver este problema, pero como también escribí en mi comentario, corre el riesgo de desbordamientos. Esto se puede resolver utilizando un tipo más amplio, pero ¿qué pasa si desea dividir long longs?

La respuesta de Nathan Ernst proporciona una solución, pero implica una llamada a la función, una declaración de variable y un condicional, lo que lo hace no más corto que el código OP y probablemente aún más lento, porque es más difícil de optimizar.

Mi solución es esta:

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

Será un poco más rápido que el código OP, porque el módulo y la división se realizan utilizando la misma instrucción en el procesador, porque el compilador puede ver que son equivalentes. Al menos gcc 4.4.1 realiza esta optimización con el indicador -O2 en x86.

En teoría, el compilador podría incluir la llamada de función en el código de Nathan Ernst y emitir lo mismo, pero gcc no hizo eso cuando lo probé. Esto podría deberse a que vincularía el código compilado a una única versión de la biblioteca estándar.

Como nota final, nada de esto importa en una máquina moderna, excepto si está en un circuito extremadamente cerrado y todos sus datos están en registros o en el caché L1. De lo contrario, todas estas soluciones serán igualmente rápidas, excepto posiblemente la de Nathan Ernst, que podría ser significativamente más lenta si la función tiene que ser obtenida de la memoria principal.

Puede usar la divfunción en cstdlib para obtener el cociente y el resto en una sola llamada y luego manejar el techo por separado, como en el siguiente

#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;
}

¿Qué tal esto? (requiere y no negativo, así que no use esto en el raro caso de que y sea una variable sin garantía de no negatividad)

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

Reduje y/ya uno, eliminando el término x + y - 1y con él cualquier posibilidad de desbordamiento.

Evito x - 1envolviendo alrededor cuando xes un tipo sin signo y contiene cero.

Para firmado x, negativo y cero aún se combinan en un solo caso.

Probablemente no sea un gran beneficio en una CPU moderna de uso general, pero esto sería mucho más rápido en un sistema integrado que cualquiera de las otras respuestas correctas.

Hay una solución tanto para positivo como negativo, xpero solo para positivo ycon solo 1 división y sin ramas:

int ceil(int x, int y) {
    return x / y + (x % y > 0);
}

Tenga en cuenta que si xes positivo, entonces la división es hacia cero, y debemos agregar 1 si el recordatorio no es cero.

Si xes negativo, entonces la división es hacia cero, eso es lo que necesitamos, y no agregaremos nada porque x % yno es positivo

Esto funciona para números positivos o negativos:

q = x / y + ((x % y != 0) ? !((x > 0) ^ (y > 0)) : 0);

Si hay un resto, comprueba si xy yson del mismo signo, y añade 1en consecuencia.

Hubiera preferido comentar pero no tengo un representante lo suficientemente alto.

Hasta donde yo sé, para argumentos positivos y un divisor que es una potencia de 2, esta es la forma más rápida (probado en CUDA):

//example y=8
q = (x >> 3) + !!(x & 7);

Solo para argumentos positivos genéricos, tiendo a hacerlo así:

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

forma genérica simplificada,

int div_up(int n, int d) {
    return n / d + (((n < 0) ^ (d > 0)) && (n % d));
} //i.e. +1 iff (not exact int && positive result)

Para una respuesta más genérica, C ++ funciona para la división de enteros con una estrategia de redondeo bien definida

Compilar con O3, el compilador realiza bien la optimización.

q = x / y;
if (x % y)  ++q;