porcentajes - ¿Cuál es la manera correcta de encontrar el promedio de dos valores?
como sacar promedio de notas escolares (8)
Hace poco aprendí que el desbordamiento de enteros es un comportamiento indefinido en C (pregunta paralela: ¿es también UB en C ++?)
A menudo, en la programación en C es necesario encontrar el promedio de dos valores a y b . Sin embargo, hacer (a+b)/2 puede provocar un desbordamiento y un comportamiento indefinido.
Entonces, mi pregunta es: ¿cuál es la forma correcta de encontrar el promedio de dos valores a y b en C?
Con la ayuda de Secure Coding
if (((si_b > 0) && (si_a > (INT_MAX - si_b))) ||
((si_b < 0) && (si_a < (INT_MIN - si_b))))
{
/* will overflow, so use difference method */
return si_b + (si_a - si_b) / 2;
}
else
{
/* the addition will not overflow */
return (si_a + si_b) / 2;
}
APÉNDICE
Gracias a @chux por señalar el problema del redondeo. Aquí hay una versión que está probada para el redondeo correcto ...
int avgnoov (int si_a, int si_b)
{
if ((si_b > 0) && (si_a > (INT_MAX - si_b)))
{
/* will overflow, so use difference method */
/* both si_a and si_b > 0;
we want difference also > 0
so rounding works correctly */
if (si_a >= si_b)
return si_b + (si_a - si_b) / 2;
else
return si_a + (si_b - si_a) / 2;
}
else if ((si_b < 0) && (si_a < (INT_MIN - si_b)))
{
/* will overflow, so use difference method */
/* both si_a and si_b < 0;
we want difference also < 0
so rounding works correctly */
if (si_a <= si_b)
return si_b + (si_a - si_b) / 2;
else
return si_a + (si_b - si_a) / 2;
}
else
{
/* the addition will not overflow */
return (si_a + si_b) / 2;
}
}
Esto es a partir del cálculo del promedio de dos números enteros redondeados hacia cero en un solo ciclo de instrucción :
(a >> 1) + (b >> 1) + (a & b & 0x1)
Debes tener en cuenta que:
su implementación está definida si el desplazamiento a la derecha de un entero negativo desplaza ceros o unos a los bits de orden superior. Muchas CPU tienen a menudo dos instrucciones diferentes: un desplazamiento aritmético a la derecha (conserva el bit de signo) y un cambio lógico a la derecha (no conserva el bit de signo). El compilador puede elegir cualquiera de los dos (la mayoría de los compiladores eligen una instrucción de cambio aritmético).
ISO / IEC 9899: 2011 §6.5.7 Operadores de cambio bitwise
¶5 El resultado de E1 >> E2 es E1 posiciones de bit E2 desplazadas a la derecha. [CUT] Si E1 tiene un tipo firmado y un valor negativo, el valor resultante está definido por la implementación.
Cambiando la expresión a:
a / 2 + b / 2 + (a & b & 0x1)no es una solución ya que los desplazamientos lógicos hacia la derecha son equivalentes a la división por una potencia de 2 solo para números positivos o sin signo .
también
(a & b & 0x1)no está bien definido. Este término debe ser distinto de cero cuandoaybson impares. Pero falla con la representación del complemento de uno y la sección 6.2.6.2/2 de ISO C, establece que una implementación puede elegir una de las tres representaciones diferentes para los tipos de datos integrales :- complemento de dos
- complemento de uno
- signo / magnitud
(Por lo general, el complemento de los dos es mucho mayor que los otros).
La forma más simple (y generalmente más rápida) de promediar dos int en todo el rango [INT_MIN...INT_MAX] es recurrir a un tipo entero más amplio. (Sugerido por @user3100381 ). Llamemos a eso int2x .
int average_int(int a, int b) {
return ((int2x) a + b)/2;
}
Por supuesto, esto obliga a que exista un tipo más amplio, así que veamos una solución que no requiera un tipo más amplio.
Desafíos:
P: Cuando un int es impar y el otro es par, ¿de qué manera debería ocurrir el redondeo?
A: Siga a average_int() arriba y redondee hacia 0. (truncar).
P: ¿Puede el código usar % ?
R: Con el código pre-C99, el resultado de a % 2 permite diferentes resultados cuando a < 0 . Así que no utilicemos % .
P: ¿Es necesario que int tenga un rango simétrico de números positivos y negativos?
R: Desde C99, el número de números negativos es el mismo (o 1 más) que el número de números positivos. Tratemos de no requerir esto.
SOLUCIÓN:
Realizar pruebas para determinar si puede ocurrir un desbordamiento. Si no, uso simple (a + b) / 2 . De lo contrario, agregue la mitad de la diferencia (firmada igual que la respuesta) al valor más pequeño.
Lo siguiente da la misma respuesta que average_int() sin tener que recurrir a un tipo entero más amplio. Protege contra el desbordamiento de int y no requiere que INT_MIN + INT_MAX sea 0 o -1. No depende de la codificación para ser el complemento de 2, el complemento de 1 o la magnitud de signo.
int avgC2(int a, int b) {
if (a >= 0) {
if (b > (INT_MAX - a)) {
// (a+b) > INT_MAX
if (a >= b) {
return (a - b) / 2 + b;
} else {
return (b - a) / 2 + a;
}
}
} else {
if (b < (INT_MIN - a)) {
// (a+b) < INT_MIN
if (a <= b) {
return (a - b) / 2 + b;
} else {
return (b - a) / 2 + a;
}
}
}
return (a + b) / 2;
}
Como máximo, 3 if() s ocurren con cualquier par de int .
La respuesta más simple si solo hay 2 elementos para evitar el desbordamiento sería:
(a/2) + (b/2) = average
Para más elementos, podrías usar:
(a/x) + (b/x) + (c/x) + (d/x) ..... = average //x = amount of elements
Desde un punto de vista matemático , esto nunca alcanzará un desbordamiento si ninguno de los valores originales lo ha hecho anteriormente, ya que realmente no los suma todos, sino que los divide antes de sumarlos. Por lo tanto, ningún resultado de ninguna operación realizada durante el cálculo, incluido el resultado, será más grande (a cada lado de 0) que el elemento inicial más grande (suponiendo que solo trabaje con Real Numbers ).
Así que haz lo siguiente:
- Determine la cantidad de elementos en ''C'', llamémoslo
total. - Declare un valor para almacenar el promedio, llamémoslo
average. - Declare un valor para almacenar los residuos, llamémoslo
remainder. - Iterar a través de ellos y:
- Divide el elemento actual por la cantidad
total,total. - Suma el resultado al promedio, al
average. - Suma el resto de los valores divididos juntos, el
remainder.
- Divide el elemento actual por la cantidad
- Divida los residuos también y agréguelos a la media, a la
average. - Haga con el promedio lo que necesita / tiene la intención de hacer.
Esto le dará una respuesta desactivada por un máximo de 1 (sistema numérico decimal [base 10]). Todavía no conozco C ++, así que solo puedo darte un ejemplo en C #.
Pseudo código en C # (solo para dar una idea):
int[] C = new int[20]; //The array of elements.
int total = C.Length; //The total amount of elements.
int average = 0; //The variable to contain the result.
int remainder = 0; //The variable to contain all the smaller bits.
foreach (int element in C) //Iteration
{
int temp = (element / total); //Divide the current element by the total.
average = average + temp; //Add the result to the average.
temp = (temp % total); //Get the remainder (number that was not divided)
remainder = remainder + temp; //Add remainder to the other remainders.
}
average = average + (remainder / total); // Adds the divided remainders to the average.
Ejemplo de C # comprimido:
int[] C = new int[20]; //The array of elements.
int total = C.Length; //The total amount of elements.
int average = 0; //The variable to contain the result.
int remainder = 0; //The variable to contain all the smaller bits.
foreach (int element in C) //Iteration
{
average += (element / total); //Add the current element divided by the total to the average.
remainder += ( element % total); //Add the remainders together.
}
average += (remainder / total); //Adds the divided remainders to the total.
Si le preocupa el desbordamiento, puede convertir los valores en un tipo más grande para realizar los cálculos y luego realizar la comprobación de límites.
Si solo tiene que tratar con tipos de enteros sin signo (y puede pensar en binario), puede descomponer su suma en digit y carry . Podemos escribir a+b (con una precisión ilimitada) como (a^b) + ((a&b)<<1)) , por lo que (a+b)/2 es simplemente ((a^b)>>1) + (a&b) . Esta última expresión se ajusta al tipo común de a y b , por lo que puede usarla en su código:
unsigned semisum(unsigned a, unsigned b)
{
return ((a^b)>>1) + (a&b);
}
Un enfoque simple es el siguiente
int c = a / 2 + ( b + a % 2 ) / 2;
Por ejemplo, a y b se pueden representar como
a = 2 * n + r1;
b = 2 * m + r2;
Entonces
( a + b ) / 2 => ( 2 * n + r1 + 2 * m + r2 ) / 2 => 2 * n / 2 + ( b + r1 ) / 2
Y la última expresión te da.
=> a / 2 + ( b + a % 2 ) / 2
La expresión más correcta es la siguiente
int c = a / 2 + b / 2 + ( a % 2 + b % 2 ) / 2;
Por ejemplo si tenemos
int a = INT_MAX;
int b = INT_MAX;
entonces c calculada como
int c = a / 2 + b / 2 + ( a % 2 + b % 2 ) / 2;
dará c == INT_MAX
EDIT: se encontró una diferencia interesante entre el efecto de los operadores informáticos y el efecto de los operadores matemáticos. Por ejemplo, de acuerdo con las matemáticas -1 se puede representar como
-1 = -1 * 2 + 1
eso es de acuerdo a la formula
a = 2 * n + r1
2 * n será un número entero menor o igual que tp a
Entonces el número que es menos -1 es -2. :)
Pienso que la fórmula general mostrada por mí funcionaría, se requiere que para los números impares negativos se consideren incluso números negativos menos que el número impar negativo.
Parece que la fórmula correcta se ve como
int c = ( a < 0 ? a & ~1 : a ) / 2 +
( b < 0 ? b & ~1 : b ) / 2 +
( ( a & 1 ) + ( b & 1 ) ) / 2;
Es importante tener en cuenta que, desde el punto de vista matemático, el promedio de -1 y -2 será igual a -2 y la fórmula da el resultado correcto. :)
(a >> 1) + (b >> 1) + (((a & 1) + (b & 1)) >> 1)
La declaración de cambio (x >> i) en c int matemáticas es equivalente a una división por 2 al poder de i. Así que la declaración (a >> 1) + (b >> 1) es la misma que a / 2 + b / 2. Sin embargo, la media de las partes truncadas del número también debe agregarse. Este valor se puede obtener enmascarando (a y 1), agregando ((a & 1) + (b & 1)) y dividiendo (((a & 1) + (b & 1)) >> 1). La media se convierte en (a >> 1) + (b >> 1) + (((a & 1) + (b & 1)) >> 1)
Nota: la razón para usar >> y & en lugar de / y% como operadores de división y resto es una de eficiencia.