Fast Ceiling of an Integer Division in C/C++

Fast ceiling of an integer division in C / C++

For positive numbers where you want to find the ceiling (q) of x when divided by y.

unsigned int x, y, q;

To round up ...

q = (x + y - 1) / y;

or (avoiding overflow in x+y)

q = 1 + ((x - 1) / y); // if x != 0

Divide integers with floor, ceil and outwards rounding modes in C++

In C++, the / division operation rounds using truncate (towards zero) by default. We can adjust the result of division towards zero to implement other rounding modes.
Note that when the division has no remainder, all rounding modes are equivalent because no rounding is necessary.

With that in mind, we can implement the different rounding modes.
But before we get started, we will need a helper template for the return types so that we don't use auto return types everywhere:

#include <type_traits>

/**
 * Similar to std::common_type_t<A, B>, but if A or B are signed, the result will also be signed.
 *
 * This differs from the regular type promotion rules, where signed types are promoted to unsigned types.
 */
template <typename A, typename B>
using common_signed_t =
    std::conditional_t<std::is_unsigned_v<A> && std::is_unsigned_v<B>,
                       std::common_type_t<A, B>,
                       std::common_type_t<std::make_signed_t<A>, std::make_signed_t<B>>>;

Ceil (towards +∞)

Ceil rounding is identical to truncate rounding for negative quotients, but for positive quotients and nonzero remainders we round away from zero. This means that we increment the quotient for nonzero remainders.

Thanks to if-constexpr, we can implement everything using only a single function:

template <typename Dividend, typename Divisor>
constexpr common_signed_t<Dividend, Divisor> div_ceil(Dividend x, Divisor y)
{
    if constexpr (std::is_unsigned_v<Dividend> && std::is_unsigned_v<Divisor>) {
        // quotient is always positive
        return x / y + (x % y != 0);  // uint / uint
    }
    else if constexpr (std::is_signed_v<Dividend> && std::is_unsigned_v<Divisor>) {
        auto sy = static_cast<std::make_signed_t<Divisor>>(y);
        bool quotientPositive = x >= 0;
        return x / sy + (x % sy != 0 && quotientPositive);  // int / uint
    }
    else if constexpr (std::is_unsigned_v<Dividend> && std::is_signed_v<Divisor>) {
        auto sx = static_cast<std::make_signed_t<Dividend>>(x);
        bool quotientPositive = y >= 0;
        return sx / y + (sx % y != 0 && quotientPositive);  // uint / int
    }
    else {
        bool quotientPositive = (y >= 0) == (x >= 0);
        return x / y + (x % y != 0 && quotientPositive);  // int / int
    }
}

At first glance, the implementations for signed types seem expensive, because they use both an integer division and a modulo division. However, on modern architectures division typically sets a flag that indicates whether there was a remainder, so x % y != 0 is completely free in this case.

You might also be wondering why we don't compute the quotient first and then check if the quotient is positive. This wouldn't work because we already lost precision during this division, so we can't perform this test afterwards. For example:

-1 / 2 = -0.5
// C++ already rounds towards zero
-0.5 -> 0
// Now we think that the quotient is positive, even though it is negative.
// So we mistakenly round up again:
0 -> 1

Floor (towards -∞)

Floor rounding is identical to truncate for positive quotients, but for negative quotients we round away from zero. This means that we decrement the quotient for nonzero remainders.

template <typename Dividend, typename Divisor>
constexpr common_signed_t<Dividend, Divisor> div_floor(Dividend x, Divisor y)
{
    if constexpr (std::is_unsigned_v<Dividend> && std::is_unsigned_v<Divisor>) {
        // quotient is never negative
        return x / y;  // uint / uint
    }
    else if constexpr (std::is_signed_v<Dividend> && std::is_unsigned_v<Divisor>) {
        auto sy = static_cast<std::make_signed_t<Divisor>>(y);
        bool quotientNegative = x < 0;
        return x / sy - (x % sy != 0 && quotientNegative);  // int / uint
    }
    else if constexpr (std::is_unsigned_v<Dividend> && std::is_signed_v<Divisor>) {
        auto sx = static_cast<std::make_signed_t<Dividend>>(x);
        bool quotientNegative = y < 0;
        return sx / y - (sx % y != 0 && quotientNegative);  // uint / int
    }
    else {
        bool quotientNegative = (y < 0) != (x < 0);
        return x / y - (x % y != 0 && quotientNegative);  // int / int
    }
}

The implementation is almost identical to that of div_ceil.

Away From Zero

Away from zero is the exact opposite of truncate. Basically, we need to increment or decrement depending on the sign of the quotient, but only if there is a remainder. This can be expressed as adding the sgn of the quotient onto the result:

template <typename Int>
constexpr signed char sgn(Int n)
{
    return (n > Int{0}) - (n < Int{0});
};

Using this helper function, we can fully implement up rounding:

