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

Question

Используя только целочисленную математику, я бы хотел "безопасно" усреднить два целых числа без знака в C ++.

То, что я имею в виду под "безопасно", - это избегать переполнений (и всего, что можно придумать).

Например, усреднить 200 и 5000 легко:

unsigned int a = 200;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2600 as intended

Но в случаеиз 4294967295 и 5000 затем:

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a + b) / 2; // Equals: 2499 instead of 2147486147

Лучшее, что я придумал, это:

unsigned int a = 4294967295;
unsigned int b = 5000;
unsigned int average = (a / 2) + (b / 2); // Equals: 2147486147 as expected

Есть ли лучшие способы?

Answer 1

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

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

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

Answer 2

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

EDIT

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

Answer 3

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

Попробуйте:

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

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

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

Answer 4

Если вы не возражаете против небольшой встроенной сборки x86 (синтаксис GNU C), вы можете воспользоваться предложением суперкатера использовать 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, являющимся константой или указателем с разыменованием (память операнд). Вероятно, использование соответствия для выходного операнда побеждает это, поскольку вы не можете использовать его с операндами чтения-записи.

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

---

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

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

Answer 5

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

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

Answer 6

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

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

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

Answer 7

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

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

Answer 8

Последний подход

unsigned int average = (a / 2) + (b / 2); // Equals: 2147486147 as expected

иногда не работает из-за ошибок округления.

Answer 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 для этого теста

Answer 10

(((a&b << 1) + (a^b)) >> 1) тоже хороший способ.

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