Redondear la división de enteros (en lugar de truncar)

Tenía curiosidad por saber cómo puedo redondear un número al décimo número entero más cercano. Por ejemplo, si tuviera:

int a = 59 / 4; 

que sería 14.75 calculado en coma flotante; ¿cómo puedo almacenar el número como 15 en “a”?

 int a = 59.0f / 4.0f + 0.5f; 

Esto solo funciona cuando se asigna a un int ya que descarta cualquier cosa después del ‘.’

Editar: Esta solución solo funcionará en los casos más simples. Una solución más robusta sería:

 unsigned int round_closest(unsigned int dividend, unsigned int divisor) { return (dividend + (divisor / 2)) / divisor; } 

La expresión estándar para el redondeo de números enteros es:

 int a = (59 + (4 - 1)) / 4; 

Agregue el divisor menos uno al dividendo.

Un código que funciona para cualquier signo en dividendo y divisor:

 int divRoundClosest(const int n, const int d) { return ((n < 0) ^ (d < 0)) ? ((n - d/2)/d) : ((n + d/2)/d); } 

Si prefieres una macro:

 #define DIV_ROUND_CLOSEST(n, d) ((((n) < 0) ^ ((d) < 0)) ? (((n) - (d)/2)/(d)) : (((n) + (d)/2)/(d))) 

¡La macro del núcleo de Linux DIV_ROUND_CLOSEST no funciona para los divisores negativos!

En su lugar, debería usar algo como esto:

 int a = (59 - 1)/ 4 + 1; 

Supongo que realmente está tratando de hacer algo más general:

 int divide(x, y) { int a = (x -1)/y +1; return a; } 

x + (y-1) tiene el potencial de desbordarse dando el resultado incorrecto; mientras que, x – 1 solo subfluirá si x = min_int …

(Editado) Redondear enteros con coma flotante es la solución más fácil para este problema; sin embargo, dependiendo del problema establecido, puede ser posible. Por ejemplo, en sistemas integrados la solución de coma flotante puede ser muy costosa.

Hacer esto usando matemáticas enteras resulta ser un poco difícil y poco intuitivo. La primera solución publicada funcionó bien para el problema que yo había usado, pero después de caracterizar los resultados en el rango de los enteros resultó ser muy malo en general. Mirando a través de varios libros en poco movimiento y matemáticas incrustadas devuelven pocos resultados. Un par de notas. Primero, solo probé enteros positivos, mi trabajo no involucra numeradores o denominadores negativos. En segundo lugar, y la prueba exhaustiva de los enteros de 32 bits es computacionalmente prohibitiva, así que comencé con enteros de 8 bits y luego me aseguro de obtener resultados similares con los enteros de 16 bits.

Empecé con las 2 soluciones que había propuesto anteriormente:

#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)

#define DIVIDE_WITH_ROUND(N, D) (N == 0) ? 0:(N - D/2)/D + 1;

Mi pensamiento fue que la primera versión se desbordó con números grandes y la segunda con números pequeños. No tomé 2 cosas en consideración. 1.) el segundo problema es recursivo ya que para obtener la respuesta correcta tienes que redondear correctamente D / 2. 2.) En el primer caso, a menudo se desborda y luego se desborda, y los dos se anulan mutuamente. Aquí hay un diagtwig de error de los dos algoritmos (incorrectos): Divide con Round1 8 bit x = numerador y = denominador

Este gráfico muestra que el primer algoritmo solo es incorrecto para los denominadores pequeños (0 los numeradores grandes mejor que la segunda versión.

Aquí hay una gráfica del segundo algoritmo: Números con signo de 8 bits 2º algoritmo.

Como se esperaba, falla para los numeradores pequeños, pero también falla para los numeradores más grandes que la primera versión.

Claramente este es el mejor punto de partida para una versión correcta:

#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)

Si tus denominadores son> 10 entonces esto funcionará correctamente.

Se necesita un caso especial para D == 1, simplemente devuelve N. Se necesita un caso especial para D == 2, = N / 2 + (N y 1) // Redondear si es impar.

D> = 3 también tiene problemas una vez que N crece lo suficiente. Resulta que los denominadores más grandes solo tienen problemas con los numeradores más grandes. Para el número firmado de 8 bits, los puntos problemáticos son

if (D == 3) && (N > 75))
else if ((D == 4) && (N > 100))
else if ((D == 5) && (N > 125))
else if ((D == 6) && (N > 150))
else if ((D == 7) && (N > 175))
else if ((D == 8) && (N > 200))
else if ((D == 9) && (N > 225))
else if ((D == 10) && (N > 250))

