Как я могу безопасно средние два без знака в C ++?
-
26-09-2019 - |
Вопрос
Используя целочисленную математику в одиночку, я бы хотел «безопасно» в среднем два без знака в 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
Есть ли лучшие способы?
Решение
Ваш последний подход кажется многообещающим. Вы можете улучшить это, вручную, учитывая самые низкие биты 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 для использования вращаться После добавления поставить высокие 32 бита полного 33-битного привода в реестр.
Конечно, вы обычно должен разум использует встроенный ASM, потому что он поражает некоторые оптимизации (https://gcc.gnu.org/wiki/dontuseusinineasm.). Но здесь мы идем все равно:
// 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;
}
То %
модификатор Чтобы сказать компилятору, args являются коммутативным, на самом деле не помогает сделать лучше ASM в том случае, когда я пробовал, вызывая функцию с помощью y, будучи постоянным или указателем-дерефом (операндом памяти). Вероятно, используя подходящее ограничение для выходного операнда, пораженные, поскольку вы не можете использовать его с операндами чтения.
Как вы видете на Godbolt Compiler Explorer, это компилирует правильно, и так ли версия, где мы меняем операнды unsigned long
, с таким же встроенным ASM. Clang3.9 делает это беспорядок, хотя и решит использовать "m"
Вариант для "rme"
Ограничение, поэтому он хранит в память и использует операнду памяти.
RCR-BY-One не слишком медленный, но это все еще 3 UOPS на Skylake, с 2 цикла задержки. Он отлично подходит на CPU AMD, где RCR имеет однокольный задержка. (Источник: Столы инструкции Agner Gog, см. также x86. Tag Wiki для X86 Ссылки производительности). Это все еще лучше, чем @ версия Sellibitze, но хуже, чем @ Sheldon, зависимая версия для зависимости. (См. Код на Godbolt)
Но помните, что встроенный asm поражает оптимизацию, такие как постоянное распространение, поэтому любая версия Pure-C ++ будет лучше в этом случае.
И правильный ответ ...
(A&B)+((A^B)>>1)
То, что у вас есть в порядке, с незначительными деталями, что это утверждает, что в среднем 3 и 3 равно 2. Я предполагаю, что вы этого не хотите; К счастью, есть простое исправление:
unsigned int average = a/2 + b/2 + (a & b & 1);
Это просто не ударило среднее резервное копирование в том случае, если оба подразделения были усечены.
Если код предназначен для встроенного микро, а если скорость имеет решающее значение, язык сборки может быть полезен. На многих микроконтроллерах результат добавления, естественно, перейдет в флаг для переноски, и существуют инструкции, чтобы перенести его обратно в реестр. На руке средняя операция (источник и dest. В регистрах) могут быть сделаны в двух инструкциях; Любой эквивалент языка C-языка, скорее всего, будет принести как минимум 5, и, вероятно, довольно больше, чем это.
Кстати, на машинах с более короткоми размерами слов различия могут быть еще более существенными. На 8-битной серии PIC-18, усреднение двух 32-битных номеров займет двенадцать инструкций. Делая сдвиги, добавление и коррекция, потребуется 5 инструкций для каждой смены, восемь для добавления и восемь для коррекции, поэтому 26 (не совсем 2,5x разница, но, вероятно, более значительна в абсолютных условиях).
(((a&b << 1) + (a^b)) >> 1)
тоже хороший способ.
Учтивость: http://www.ragestorm.net/blogs/?p=29.
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 для этого теста