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

Ответ 1

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

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

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

Ответ 2

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

ИЗМЕНИТЬ

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

Ответ 3

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

Попробуйте следующее:

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

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

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

Ответ 4

Если вы не возражаете против небольшой встроенной сборки 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;
}

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

Как вы можете видеть в проводнике компилятора Godbolt, это компилируется правильно, а также версия, в которой мы меняем операнды на unsigned long, с тем же встроенным asm. Однако clang3.9 делает беспорядок, и решает использовать параметр "m" для ограничения "rme", поэтому он хранится в памяти и использует операнд памяти.

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

Но помните, что inline-asm побеждает оптимизации, такие как постоянное распространение, поэтому в этом случае любая версия pure-С++ будет лучше.

Ответ 5

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

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

Ответ 6

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

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

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

Ответ 7

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

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

Ответ 8

Использовать 64-битный unsigned int в качестве заполнителя для суммы, отбрасывать на int после деления на 2. Сомнительно, является ли это "лучше", но вы, конечно, избегаете проблемы с переполнением с минимальными усилиями.

Ответ 9

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

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

Ответ 10

(((a&b << 1) + (a^b)) >> 1) также является хорошим способом.

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