(devuelva D / N para estos)

Entonces, en general, la punta donde un numerador particular se pone malo está en algún lugar alrededor
N > (MAX_INT - 5) * D/10

Esto no es exacto, pero está cerca. Cuando trabaje con números de 16 o más bits, el error <1% si hace una división en C (truncamiento) para estos casos.

Para números de 16 bits con signo, las pruebas serían

if ((D == 3) && (N >= 9829))
else if ((D == 4) && (N >= 13106))
else if ((D == 5) && (N >= 16382))
else if ((D == 6) && (N >= 19658))
else if ((D == 7) && (N >= 22935))
else if ((D == 8) && (N >= 26211))
else if ((D == 9) && (N >= 29487))
else if ((D == 10) && (N >= 32763))

Por supuesto, para enteros sin signo, MAX_INT se reemplazaría por MAX_UINT. Estoy seguro de que hay una fórmula exacta para determinar la N más grande que funcionará para una D en particular y una cantidad de bits, pero no tengo más tiempo para trabajar en este problema …

(Parece que me falta este gráfico en este momento, lo editaré y lo agregaré más adelante). Este es un gráfico de la versión de 8 bits con los casos especiales mencionados anteriormente:! [8 bits firmados con casos especiales para 0 < N <= 10 3

Tenga en cuenta que para 8 bits, el error es 10% o menos para todos los errores en el gráfico, 16 bits es <0.1%.

Tal como está escrito, está realizando una aritmética de enteros, que automáticamente trunca cualquier resultado decimal. Para realizar la aritmética de coma flotante, cambie las constantes para que sean valores de coma flotante:

 int a = round(59.0 / 4); 

O inclúyalos a un float u otro tipo de punto flotante:

 int a = round((float)59 / 4); 

De cualquier forma, debe hacer el redondeo final con la función round() en el encabezado math.h , así que asegúrese de #include

y usar un comstackdor compatible con C99.

 int a, b; int c = a / b; if(a % b) { c++; } 

Verificar si hay un rest le permite redondear manualmente el cociente de la división entera.

 #define CEIL(a, b) (((a) / (b)) + (((a) % (b)) > 0 ? 1 : 0)) 

Otro MACROS útil (DEBE TENER):

 #define MIN(a, b) (((a) < (b)) ? (a) : (b)) #define MAX(a, b) (((a) > (b)) ? (a) : (b)) #define ABS(a) (((a) < 0) ? -(a) : (a)) 

Desde el kernel de Linux (GPLv2):

 /* * Divide positive or negative dividend by positive divisor and round * to closest integer. Result is undefined for negative divisors and * for negative dividends if the divisor variable type is unsigned. */ #define DIV_ROUND_CLOSEST(x, divisor)( \ { \ typeof(x) __x = x; \ typeof(divisor) __d = divisor; \ (((typeof(x))-1) > 0 || \ ((typeof(divisor))-1) > 0 || (__x) > 0) ? \ (((__x) + ((__d) / 2)) / (__d)) : \ (((__x) - ((__d) / 2)) / (__d)); \ } \ ) 

Aquí está mi solución. Me gusta porque me resulta más legible y porque no tiene ramificaciones (ni ifs ni ternaries).

 int32_t divide(int32_t a, int32_t b) { int32_t resultIsNegative = ((a ^ b) & 0x80000000) >> 31; int32_t sign = resultIsNegative*-2+1; return (a + (b / 2 * sign)) / b; } 

Progtwig de prueba completo que ilustra el comportamiento previsto:

 #include  #include  int32_t divide(int32_t a, int32_t b) { int32_t resultIsNegative = ((a ^ b) & 0x80000000) >> 31; int32_t sign = resultIsNegative*-2+1; return (a + (b / 2 * sign)) / b; } int main() { assert(divide(0, 3) == 0); assert(divide(1, 3) == 0); assert(divide(5, 3) == 2); assert(divide(-1, 3) == 0); assert(divide(-5, 3) == -2); assert(divide(1, -3) == 0); assert(divide(5, -3) == -2); assert(divide(-1, -3) == 0); assert(divide(-5, -3) == 2); } 

El préstamo de @ericbn I prefere define como

 #define DIV_ROUND_INT(n,d) ((((n) < 0) ^ ((d) < 0)) ? (((n) - (d)/2)/(d)) : (((n) + (d)/2)/(d))) or if you work only with unsigned ints #define DIV_ROUND_UINT(n,d) ((((n) + (d)/2)/(d))) 
 int divide(x,y){ int quotient = x/y; int remainder = x%y; if(remainder==0) return quotient; int tempY = divide(y,2); if(remainder>=tempY) quotient++; return quotient; } 

por ejemplo, 59/4 cociente = 14, tempY = 2, rest = 3, rest> = tempY, por lo tanto, cociente = 15;

 double a=59.0/4; int b=59/4; if(ab>=0.5){ b++; } printf("%d",b); 
  1. deje que el valor exacto de flotación de 59.0 / 4 sea x (aquí es 14.750000)
  2. deja el entero más pequeño menos que x be y (aquí es 14)
  3. si xy <0.5 entonces y es la solución
  4. else y + 1 es la solución

intente usar la función de ceil matemático que redondea. Math Ceil !

Si divide números enteros positivos, puede cambiarlos, hacer la división y luego verificar el bit a la derecha del real b0. En otras palabras, 100/8 es 12.5 pero devolvería 12. Si lo hace (100 < < 1) / 8, puede verificar b0 y luego redondear después de cambiar el resultado hacia abajo.

Para algunos algoritmos, necesita un sesgo constante cuando ‘más cercano’ es un empate.

 // round-to-nearest with mid-value bias towards positive infinity int div_nearest( int n, int d ) { if (d<0) n*=-1, d*=-1; return (abs(n)+((d-(n<0?1:0))>>1))/d * ((n<0)?-1:+1); } 

Esto funciona independientemente del signo del numerador o denominador.


Si desea hacer coincidir los resultados de la round(N/(double)D) (división de coma flotante y redondeo), aquí hay algunas variaciones que producen todos los mismos resultados:

 int div_nearest( int n, int d ) { int r=(n<0?-1:+1)*(abs(d)>>1); // eliminates a division // int r=((n<0)^(d<0)?-1:+1)*(d/2); // basically the same as @ericbn // int r=(n*d<0?-1:+1)*(d/2); // small variation from @ericbn return (n+r)/d; } 

Nota: La velocidad relativa de (abs(d)>>1) vs. (d/2) es probable que dependa de la plataforma.

Me encontré con la misma dificultad. El siguiente código debería funcionar para enteros positivos.

Aún no lo compilé, pero probé el algoritmo en una hoja de cálculo de google (lo sé, wtf) y estaba funcionando.

 unsigned int integer_div_round_nearest(unsigned int numerator, unsigned int denominator) { unsigned int rem; unsigned int floor; unsigned int denom_div_2; // check error cases if(denominator == 0) return 0; if(denominator == 1) return numerator; // Compute integer division and remainder floor = numerator/denominator; rem = numerator%denominator; // Get the rounded value of the denominator divided by two denom_div_2 = denominator/2; if(denominator%2) denom_div_2++; // If the remainder is bigger than half of the denominator, adjust value if(rem >= denom_div_2) return floor+1; else return floor; } 

Código C más seguro (a menos que tenga otros métodos de manejo / 0):

return (_divisor > 0) ? ((_dividend + (_divisor - 1)) / _divisor) : _dividend;

Esto no soluciona los problemas que ocurren al tener un valor de retorno incorrecto como resultado de sus datos de entrada no válidos, por supuesto.