Округление целочисленного деления (вместо усечения)

Ответ 1

int a = 59.0f / 4.0f + 0.5f;

Это работает только при назначении int, поскольку он отбрасывает что-либо после "."

Edit: Это решение будет работать только в самых простых случаях. Более надежным решением будет:

unsigned int round_closest(unsigned int dividend, unsigned int divisor)
{
    return (dividend + (divisor / 2)) / divisor;
}

Ответ 2

Стандартная идиома для целочисленного округления:

int a = (59 + (4 - 1)) / 4;

Вы добавляете делитель минус один к дивиденду.

Ответ 3

Код, который работает для любого знака в дивиденде и делителе:

int divRoundClosest(const int n, const int d)
{
  return ((n < 0) ^ (d < 0)) ? ((n - d/2)/d) : ((n + d/2)/d);
}

Если вы предпочитаете макрос:

#define DIV_ROUND_CLOSEST(n, d) ((((n) < 0) ^ ((d) < 0)) ? (((n) - (d)/2)/(d)) : (((n) + (d)/2)/(d)))

Макрос ядра linux DIV_ROUND_CLOSEST не работает для отрицательных делителей!

Ответ 4

Вместо этого вы должны использовать что-то вроде этого:

int a = (59 - 1)/ 4 + 1;

Я предполагаю, что вы действительно пытаетесь сделать что-то более общее:

int divide(x, y)
{
   int a = (x -1)/y +1;

   return a;
}

x + (y-1) имеет потенциал переполнения, дающий неверный результат; тогда как x - 1 будет только ниже, если x = min_int...

Ответ 5

(Edited) Целые числа округления с плавающей точкой - это самое простое решение этой проблемы; однако, в зависимости от заданного набора может быть возможно. Например, во встроенных системах решение с плавающей запятой может быть слишком дорогостоящим.

Выполнение этого с использованием целочисленной математики оказывается довольно жестким и немного неинтуитивным. Первое опубликованное решение работало хорошо для проблемы, для которой я использовал его, но после характеристики результатов в диапазоне целых чисел оказалось, что в целом это было очень плохо. Просматривая несколько книг о бит-сплетении и встроенной математике, получим несколько результатов. Несколько заметок. Во-первых, я тестировал только положительные целые числа, моя работа не включает отрицательные числители или знаменатели. Во-вторых, и исчерпывающий тест 32-битных целых чисел является вычислительным, поэтому я начал с 8-битных целых чисел, а затем уверен, что получил аналогичные результаты с 16-битными целыми числами.

Я начал с двух предложенных мной решений:

#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)

#define DIVIDE_WITH_ROUND(N, D) (N == 0) ? 0:(N - D/2)/D + 1;

Моя мысль заключалась в том, что первая версия будет переполняться большими числами и вторым нижним потоком с небольшими номерами. Я не принимал во внимание две вещи. 1.) Вторая проблема на самом деле рекурсивна, так как для получения правильного ответа вам нужно правильно округлить D/2. 2.) В первом случае вы часто переполняете, а затем переполняете, два отменяют друг друга. Вот график ошибок двух (неправильных) алгоритмов:

Этот график показывает, что первый алгоритм неверен только для малых знаменателей (0 < d < 10). Неожиданно он фактически обрабатывает большие числители лучше, чем вторая версия.

Вот график второго алгоритма:

Как и ожидалось, он терпит неудачу для небольших числителей, но также терпит неудачу для более крупных числителей, чем первая версия.

Очевидно, что это лучшая отправная точка для правильной версии:

#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)

Если ваши знаменатели равны > 10, тогда это будет работать правильно.

Для D == 1 необходим специальный случай, просто возвращаем N. Для D == 2, = N/2 + (N и 1) необходим специальный случай. //Round up if odd.

D >= 3 также имеет проблемы, когда N становится достаточно большим. Оказывается, что большие знаменатели имеют проблемы с большими числителями. Для 8-битного знакового числа проблемные точки

if (D == 3) && (N > 75))
else if ((D == 4) && (N > 100))
else if ((D == 5) && (N > 125))
else if ((D == 6) && (N > 150))
else if ((D == 7) && (N > 175))
else if ((D == 8) && (N > 200))
else if ((D == 9) && (N > 225))
else if ((D == 10) && (N > 250))

(возврат D/N для них)

Итак, в общем случае точка, где определенный числитель плоха, где-то рядом N > (MAX_INT - 5) * D/10

Это не точно, но близко. При работе с 16-битными или большими номерами ошибка < 1%, если вы просто выполняете разделение C (усечение) для этих случаев.

Для 16-разрядных подписных номеров тесты будут

if ((D == 3) && (N >= 9829))
else if ((D == 4) && (N >= 13106))
else if ((D == 5) && (N >= 16382))
else if ((D == 6) && (N >= 19658))
else if ((D == 7) && (N >= 22935))
else if ((D == 8) && (N >= 26211))
else if ((D == 9) && (N >= 29487))
else if ((D == 10) && (N >= 32763))

