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

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

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

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

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

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

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

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

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

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

   return a;
}

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

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

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

Я начал с 2-х решений, которые я имел ранее предложил:

#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.) вторая проблема на самом деле рекурсивна, так как для получения правильного ответа вы должны правильно округлить D/2. 2.) В первом случае вы часто переполняетесь, а затем недоливаете, два отменяя друг друга. Вот график ошибок из двух (неверно) алгоритмы:

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

вот сюжет 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))
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-битными или большими числами Ошибка

для 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 <= 103

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

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

int a = round(59.0 / 4);

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

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

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

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

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

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

еще один полезный макрос (должен иметь):

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

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

вот мое решение. Мне нравится это, потому что я нахожу его более читабельным и потому, что она не имеет разветвления (ни сослагательного наклонения, ни торфяники).

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

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

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, темпи = 2, остаток = 3, остаток >= темпи следовательно фактор = 15;

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

1. пусть точное значение float 59.0 / 4 будет x (здесь это 14.750000)
2. пусть наименьшее целое число меньше x будет y (здесь это 14)
3. если x-y
4. иначе y+1-это решение

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

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

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

// 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) - это будет зависеть от платформы.

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

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

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

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

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