Как избежать переполнения с помощью l + (rl) / 2 - PullRequest
Новая
       42

Как избежать переполнения с помощью l + (rl) / 2

0 голосов
/ 27 декабря 2018

Когда я изучал реализацию сортировки слиянием, я наткнулся на код ниже: 

// Same as (l+r)/2, but avoids overflow for 
// large l and h 
int m = l+(r-l)/2;

  1. Как (l + r) / 2 совпадает с l + (rl) / 2?Последнее оценивается как r / 2.

  2. Как (l + r) / 2 вызывает переполнение и как l + (rl) / 2 решает проблему?

  3. Что такое?(Я думаю, что это опечатка, которая должна быть г)

1 Ответ

0 голосов
/ 27 декабря 2018

  1. Пожалуйста, проверьте еще раз - он расширяется до l + r/2 - l/2, что составляет l/2 + r/2.Обратите внимание, что мы не можем просто использовать l/2 + r/2, поскольку будет целочисленное усечение, поэтому 3/2 + 5/2 = 1 + 2 = 3, но требуемое значение равно 4.

  2. Предположим, что оба значения l и r являются положительными значениями типа int.

Если мы имеем: 

int l = INT_MAX - 2;
int r = INT_MAX;

Тогда l + r part is INT_MAX - 2 + INT_MAX, что является целочисленным переполнением.INT_MAX - 2 + (INT_MAX - (INT_MAX - 2))/2 не имеет целочисленных переполнений, так как каждое подвыражение остается между INT_MIN и INT_MAX.

Да, это опечатка!
...