Округление целочисленного деления (вместо усечения) - PullRequest
63 голосов
/ 11 марта 2010

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

int a = 59 / 4;

, что было бы 14,75, если рассчитать с плавающей запятой; как я могу сохранить результат как 15 в «а»?

Ответы [ 20 ]

2 голосов
/ 05 января 2015

Заимствование у @ericbn, которое я предпочитаю определять как

#define DIV_ROUND_INT(n,d) ((((n) < 0) ^ ((d) < 0)) ? (((n) - (d)/2)/(d)) : (((n) + (d)/2)/(d)))
or if you work only with unsigned ints
#define DIV_ROUND_UINT(n,d) ((((n) + (d)/2)/(d)))
1 голос
/ 06 августа 2011
int divide(x,y){
 int quotient = x/y;
 int remainder = x%y;
 if(remainder==0)
  return quotient;
 int tempY = divide(y,2);
 if(remainder>=tempY)
  quotient++;
 return quotient;
}

например, 59/4 частное = 14, tempY = 2, остаток = 3, остаток> = tempY, следовательно, частное = 15;

1 голос
/ 24 сентября 2016
double a=59.0/4;
int b=59/4;
if(a-b>=0.5){
    b++;
}
printf("%d",b);
  1. пусть точное значение с плавающей запятой 59,0 / 4 будет х (здесь это 14,750000)
  2. пусть наименьшее целое число меньше x будет y (здесь это 14)
  3. если x-y <0,5, то y является решением </li>
  4. иначе у + 1 - решение
0 голосов
/ 09 марта 2014

Для некоторых алгоритмов вам нужно постоянное смещение, когда «ближайший» - это ничья.

// round-to-nearest with mid-value bias towards positive infinity
int div_nearest( int n, int d )
   {
   if (d<0) n*=-1, d*=-1;
   return (abs(n)+((d-(n<0?1:0))>>1))/d * ((n<0)?-1:+1);
   }

Это работает независимо от знака числителя или знаменателя.


Если вы хотите сопоставить результаты round(N/(double)D) (деление и округление с плавающей запятой), вот несколько вариантов, которые все дают одинаковые результаты:

int div_nearest( int n, int d )
   {
   int r=(n<0?-1:+1)*(abs(d)>>1); // eliminates a division
// int r=((n<0)^(d<0)?-1:+1)*(d/2); // basically the same as @ericbn
// int r=(n*d<0?-1:+1)*(d/2); // small variation from @ericbn
   return (n+r)/d;
   }

Примечание. Относительная скорость (abs(d)>>1) против (d/2) может зависеть от платформы.

0 голосов
/ 30 октября 2015

Безопасный код C (если у вас нет других методов обработки / 0):

return (_divisor > 0) ? ((_dividend + (_divisor - 1)) / _divisor) : _dividend;

Конечно, это не решает проблемы, возникающие из-за неправильного возвращаемого значения в результате неверных входных данных.

0 голосов
/ 22 декабря 2018

Следующее правильно округляет частное до ближайшего целого числа как для положительного, так и для отрицательного операндов БЕЗ плавающей запятой или условных ветвей (см. Вывод сборки ниже). Предполагается, что N-бит 2 дополняет целые числа.

#define ASR(x) ((x) < 0 ? -1 : 0)  // Compiles into a (N-1)-bit arithmetic shift right
#define ROUNDING(x,y) ( (y)/2 - (ASR((x)^(y)) & (y)))

int RoundedQuotient(int x, int y)
   {
   return (x + ROUNDING(x,y)) / y ;
   }

Значение ROUNDING будет иметь тот же знак, что и дивиденд (x), и половину величины делителя (y). Таким образом, добавление ROUNDING к дивиденду увеличивает его величину до того, как целочисленное деление усекает результирующий коэффициент. Вот вывод компилятора gcc с оптимизацией -O3 для 32-битного процессора ARM Cortex-M4:

RoundedQuotient:                // Input parameters: r0 = x, r1 = y
    eor     r2, r1, r0          // r2 = x^y
    and     r2, r1, r2, asr #31 // r2 = ASR(x^y) & y
    add     r3, r1, r1, lsr #31 // r3 = (y < 0) ? y + 1 : y
    rsb     r3, r2, r3, asr #1  // r3 = y/2 - (ASR(x^y) & y)
    add     r0, r0, r3          // r0 = x + (y/2 - (ASR(x^y) & y)
    sdiv    r0, r0, r1          // r0 = (x + ROUNDING(x,y)) / y
    bx      lr                  // Returns r0 = rounded quotient
0 голосов
/ 06 сентября 2015

Я столкнулся с той же трудностью. Код ниже должен работать для положительных целых чисел.

Я еще не скомпилировал его, но я протестировал алгоритм в электронной таблице Google (знаю, wtf), и он работал.

unsigned int integer_div_round_nearest(unsigned int numerator, unsigned int denominator)
{
    unsigned int rem;
    unsigned int floor;
    unsigned int denom_div_2;

    // check error cases
    if(denominator == 0)
        return 0;

    if(denominator == 1)
        return numerator;

    // Compute integer division and remainder
    floor = numerator/denominator;
    rem = numerator%denominator;

    // Get the rounded value of the denominator divided by two
    denom_div_2 = denominator/2;
    if(denominator%2)
        denom_div_2++;

    // If the remainder is bigger than half of the denominator, adjust value
    if(rem >= denom_div_2)
        return floor+1;
    else
        return floor;
}
0 голосов
/ 31 января 2015

Если вы делите положительные целые числа, вы можете сдвинуть его вверх, выполнить деление, а затем проверить бит справа от действительного b0. Другими словами, 100/8 - это 12,5, но вернется 12. Если вы сделаете (100 << 1) / 8, вы можете проверить b0, а затем округлить после сдвига результата обратно вниз.

0 голосов
/ 18 марта 2019

Некоторые варианты деления на 4

return x/4 + (x/2 % 2);
return x/4 + (x % 4 >= 2)

Или вообще деление на любую степень 2

return x/y + x/(y/2) % 2;    // or
return (x >> i) + ((x >> i - 1) & 1);  // with y = 2^i

Работает путем округления в большую сторону, если дробная часть ⩾ 0,5, т. Е. Первая цифра / base / 2. В двоичном коде это эквивалентно добавлению первого дробного бита к результату

Этот метод имеет преимущество в архитектурах с регистром флагов, поскольку флаг переноса будет содержать последний бит, который был сдвинут . Например, на x86 он может быть оптимизирован в

shr eax, i
adc eax, 0

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

(x - 1)/y + ((x - 1)/(y/2) & 1)

мы можем заставить работать как для положительных, так и для отрицательных значений с

int t = x + (x >> 31);
return (t >> i) + ((t >> i - 1) & 1);
0 голосов
/ 26 апреля 2014

попробуйте использовать функцию math ceil, которая делает округление. Math Ceil !

...