template <typename Dividend, typename Divisor>
constexpr common_signed_t<Dividend, Divisor> div_up(Dividend x, Divisor y)
{
    if constexpr (std::is_unsigned_v<Dividend> && std::is_unsigned_v<Divisor>) {
        // sgn is always 1
        return x / y + (x % y != 0);  // uint / uint
    }
    else if constexpr (std::is_signed_v<Dividend> && std::is_unsigned_v<Divisor>) {
        auto sy = static_cast<std::make_signed_t<Divisor>>(y);
        signed char quotientSgn = sgn(x);
        return x / sy + (x % sy != 0) * quotientSgn;  // int / uint
    }
    else if constexpr (std::is_unsigned_v<Dividend> && std::is_signed_v<Divisor>) {
        auto sx = static_cast<std::make_signed_t<Dividend>>(x);
        signed char quotientSgn = sgn(y);
        return sx / y + (sx % y != 0) * quotientSgn;  // uint / int
    }
    else {
        signed char quotientSgn = sgn(x) * sgn(y);
        return x / y + (x % y != 0) * quotientSgn;  // int / int
    }
}

Unresolved Problems

Unfortunately these functions won't work for all possible inputs, which is a problem that we can not solve.
For example, dividing uint32_t{3 billion} / int32_t{1} results in int32_t(3 billion) which isn't representable using a 32-bit signed integer.
We get an underflow in this case.

Using larger return types would be an option for everything but 64-bit integers, where there isn't a larger alternative available.
Hence, it is the responsibility of the user to ensure that when they pass an unsigned number into this function, it is equivalent to its signed representation.

Fast floor of a signed integer division in C / C++

Floored division can be performed by using a division and modulo.

There is no reason to avoid the modulo call since modern compilers optimize a divide & modulo into a single divide.

int floor_div(int a, int b) {
    int d = a / b;
    int r = a % b;  /* optimizes into single division. */
    return r ? (d - ((a < 0) ^ (b < 0))) : d;
}

Ceiling of Long Integer division in c++

Although it can store numbers with much larger magnitude, a typical implementation of double can only maintain around 15-16 digits of precision.

Subtraction with floating point can also be something of a problem, especially if the two numbers are of nearly the same magnitude. If both inputs are (say) 50 bits, but the first 40 bits are identical, those will cancel out, and the result will only have about 10 bits.

So, first of all, you probably want to do all the math with long long if that's the type you want for the result. Second, you might at least want to consider rearranging your (a-b)/c to a/c-b/c to delay the subtraction as long as possible.

Division Round Up in C++

If a and b are both positive, you can avoid floating point completely and get both exact results (no problems with FP rounding) and faster execution time through the classical method:

int res = (a + (b - 1)) / b;

For negative a you don't need any correction - the truncation performed by integer division already has the semantics matching your ceil formula; so, if you want a more general case:

int res = (a<0 ? a : (a + (b - 1))) / b;

Rounding integer division (instead of truncating)

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

This only works when assigning to an int as it discards anything after the '.'

Edit:
This solution will only work in the simplest of cases. A more robust solution would be:

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

Dividing 2 long values produces wrong output in c++

Because of order of evaluation of long output = ceil(first/second);

The first operation is first/second, 100/1000. Once you are using integer types (long is an integer) the result will be a long and it is truncated towards zero. 100/1000 =0

Then you have:
ceil(0) = 0 // as expected

long output = 0

What is the behavior of integer division?

Will result always be the floor of the division? What is the defined behavior?

Not quite. It rounds toward 0, rather than flooring.

6.5.5 Multiplicative operators

6 When integers are divided, the result of the / operator is the algebraic quotient with any
fractional part discarded.⁸⁸⁾ If the quotient a/b is representable, the expression
(a/b)*b + a%b shall equal a.

and the corresponding footnote:

88. This is often called ‘‘truncation toward zero’’.

Of course two points to note are:

3 The usual arithmetic conversions are performed on the operands.

and:

5 The result of the / operator is the
quotient from the division of the
first operand by the second; the
result of the % operator is the
remainder. In both operations, if the
value of the second operand is zero,
the behavior is undefined.

[Note: Emphasis mine]

What operators can be used to ceil an integer division?

Ceiling of integer division:

unsigned int dividend, divisor, c;
/* dividend != 0 && divisor != 0 */
c = 1 + ((dividend - 1) / divisor);

Your program would then look something like this:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    unsigned int giant, dwarf, c;

    printf("Height of giant: ");
    scanf("%u", &giant);
    printf("Height of dwarf: ");
    scanf("%u", &dwarf);

    /* the heights can't be 0 */
    if (giant == 0 || dwarf == 0) {
        printf("The heights need to be greater than 0.\n");
        exit(EXIT_FAILURE);
    }

    /* ceil giant divided by dwarf */
    c = 1 + ((giant - 1) / dwarf);

    printf("It takes %u dwarfs to be as high "
           "or higher than a giant.\n", c);

    return 0;
}

c integer division not returning correct quotient

Assuming that r, g, and b have integer types, the expression (r + g + b) / 3 performs integer division because all operands have integer type. This means that any fractional part of the division gets truncated.

Change the expression to this:

(r + g + b) / 3.0

The constant 3.0 has type double, so this will perform floating point division. Then rounding the result of this expression will give you the desired result.

---

Related Topics