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

Question

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

int a = 59 / 4;

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

Answer 1

Стандартный способ округления до целого числа:

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

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

Answer 2

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

Answer 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 не работает для отрицательных делителей!

Answer 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 ...

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

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

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

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

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

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

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

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

Для D == 1 требуется особый случай, просто верните N. Особый случай необходим для D == 2, = N / 2 + (N & 1) // Округление, если нечетное.

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

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

(верните D / N для них)

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

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

Для 16-битных чисел со знаком тесты будут

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

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

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

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

Answer 6

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

int a = round(59.0 / 4);

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

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

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

Answer 7

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

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

Answer 8

Из ядра 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));    \
}                           \
)

Answer 9

#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))

Answer 10

Вот мое решение. Мне это нравится, потому что я нахожу его более читаемым и потому что оно не имеет разветвлений (ни 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);
}