Как отлаживать код Этого C

Question

При чтении какого-то вопроса на сайте я наткнулся ниже вопроса, где переменный ток вопрос должен быть отлаживать

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? 

Некоторые из ответа говоря, что это может вызвать переполнение (с = (а + b)/2). Но действительно не получилось, как это вызывает переполнение?

Answer 1

Если a и/или b очень велики, то a + b может превысить максимальный размер целого числа без знака (см MAX_UINT в файле limits.h). Это приведет к переполнению, поэтому результат будет неправильным. Например, если a и b равны 0x80000000, результат будет равен 0 в 32-разрядной арифметике, а не ожидаемый результат 0x80000000.

Чтобы решить эту проблему, вы можете использовать что-то вроде этого, вместо:

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

Если вы знаете, что b больше a, то вы можете использовать эту немного более простой вариант:

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

Читать эту статью для получения информации о том, как эта ошибка появилась в бинарных алгоритмах поиска в популярных языках (хотя она говорит о signed int, а не о unsigned int):

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

Answer 2

Это может вызвать переполнение, если a и b достаточно высоки, чтобы получить a + b выше, чем максимальное представимыми в unsigned int.

Answer 3

a+b может вытечь, если сумма a и b больше, чем UINT_MAX, максимальное значение для unsigned int. НАПРИМЕР,

unsigned a = 1; 
unsigned b = UINT_MAX; 

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

печатает 0.

Если вы хотите, чтобы найти среднее значение двух unsigned int с без перелива, сделать

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

(или (a%2 + b%2)/2 или (a%2 && b%2) или ((a&1) & (b&1)) и т.д.)

Answer 4

Если вы только объявить переменную C без инициализации, он получает непредсказуемое значение. a и b могут быть некоторыми значениями, которые в настоящее время находятся в адресе, который они получают в памяти.

Вы можете отлаживать код С в Eclipse CDT
http://www.eclipse.org/cdt/

С помощью этой IDE можно запрограммировать в C ANC C++ и содержит отладчик GDB.
http://www.gnu.org/software/gdb/

Answer 5

Как говорят другие:

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

a + b может быть не представима в unsigned int при некотором значении a и b.

Очень похожая ситуация привела к известной ошибке в стандартной реализации двоичного поиска Java (binarySearch).

Посмотреть этот известный блог Джошуа Blosh в 2006 году:

"Extra, Extra - Read All About It: Почти все бинарные запросы и Mergesorts сломаны" http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Выдержки:

Ошибка в этой строке:

6: int mid = (низкий + высокий)/2;

дальше:

Так что это лучший способ, чтобы исправить эту ошибку? Вот один из способов:

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

Обратите внимание, что в Joshua посте, high является >= low, а также int объектов были использованы, но Java трактует подписали переполнение в упаковке. В C-значении целочисленные переполнения являются неопределенным поведением и неподписанным обрывом.