¿Cómo puedo asegurar que una división de enteros siempre se redondea hacia arriba?
Quiero asegurarme de que una división de enteros siempre se redondee hacia arriba si es necesario. ¿Hay algo mejor que esto? Hay un montón de casting pasando. :-)
(int)Math.Ceiling((double)myInt1 / myInt2)
7 answers
ACTUALIZACIÓN: Esta pregunta fue el tema de mi blog en enero de 2013. Gracias por la gran pregunta!
Obtener aritmética de enteros correcta es difícil. Como se ha demostrado ampliamente hasta ahora, en el momento en que intenta hacer un truco "inteligente", las probabilidades son buenas de que haya cometido un error. Y cuando se encuentra una falla, cambiar el código para corregir la falla sin considerar si la solución rompe algo más no es una buena técnica para resolver problemas. Hasta ahora hemos tenido creo cinco diferentes soluciones aritméticas de enteros incorrectos a este problema completamente no-particularmente-difícil publicado.
La forma correcta de abordar los problemas aritméticos enteros, es decir, la forma en que aumenta la probabilidad de obtener la respuesta correcta la primera vez, es abordar el problema con cuidado, resolverlo paso a paso y usar buenos principios de ingeniería para hacerlo.
Comience leyendo la especificación de lo que está tratando de reemplazar. El la especificación para la división entera establece claramente:
-
La división redondea el resultado hacia cero
El resultado es cero o positivo, cuando los dos operandos tienen el mismo signo, y cero o negativo cuando los dos operandos tienen signos opuestos
Si el operando izquierdo es el int representable más pequeño y el operando derecho es -1, se produce un desbordamiento. [...] se define la implementación en cuanto a si se lanza [una excepción ArithmeticException] o el desbordamiento no se reporta con el valor resultante siendo el del operando izquierdo.
Si el valor del operando derecho es cero, un Sistema.Se lanza DivideByZeroException.
Lo que queremos es una función de división de enteros que calcula el cociente pero redondea el resultado siempre hacia arriba, no siempre hacia cero.
Así que escribe una especificación para esa función. Nuestra función int DivRoundUp(int dividend, int divisor) debe tener un comportamiento definido para cada posible entrada. Ese comportamiento indefinido es profundamente preocupante, así que eliminémoslo. Diremos que nuestra operación tiene esta especificación:
-
La operación lanza si el divisor es cero
-
Operación lanza si dividendo es int.minval y divisor es -1
-
Si no hay resto division la división es ' par ' then entonces el valor devuelto es el cociente integral
De lo Contrario, devuelve el más pequeño entero que es más que el cociente, es decir, siempre se redondea.
Ahora tenemos una especificación, así que sabemos que podemos llegar a un diseño comprobable. Supongamos que agregamos un criterio de diseño adicional para que el problema se resuelva únicamente con aritmética de enteros, en lugar de calcular el cociente como un doble, ya que la solución "doble" ha sido rechazada explícitamente en la declaración del problema.
Entonces, ¿qué debemos calcular? Claramente, para cumplir con nuestras especificaciones mientras permanece únicamente en entero aritmética, necesitamos saber tres hechos. Primero, ¿cuál fue el cociente entero? Segundo, ¿la división estaba libre de remanente? Y tercero, si no, ¿el cociente entero se calculó redondeando hacia arriba o hacia abajo?
Ahora que tenemos una especificación y un diseño, podemos empezar a escribir código.
public static int DivRoundUp(int dividend, int divisor)
{
if (divisor == 0 ) throw ...
if (divisor == -1 && dividend == Int32.MinValue) throw ...
int roundedTowardsZeroQuotient = dividend / divisor;
bool dividedEvenly = (dividend % divisor) == 0;
if (dividedEvenly)
return roundedTowardsZeroQuotient;
// At this point we know that divisor was not zero
// (because we would have thrown) and we know that
// dividend was not zero (because there would have been no remainder)
// Therefore both are non-zero. Either they are of the same sign,
// or opposite signs. If they're of opposite sign then we rounded
// UP towards zero so we're done. If they're of the same sign then
// we rounded DOWN towards zero, so we need to add one.
bool wasRoundedDown = ((divisor > 0) == (dividend > 0));
if (wasRoundedDown)
return roundedTowardsZeroQuotient + 1;
else
return roundedTowardsZeroQuotient;
}
¿Es esto inteligente? No. ¿Hermosa? No. Corto? No. ¿Correcto según la especificación? Lo creo, pero no lo he probado completamente. Sin embargo, se ve bastante bien.
Estamos profesionales aquí; utilizar buenas prácticas de ingeniería. Investigue sus herramientas, especifique el comportamiento deseado, considere primero los casos de error y escriba el código para enfatizar su corrección obvia. Y cuando encuentre un error, considere si su algoritmo es profundamente defectuoso para empezar antes de comenzar a intercambiar aleatoriamente las direcciones de las comparaciones y romper cosas que ya funcionan.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-01-28 19:29:50
La respuesta final basada en int
Para enteros con signo:
int div = a / b;
if (((a ^ b) >= 0) && (a % b != 0))
div++;
Para enteros sin signo:
int div = a / b;
if (a % b != 0)
div++;
El razonamiento para esta respuesta
La división entera '/' se define para redondear hacia cero (7.7.2 de la especificación), pero queremos redondear hacia arriba. Esto significa que las respuestas negativas ya se redondean correctamente, pero las respuestas positivas deben ajustarse.
Las respuestas positivas distintas de cero son fáciles de detectar, pero la respuesta cero es un poco más complicada, ya que puede sea el redondeo hacia arriba de un valor negativo o el redondeo hacia abajo de un valor positivo.
La apuesta más segura es detectar cuándo la respuesta debe ser positiva comprobando que los signos de ambos enteros son idénticos. El operador xor entero ' ^' en los dos valores dará como resultado un bit de signo 0 cuando este sea el caso, lo que significa un resultado no negativo, por lo que la verificación (a ^ b) >= 0 determina que el resultado debería haber sido positivo antes del redondeo. También tenga en cuenta que para enteros sin signo, cada respuesta es obviamente positivo, por lo que esta comprobación se puede omitir.
La única comprobación que queda es entonces si se ha producido algún redondeo, para lo cual a % b != 0 hará el trabajo.
Lecciones aprendidas
La aritmética (entera o no) no es tan simple como parece. Pensar cuidadosamente requiere en todo momento.
También, aunque mi respuesta final quizás no sea tan 'simple' o 'obvia' o quizás incluso 'rápida' como las respuestas de punto flotante, tiene una cualidad redentora muy fuerte para mí; ahora he razonado a través de la respuesta, así que estoy realmente seguro de que es correcta (hasta que alguien más inteligente me diga lo contrario -mirada furtiva en la dirección de Eric-).
Para tener la misma sensación de certeza sobre la respuesta de punto flotante, tendría que hacer más (y posiblemente más complicado) pensando si hay alguna condición bajo la cual la precisión de punto flotante podría interponerse, y si Math.Ceiling tal vez hace algo indeseable en 'justo lo correcto' entrada.
El camino recorrido
Reemplazar (nota I reemplazó el segundo myInt1 con myInt2, suponiendo que eso era lo que quería decir):
(int)Math.Ceiling((double)myInt1 / myInt2)
Con:
(myInt1 - 1 + myInt2) / myInt2
La única advertencia es que si myInt1 - 1 + myInt2 se desborda el tipo entero que está utilizando, es posible que no obtenga lo que espera.
Razón por la que esto está mal: -1000000 y 3999 deberían dar -250, esto da -249
EDITAR:
Teniendo en cuenta que esto tiene el mismo error que el otro entero solución para valores myInt1 negativos, podría ser más fácil hacer algo como:
int rem;
int div = Math.DivRem(myInt1, myInt2, out rem);
if (rem > 0)
div++;
Eso debería dar el resultado correcto en div usando solo operaciones enteras.
Razón por la que esto está mal: -1 y -5 deberían dar 1, esto da 0
EDITAR (una vez más, con sentimiento):
El operador de división redondea hacia cero; para resultados negativos esto es exactamente correcto, por lo que solo los resultados no negativos necesitan ajuste. También teniendo en cuenta que DivRem solo hace un / y a % de todos modos, saltemos la llamada (y comencemos con la comparación fácil para evitar el cálculo del módulo cuando no es necesario):
int div = myInt1 / myInt2;
if ((div >= 0) && (myInt1 % myInt2 != 0))
div++;
Razón por la que esto está mal: -1 y 5 deberían dar 0, esto da 1
(En mi propia defensa del último intento nunca debería haber intentado una respuesta razonada mientras mi mente me decía que llegué 2 horas tarde para dormir)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-05-30 00:15:24
Todas las respuestas aquí hasta ahora parecen bastante complicadas.
En C# y Java, para dividendo positivo y divisor, simplemente debe hacer:
( dividend + divisor - 1 ) / divisor
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-12-09 15:43:03
Oportunidad perfecta para usar un método de extensión:
public static class Int32Methods
{
public static int DivideByAndRoundUp(this int number, int divideBy)
{
return (int)Math.Ceiling((float)number / (float)divideBy);
}
}
Esto hace que su código uber legible también:
int result = myInt.DivideByAndRoundUp(4);
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-12-01 11:02:31
Podrías escribir un ayudante.
static int DivideRoundUp(int p1, int p2) {
return (int)Math.Ceiling((double)p1 / p2);
}
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-05-28 14:40:33
Podrías usar algo como lo siguiente.
a / b + ((Math.Sign(a) * Math.Sign(b) > 0) && (a % b != 0)) ? 1 : 0)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2009-05-30 11:17:58
El problema con todas las soluciones aquí es que necesitan un molde o tienen un problema numérico. Lanzar a flotador o doble es siempre una opción, pero podemos hacerlo mejor.
Cuando se utiliza el código de la respuesta de @jerryjvl
int div = myInt1 / myInt2;
if ((div >= 0) && (myInt1 % myInt2 != 0))
div++;
Hay un error de redondeo. 1 / 5 se redondearía, porque 1% 5 != 0. Pero esto está mal, porque el redondeo solo ocurrirá si reemplaza el 1 con un 3, por lo que el resultado es 0.6. Tenemos que encontrar una manera de redondear cuando el cálculo dar us un valor mayor o igual a 0.5. El resultado del operador modulo en el ejemplo superior tiene un rango de 0 a myInt2-1. El redondeo solo se producirá si el resto es mayor que el 50% del divisor. Así que el código ajustado se ve así:
int div = myInt1 / myInt2;
if (myInt1 % myInt2 >= myInt2 / 2)
div++;
Por supuesto que tenemos un problema de redondeo en myInt2 / 2 también, pero este resultado le dará una mejor solución de redondeo que los otros en este sitio.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-06-20 15:47:20