¿Cómo puedo asegurar que una división de números enteros siempre se redondee hacia arriba?

ACTUALIZACIÓN: Esta pregunta fue el tema de mi blog en enero de 2013 . ¡Gracias por la gran pregunta!

Obtener la aritmética de números enteros correcta es difícil. Como se ha demostrado ampliamente hasta ahora, en el momento en que intentas hacer un truco "inteligente", es muy probable que hayas 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 de resolución de problemas. Hasta ahora, creo que hemos publicado cinco soluciones aritméticas enteras incorrectas diferentes para este problema que no es particularmente difícil.

La forma correcta de abordar los problemas de aritmética de números enteros (es decir, la forma que aumenta la probabilidad de obtener la respuesta correcta la primera vez) es abordar el problema con cuidado, resolverlo paso a paso y utilizar buenos principios de ingeniería al resolverlos. entonces.

Comience leyendo las especificaciones de lo que está intentando reemplazar. La especificación para la división de números enteros establece claramente:

1. La división redondea el resultado hacia cero.

2. 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

3. Si el operando izquierdo es el int más pequeño representable y el operando derecho es –1, se produce un desbordamiento. [...] está definido por la implementación en cuanto a si se lanza [una ArithmeticException] o si el desbordamiento no se informa y el valor resultante es el del operando izquierdo.

4. Si el valor del operando derecho es cero, se genera una System.DivideByZeroException.

Lo que queremos es una función de división de enteros que calcule el cociente pero redondee el resultado siempre hacia arriba , no siempre hacia cero .

Entonces escriba una especificación para esa función. Nuestra función int DivRoundUp(int dividend, int divisor)debe tener un comportamiento definido para cada entrada posible. Ese comportamiento indefinido es profundamente preocupante, así que eliminémoslo. Diremos que nuestra operación tiene esta especificación:

1. la operación arroja si el divisor es cero

2. la operación arroja si el dividendo es int.minval y el divisor es -1

3. si no hay resto (la división es "par"), entonces el valor de retorno es el cociente integral

4. En caso contrario devuelve el menor entero que sea mayor que el cociente, es decir, siempre redondea hacia arriba.

Ahora tenemos una especificación, por lo que sabemos que podemos crear un diseño comprobable . Supongamos que agregamos un criterio de diseño adicional de 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 el planteamiento del problema.

Entonces, ¿qué debemos calcular? Claramente, para cumplir con nuestras especificaciones y permanecer únicamente en la aritmética de enteros, necesitamos conocer tres hechos. Primero, ¿cuál fue el cociente entero? En segundo lugar, ¿estaba la división libre de restos? Y en tercer lugar, si no, ¿se calculó el cociente entero 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 las especificaciones? Creo que sí, pero no lo he probado completamente. Aunque luce bastante bien.

Somos 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 evidente corrección. Y cuando encuentre un error, considere si su algoritmo tiene fallas profundas antes de comenzar a intercambiar aleatoriamente las direcciones de las comparaciones y romper cosas que ya funcionan.

May 29 '2009 16:05 Eric Lippert