Как я могу безопасно усреднить два целых числа без знака в С++?

Ваш последний подход кажется многообещающим. Вы можете улучшить это, вручную рассматривая младшие биты a и b:

unsigned int average = (a / 2) + (b / 2) + (a & b & 1);

Это дает правильные результаты, если и a, и b нечетны.

Если вы заранее знаете, какой из них выше, возможен очень эффективный способ. В противном случае вам лучше использовать одну из других стратегий вместо условного переключения на использование этой.

unsigned int average = low + ((high - low) / 2);

Вот соответствующая статья: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

Ваш метод неверен, если оба числа нечетные, например 5 и 7, среднее значение равно 6, но ваш метод № 3 возвращает 5.

Попробуй это:

average = (a>>1) + (b>>1) + (a & b & 1)

только с математическими операторами:

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

Если вы не возражаете против небольшого встроенного ассемблера x86 (синтаксис GNU C), вы можете воспользоваться предложением supercat использовать rotate-with-carry после добавления, чтобы поместить старшие 32 бита полного 33-битного результата в регистр.

Конечно, вы обычно должны возражать против использования inline-asm, потому что это нарушает некоторые оптимизации (https://gcc.gnu.org/wiki/DontUseInlineAsm). Но вот все равно:

// works for 64-bit long as well on x86-64, and doesn't depend on calling convention
unsigned average(unsigned x, unsigned y)
{
    unsigned result;
    asm("add   %[x], %[res]\n\t"
        "rcr   %[res]"
        : [res] "=r" (result)   // output
        : [y] "%0"(y),  // input: in the same reg as results output.  Commutative with next operand
          [x] "rme"(x)  // input: reg, mem, or immediate
        :               // no clobbers.  ("cc" is implicit on x86)
    );
    return result;
}

% модификатор, сообщающий компилятору, что аргументы являются коммутативными, не на самом деле помогает улучшить asm в случае, когда я пытался, вызывая функцию с y, являющимся константой или указателем-deref (операнд памяти). Вероятно, использование ограничения соответствия для выходного операнда побеждает это, поскольку вы не можете использовать его с операндами чтения-записи.

RCR-by-one не слишком медленный, но на Skylake это все еще 3 мкп с задержкой в ​​2 цикла. Это отлично работает на процессорах AMD, где RCR имеет задержку в один цикл. (Источник: таблицы инструкций Agner Fog, см. также x86 пометить вики для ссылок на производительность x86). Это все еще лучше, чем версия @sellibitze, но хуже, чем версия @Sheldon, зависящая от порядка. (См. код на Godbolt)

Но помните, что встроенный ассемблер отменяет такие оптимизации, как распространение констант, поэтому в этом случае любая версия на чистом C++ будет лучше.

И правильный ответ...

То, что у вас есть, прекрасно, с небольшой деталью, что оно будет утверждать, что среднее значение 3 и 3 равно 2. Я предполагаю, что вы этого не хотите; к счастью, есть простое решение:

(A&B)+((A^B)>>1)

Это просто увеличивает среднее значение в случае, если оба деления были усечены.

unsigned int average = a/2 + b/2 + (a & b & 1);

Если код предназначен для встроенного микроконтроллера и скорость имеет решающее значение, может оказаться полезным язык ассемблера. На многих микроконтроллерах результат сложения естественным образом помещается во флаг переноса, и существуют инструкции для его смещения обратно в регистр. На ARM средняя операция (источник и получатель в регистрах) может выполняться двумя инструкциями; любой эквивалент на языке C, скорее всего, даст как минимум 5, а возможно, и больше.

Между прочим, на машинах с меньшим размером слова различия могут быть еще более существенными. В 8-битной серии PIC-18 для усреднения двух 32-битных чисел потребовалось бы двенадцать инструкций. Выполнение сдвигов, добавления и исправления потребовало бы 5 инструкций для каждого смещения, восьми для добавления и восьми для исправления, то есть 26 (разница не совсем в 2,5 раза, но, вероятно, более значительная в абсолютном выражении).

В C++20 вы можете использовать _1_:

Документ P0811R3, в котором представлен std::midpoint рекомендовал этот фрагмент (слегка адаптированный для работы с С++ 11):

template <class T>
constexpr T midpoint(T a, T b) noexcept;

Для полноты вот немодифицированная реализация C++20 из статьи:

#include <type_traits>

template <typename Integer>
constexpr Integer midpoint(Integer a, Integer b) noexcept {
  using U = std::make_unsigned<Integer>::type;
  return a>b ? a-(U(a)-b)/2 : a+(U(b)-a)/2;
}

ожидает avg == 5.0 для этого теста

constexpr Integer midpoint(Integer a, Integer b) noexcept {
  using U = make_unsigned_t<Integer>;
  return a>b ? a-(U(a)-b)/2 : a+(U(b)-a)/2;
}

    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    decimal avg = 0;
    for (int i = 0; i < array.Length; i++){
        avg = (array[i] - avg) / (i+1) + avg;
    }

    int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    decimal avg = 0;
    for (int i = 0; i < array.Length; i++){
        avg = (array[i] - avg) / (i+1) + avg;
    }

Предоставлено: http://www.ragestorm.net/blogs/?p=29

Вы не можете привести сумму к (((a&b << 1) + (a^b)) >> 1)?