Недавно я узнал, что целочисленное переполнение - это поведение undefined в C (вопрос стороны - это также UB в С++?)
Часто в программировании на С необходимо найти среднее значение двух значений a и b. Однако выполнение (a+b)/2 может привести к переполнению и undefined.
Итак, мой вопрос: какой правильный способ найти среднее значение двух значений a и b в C?
С помощью Защищенного кодирования
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;
}
ДОПОЛНЕНИЕ
Благодаря @chux для указания проблемы округления. Здесь версия, проверенная на правильное округление...
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;
}
}
(a >> 1) + (b >> 1) + (((a & 1) + (b & 1)) >> 1)
Оператор сдвига (x → i) в c int математике эквивалентен делению на 2 на степень i. Таким образом, утверждение (a → 1) + (b → 1) совпадает с выражением /2 + b/2. Однако необходимо также добавить среднее значение укороченных частей номера. Это значение может быть получено путем маскировки (a и 1), добавления ((a и 1) + (b и 1)) и деления (((a и 1) + (b и 1)) → 1). Среднее значение становится (a → 1) + (b → 1) + (((a и 1) + (b и 1)) → 1)
Примечание: причина использования → и, а не/и% в качестве операторов деления и останова, является эффективной.
Простым подходом является следующий
int c = a / 2 + ( b + a % 2 ) / 2;
Например, a и b могут быть представлены как
a = 2 * n + r1;
b = 2 * m + r2;
Тогда
( a + b ) / 2 => ( 2 * n + r1 + 2 * m + r2 ) / 2 => 2 * n / 2 + ( b + r1 ) / 2
И последнее выражение дает вам
=> a / 2 + ( b + a % 2 ) / 2
Более правильным выражением является следующее
int c = a / 2 + b / 2 + ( a % 2 + b % 2 ) / 2;
Например, если мы имеем
int a = INT_MAX;
int b = INT_MAX;
тогда c рассчитывается как
int c = a / 2 + b / 2 + ( a % 2 + b % 2 ) / 2;
даст c == INT_MAX
EDIT: было обнаружено интересное различие между эффектом компьютерных операторов и эффектом математических операторов. Например, согласно математике -1 можно представить как
-1 = -1 * 2 + 1
что соответствует формуле
a = 2 * n + r1
2 * n должно быть целым числом, меньшим или равным tp a
Таким образом, число меньше -1 равно -2. :)
Я думаю, что общая формула, показанная мной, будет работать, требуется, чтобы для нечетных отрицательных чисел были рассмотрены даже отрицательные числа, которые меньше нечетного отрицательного числа.
кажется, что правильная формула выглядит как
int c = ( a < 0 ? a & ~1 : a ) / 2 +
( b < 0 ? b & ~1 : b ) / 2 +
( ( a & 1 ) + ( b & 1 ) ) / 2;
Важно отметить, что с математической точки зрения среднее значение -1 и -2 должно быть равно -2, и формула дает правильный результат.:)
Если вы беспокоитесь о переполнении, вы можете применить значения к большему типу для выполнения математики, а затем выполнить проверку границ.
Это от Вычисление среднего числа двух целых чисел, округленных до нуля в течение одного цикла команды:
(a >> 1) + (b >> 1) + (a & b & 0x1)
Вы должны учитывать, что:
В этой реализации определено, правильно ли смещение отрицательного целого смещает нули или единицы в биты верхнего порядка. Многие процессоры часто имеют две разные команды: арифметический сдвиг вправо (сохраняет знаковый бит) и логический сдвиг вправо (не сохраняет знаковый бит). Компилятору разрешено выбирать либо (большинство компиляторов выбирают инструкцию арифметического сдвига).
ISO/IEC 9899: 2011 §6.5.7 Операторы побитового сдвига
¶5 Результат E1 → E2 - это правые сдвиговые позиции E2 в E1. [CUT] Если E1 имеет подписанный тип и отрицательное значение, результирующее значение определяется реализацией.
Изменение выражения:
a / 2 + b / 2 + (a & b & 0x1)
не является решением, так как логические сдвиги справа эквивалентны делению на степень 2 только для положительных или беззнаковых чисел.
также (a & b & 0x1) не определен. Этот термин должен быть отличным от нуля, если оба a и b являются нечетными. Но это не удается с представлением одного дополнения и ISO C, раздел 6.2.6.2/2, гласит, что реализация может выбрать одно из трех различных представлений для целых типов данных:
(обычно два дополнения намного перевешивают остальные).
Самый простой (и обычно самый быстрый) способ усреднить два int во всем диапазоне [INT_MIN...INT_MAX] - это использовать более широкий целочисленный тип. (Предлагается @user3100381.) Назовем это int2x.
int average_int(int a, int b) {
return ((int2x) a + b)/2;
}
Конечно, это означает, что существует более широкий тип, поэтому давайте посмотрим на решение, которое не требует более широкого типа.
Задачи:
Q: Когда один int является нечетным, а другой четным, каким образом происходит округление?
A: Следуйте average_int() выше и округленно в направлении 0. (truncate).
В: Может ли код использовать %?
A: С кодом pre-C99 результат a % 2 допускает разные результаты при a < 0. Поэтому не будем использовать %.
Q: Должен ли int иметь симметричный диапазон положительных и отрицательных чисел?
A: С C99 число отрицательных чисел совпадает (или еще 1), чем число положительных чисел. Попробуем не требовать этого.
РЕШЕНИЕ:
Выполните тесты, чтобы определить, может ли произойти переполнение. Если нет, просто используйте (a + b) / 2. В противном случае добавьте половину разницы (подписанную так же, как и ответ) на меньшее значение.
Ниже приводится тот же ответ, что и average_int(), не прибегая к более широкому целочисленному типу. Он защищает от переполнения int и не требует, чтобы INT_MIN + INT_MAX был 0 или -1. Это не зависит от кодирования как 2 дополнения, 1 дополнения или знака-величины.
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;
}
Не более 3 if() встречаются с любой парой int.
Самый простой ответ, если есть только 2 элемента, чтобы избежать переполнения, было бы:
(a/2) + (b/2) = average
Для большего количества элементов вы можете использовать:
(a/x) + (b/x) + (c/x) + (d/x) ..... = average //x = amount of elements
В математической точке зрения это никогда не достигнет переполнения, если ранее ни одно из исходных значений не выполнялось ранее, так как вы действительно не добавляете их все вместе, а скорее разделение их перед добавлением их вместе. Таким образом, нет результата любой операции, выполняемой во время вычисления, включая результат, будет когда-либо больше (по обе стороны от 0) , чем самый большой начальный элемент strong > (предполагая, что вы работаете только с Real Numbers).
Выполните следующие действия:
total.average.remainder.total.average.remainder.average.Это даст вам ответ максимум на максимум 1 (десятичная цифровая система [база 10]). Я еще не знаю С++, поэтому я могу привести только пример на С#.
Псевдокод в С# (только для того, чтобы представить идею):
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.
Сжатый пример С#:
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.