Круглое деление целых беззнаковых чисел без переполнения - PullRequest
Новая
       103

Круглое деление целых беззнаковых чисел без переполнения

2 голосов
/ 21 июня 2020

Я ищу безопасный от переполнения метод для выполнения округленного деления целых чисел без знака.

У меня есть это: 

uint roundDiv(uint n, uint d)
{
    return (n + d / 2) / d;
}

Но, к сожалению, выражение n + d / 2 может переполняться .

Я думаю, мне придется проверить, меньше ли n % d, чем d / 2.

Но сам d / 2 может обрезаться (когда d нечетное).

Итак, я решил, что должен проверить, меньше ли n % d * 2, чем d.

Или даже без логического условия, полагайтесь на тот факт, что n % d * 2 / d либо 0 или 1: 

uint roundDiv(uint n, uint d)
{
    return n / d + n % d * 2 / d;
}

Это работает хорошо, однако, опять же, n % d * 2 может переполняться.

Есть ли какой-либо собственный способ достижения округлого целочисленного деления, безопасного для переполнения ?

Обновить

Я придумал следующее: 

uint roundDiv(uint n, uint d)
{
    if (n % d < (d + d % 2) / 2)
        return n / d;
    return n / d + 1;
}

Тем не менее, выражение d + d % 2 может переполняться.

Ответы [ 2 ]

2 голосов
/ 21 июня 2020

return n/d + (d-d/2 <= n%d);

1 голос
/ 21 июня 2020

Способ избежать переполнения на любом этапе - это, как заявил OP, сравнение остатка с половиной делителя, но результат не так очевиден, как кажется на первый взгляд. Вот несколько примеров в предположении, что 0.5 будет округлено в большую сторону. Сначала с нечетным делителем: 

Numerator   Divisor Required    Quotient    Remainder   Half divisor    Quot < Req?
3           3       1           1           0           1               no
4           3       1           1           1           1               no
5           3       2           1           2           1               yes
6           3       2           2           0           1               no

Выше единственное необходимое приращение - это когда d / 2 < remainder. Теперь с четным делителем: 

Numerator   Divisor Required    Quotient    Remainder   Half divisor    Quot < Req?
4           4       1           1           0           2               no
5           4       1           1           1           2               no
6           4       2           1           2           2               yes
7           4       2           1           3           2               yes
8           4       2           2           0           2               no

Но здесь требуется приращение, когда d / 2 <= remainder.

Резюме:

  • Вам нужно другое условие в зависимости от на нечетный или четный делитель.
...