Шукаєте канонічний приклад цієї проблеми переповнення - c, переповнення

Це нещодавно з'явилося в інтерв'ю (концепція), і я обговорював його сьогодні з одним. Ось ідея:

Припустимо, ви обчислюєте точковий продукт тривимірного вектора. Проста функція була б "return (x1 * x2) + (y1 * y2) + (z1 * z2)".

Однак, якщо перший і другий термін є великимипозитивні цифри, вони можуть переповнюватися, навіть якщо вони відповідають в межах допустимого діапазону. Наприклад, припустимо, що цілочисельний ліміт 128. 100 + 100 - 80 = 120, але якщо ви зробите перші два додавання, спочатку ви переповнетеся.

У університетському класі це прийшло на спризначення, де ми обчислювали щось, що ми, ймовірно, робили тисячу разів до цього, але ніколи не звертали уваги на переповнення (це була та частина, коли ми дізналися про написання санітарного коду), як взяти середнє або щось подібне.

Хто-небудь має уявлення, в якому контексті це могло статися? Я знаю, що це була ситуація, коли вам доводилося використовувати порівняння до або замість додавання / віднімання, щоб уникнути цього переповнення

Відповіді:

Бінарний пошук - це класичний приклад. Багато багатьох реалізацій виконують обчислення, які в основному знаходять середину двох індексів: (висока + низька) / 2 але якщо високий і низький - кожен з цілих чисел.MAX_VALUE або еквівалент для вашої мови, високий + низький переповнення, перш ніж може відбутися поділ, і ваша відповідь неправильна:

http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

У цьому випадку можна легко виправити: висока / 2 + низька / 2 замість цього, який не переповнюється, але це майже універсальна помилка в реалізаціях бінарного пошуку, і це перше, що потрібно врахувати, коли хтось говорить про переповнення в обчисленні, яке має призвести до непереповнення значення.