entera - residuo de una division en c++

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

Question

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

El enfoque obvio involucra 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 (usados ​​de hecho) involucran el lanzamiento como float o double . ¿Existe un método más directo que evite la multiplicación adicional (o una segunda división) y la rama, y ​​que también evite la conversión como un número de punto flotante?

Answer 1

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

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

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

Evito el ajuste de x - 1 cuando x es un tipo sin signo y contiene cero.

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

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

Answer 2

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 xey son del mismo signo y agrega 1 en consecuencia.

Answer 3

Hay una solución para x positiva y negativa pero solo para y positiva con solo 1 división y sin ramas:

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

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

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

Answer 4

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é sucede si se quiere dividir los long long ?

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

Mi solución es la siguiente:

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 las mismas instrucciones 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 alinear la función llamada 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 se encuentra en un bucle extremadamente cerrado y todos sus datos están en registros o en la memoria caché L1. De lo contrario, todas estas soluciones serán igual de rápidas, excepto posiblemente las de Nathan Ernst, que podrían ser significativamente más lentas si la función tiene que recuperarse de la memoria principal.

Answer 5

Para números positivos:

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

Answer 6

Para resumir ...

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

o (evitando el desbordamiento en x + y)

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

Answer 7

Podría usar la función div 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;
}

Answer 8

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 entera con una estrategia de redondeo bien definida