Cómo depurar el código Este C

Question

Durante la lectura de alguna cuestión en un sitio me encontré debajo de la pregunta en cuestión ac necesita ser depurar

unsigned int a, b, c; 
/* a and b are assume to have some values */ 
c = (a + b)/2; // <- There is a bug in this st 
What is the bug? and how you debug it? 

Algunos de la respuesta diciendo que podría causar desbordamiento (c = (a + b)/2) .pero realmente no entiendo cómo causa el desbordamiento?

Answer 1

Si a y/o b son muy grandes entonces a + b podría exceder el tamaño máximo de un entero sin signo (véase MAX_UINT en el archivo de limits.h). Esto causaría un desbordamiento y el resultado sería incorrecto. Por ejemplo, si a y b son iguales a 0x80000000, el resultado sería 0 en aritmética de 32 bits, en lugar del resultado esperado 0x80000000.

Para resolverlo se podría usar algo como esto en su lugar:

c = a/2 + b/2 + (a % 2 == 1 && b % 2 == 1); 

Si sabe que b es mayor que a entonces se podría usar esta versión un poco más simple:

c = a + (b - a)/2; 

Lee este artículo para obtener información acerca de cómo apareció este error en los algoritmos de búsqueda binarios en los idiomas populares de mayo (aunque se trata de signed int en lugar de unsigned int):

• Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken

Answer 2

podría causar desbordamiento si a y b son lo suficientemente alta para producir un a + b más alta que la representable máximo por un unsigned int.

Answer 3

a+b puede rebosar si la suma de a y b es mayor que UINT_MAX, el valor máximo para un unsigned int. Por ejemplo,

unsigned a = 1; 
unsigned b = UINT_MAX; 

printf("%u\n", (a+b)/2); 

impresiones 0.

Si usted quiere encontrar la media de dos unsigned int s sin rebosadero, lo hacen

c = a/2 + b/2 + (a % 2 & b % 2); 

(o (a%2 + b%2)/2, o (a%2 && b%2), o ((a&1) & (b&1)), etc.)

Answer 4

Si sólo se declara una variable en C sin inicializarlo, obtiene un valor impredecible. a y b pueden ser algunos valores que se encuentran actualmente en la dirección que reciben en la memoria.

Se puede depurar el código C en Eclipse CDT
http://www.eclipse.org/cdt/

Con este IDE se puede programar en C++ y C ANC que contiene el depurador GDB.
http://www.gnu.org/software/gdb/

Answer 5

Como otros dicen:

unsigned int a, b, c; 
c = (a + b)/2; 

a + b puede no representable en un unsigned int para un cierto valor de a y b.

Una situación muy similar dio lugar a un error famoso en la implementación de búsqueda binaria estándar de Java (función binarySearch).

Ver este famoso blog Joshua Blosh en 2006:

"Extra, Extra - Leer todo sobre ella: Casi todas las búsquedas binarias y Mergesorts se rompen" http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Extractos:

El error está en esta línea:

6: int mid = (low + high)/2;

más abajo:

Entonces, ¿cuál es la mejor manera de reparar el fallo? Aquí hay una forma:

6: int mid = low + ((high - low)/2);

Nótese que en Joshua puesto, high es >= low y también int objetos fueron usados, pero trata de Java firmaron desbordamiento como envoltura. En C los desbordamientos enteros con signo son comportamiento indefinido y envolvente sin signo.