Каков правильный способ найти среднее значение двух значений?

Ответ 1

С помощью Защищенного кодирования

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;
    }
}

Ответ 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)

Примечание: причина использования → и, а не/и% в качестве операторов деления и останова, является эффективной.

Ответ 3

Простым подходом является следующий

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, и формула дает правильный результат.:)

Ответ 4

Если вы беспокоитесь о переполнении, вы можете применить значения к большему типу для выполнения математики, а затем выполнить проверку границ.

Ответ 5

Это от Вычисление среднего числа двух целых чисел, округленных до нуля в течение одного цикла команды:

(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, гласит, что реализация может выбрать одно из трех различных представлений для целых типов данных:

  • два дополнения
  • одно дополнение
  • знак/величина

  (обычно два дополнения намного перевешивают остальные).

Ответ 6

Самый простой (и обычно самый быстрый) способ усреднить два 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.

Ответ 7

Самый простой ответ, если есть только 2 элемента, чтобы избежать переполнения, было бы:

(a/2) + (b/2) = average

Для большего количества элементов вы можете использовать:

(a/x) + (b/x) + (c/x) + (d/x) ..... = average //x = amount of elements

В математической точке зрения это никогда не достигнет переполнения, если ранее ни одно из исходных значений не выполнялось ранее, так как вы действительно не добавляете их все вместе, а скорее разделение их перед добавлением их вместе. Таким образом, нет результата любой операции, выполняемой во время вычисления, включая результат, будет когда-либо больше (по обе стороны от 0) , чем самый большой начальный элемент strong > (предполагая, что вы работаете только с Real Numbers).

Выполните следующие действия:

• Определите количество элементов в 'C', позвоните на него 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.