Конечно, для целых чисел без знака MAX_INT будет заменен на MAX_UINT. Я уверен, что существует точная формула для определения наибольшего N, который будет работать для определенного D и количества бит, но у меня нет больше времени для работы над этой проблемой...

(Кажется, сейчас отсутствует этот график, я отредактирую и добавлю позже.) Это график 8-разрядной версии со специальными случаями, отмеченными выше:! [8 бит подписан с особыми случаями для 0 < N <= 10 3

Обратите внимание, что для 8 бит ошибка составляет 10% или меньше для всех ошибок на графике, 16 бит - 0,1%.

Ответ 6

Как написано, вы выполняете целочисленную арифметику, которая автоматически просто усекает любые десятичные результаты. Чтобы выполнить арифметику с плавающей запятой, измените константы как значения с плавающей запятой:

int a = round(59.0 / 4);

Или переведите их в тип float или другой тип с плавающей запятой:

int a = round((float)59 / 4);

В любом случае вам нужно сделать окончательное округление с помощью функции round() в заголовке math.h, поэтому обязательно #include <math.h> и использовать компилятор, совместимый с C99.

Ответ 7

int a, b;
int c = a / b;
if(a % b) { c++; }

Проверка того, есть ли остаток, позволяет вручную округлить коэффициент целочисленного деления.

Ответ 8

#define CEIL(a, b) (((a) / (b)) + (((a) % (b)) > 0 ? 1 : 0))

Еще один полезный MACROS (ДОЛЖЕН ИМЕТЬ):

#define MIN(a, b)  (((a) < (b)) ? (a) : (b))
#define MAX(a, b)  (((a) > (b)) ? (a) : (b))
#define ABS(a)     (((a) < 0) ? -(a) : (a))

Ответ 9

Из ядра Linux (GPLv2):

/*
 * Divide positive or negative dividend by positive divisor and round
 * to closest integer. Result is undefined for negative divisors and
 * for negative dividends if the divisor variable type is unsigned.
 */
#define DIV_ROUND_CLOSEST(x, divisor)(          \
{                           \
    typeof(x) __x = x;              \
    typeof(divisor) __d = divisor;          \
    (((typeof(x))-1) > 0 ||             \
     ((typeof(divisor))-1) > 0 || (__x) > 0) ?  \
        (((__x) + ((__d) / 2)) / (__d)) :   \
        (((__x) - ((__d) / 2)) / (__d));    \
}                           \
)

Ответ 10

Заимствование из @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)))

Ответ 11

Вот мое решение. Мне это нравится, потому что я считаю его более читаемым и потому, что он не имеет ветвления (ни ifs, ни тройки).

int32_t divide(int32_t a, int32_t b) {
  int32_t resultIsNegative = ((a ^ b) & 0x80000000) >> 31;
  int32_t sign = resultIsNegative*-2+1;
  return (a + (b / 2 * sign)) / b;
}

Полная тестовая программа, которая иллюстрирует предполагаемое поведение:

#include <stdint.h>
#include <assert.h>

int32_t divide(int32_t a, int32_t b) {
  int32_t resultIsNegative = ((a ^ b) & 0x80000000) >> 31;
  int32_t sign = resultIsNegative*-2+1;
  return (a + (b / 2 * sign)) / b;
}

int main() {
  assert(divide(0, 3) == 0);

  assert(divide(1, 3) == 0);
  assert(divide(5, 3) == 2);

  assert(divide(-1, 3) == 0);
  assert(divide(-5, 3) == -2);

  assert(divide(1, -3) == 0);
  assert(divide(5, -3) == -2);

  assert(divide(-1, -3) == 0);
  assert(divide(-5, -3) == 2);
}

Ответ 12

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, следовательно, quotient = 15;

Ответ 13

double a=59.0/4;
int b=59/4;
if(a-b>=0.5){
    b++;
}
printf("%d",b);

• пусть точное значение поплавка 59.0/4 будет x (здесь оно равно 14.750000)
• пусть наименьшее целое число меньше x равно y (здесь оно равно 14)
• если x-y < 0,5, тогда y является решением
• else y + 1 - решение

Ответ 14

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

// 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) vs. (d/2) скорее всего зависит от платформы.

Ответ 15

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

Ответ 16

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

Ответ 17

Здесь решение, которое правильно округляет частное до ближайшего целого числа для положительных и отрицательных операндов и НЕ использует условные ветки. Предполагается, что 32-разрядные 2-значные дополнения и требуется арифметическое смещение вправо (ASR), поэтому, вероятно, больше подходит для реализации в сборке, чем C.

#define ASR31(x)        ((x) < 0 ? -1 : 0)  // Simulates a 31-bit arithmetic shift right
#define ROUNDING(x,y)   ((((ASR31((x)^(y)) * (y)) * 2) + (y)) / 2)
#define QUOTIENT(x,y)   (((x) + ROUNDING(x,y)) / (y))

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

Ответ 18

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

Я еще не скомпилировал его, но я протестировал алгоритм на электронной таблице 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;
}

Ответ 19

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

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

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