How to Get the Ceiling of an Integer Division in C

The standard ceil function (declared in <math.h>) is a staple for finding the least integer greater than or equal to a non-integer value. It receives a double, and returns a double, although the returned value is guaranteed not to have a fractional component. Since C99, the ceilf and ceill functions have also been available for use with float and long double types, respectively. The ceil function is prototyped as:

double ceil(double x);

Let’s say we have two non-zero, non-negative integer values, x and y, and we need to divide x by y and obtain the ceiling of the result in the form of an integer z. If we have floating point types available and they are efficient, or we don’t care about the performance of the operation (e.g., it’s done only once during initialization, etc.), then using the standard ceil library function will do the job:

int z = (int)ceil((double)x / y);

There’s quite a bit going on here. First, we need to cast either x or y to double, or the division operation will be an integer division, truncating any fractional part of the result. For the ceil function to do its job for us, the division operation needs to retain the fractional part of the result, so at least one of the division operands needs to be a double. Then, we need to convert the double result of the ceil function to an int, so that the compiler doesn’t complain about possible loss of data when storing the result into z. So, this line effectively:

1. Performs one int to double conversion.
2. Performs a double division.
3. Calls the function, passing in the double result obtained in #2.
4. Performs one double to int conversion, on the result returned by the function.
5. Stores the integer result obtained in #4 into the destination variable.

Now, let’s say our target architecture doesn’t have any hardware floating-point support, or it has floating-point support but the operations are too slow. For example, we might be targeting a microcontroller, and all floating-point support is provided in software. In this situation, we’d like to stick with using only integers and integer operations, and avoid all conversions to or from floating-point types. Integer operations are available and perform well. Floating-point operations…not so much.

Consider the following statement:

int z = x / y + (x % y != 0); // ceiling of x / y

In this statement, we remain entirely in the realm of integers. The initial division gets us part of the way. The rest of the expression, using the modulus operator to get the remainder and comparing that remainder to 0, will either add 1 or 0 to the result of the division. This code effectively performs an integer ceiling on the value x / y, without using any floating-point instructions, conversions, or functions.

Our initial reaction might be, “Wait! We’re performing the division operation twice: once for the division operator and once for the modulus operator.” On the surface, that’s what it looks like. But a decent optimizing C compiler (with appropriate optimizations enabled, of course), will recognize we’re using the same operands for both operators, and will generate code to perform the integer division just once, making use of the integer quotient and integer remainder from that one division operation. (This behavior assumes that the machine language integer division instruction yields both the quotient and the remainder, which is very common across many architectures.) So, if you look at the generated machine code, you’ll very likely see one integer division, followed by the use of both the quotient and the remainder, yielded by that division. This line effectively:

1. Performs an integer division, yielding both a quotient and a remainder.
2. Performs an integer comparison.
3. Performs an integer addition (of either 0 or 1).
4. Stores the integer result into the destination variable.

Fewer steps, yes. But the important thing is that all operations are now integer operations. Floating-point is nowhere to be seen.

Could we turn this into a function? Sure. To be consistent, we could name it ceili, receiving in this case two int arguments, and returning an int result:

int ceili(int numerator, int denominator)
{
    return (numerator / denominator + (numerator % denominator != 0));
}

Of course, if the second argument is zero, we’ll be in big trouble. Adding argument verification might be appropriate here, if we’re willing to pay for the additional cost of checking.

We would incur the function call overhead as well, if the compiler can’t or won’t inline the function. Defining a macro is an option, such as:

#define CEILI(numerator,denominator)  ((numerator)/(denominator)+((numerator)%(denominator)!= 0))

but suffers from the danger of problems caused by macro argument expressions with side effects being evaluated more than once. And a macro won’t give us the benefit of any type checking.

There are other approaches available to achieve the same thing, some suffering from potential integer overflows and other potential issues.

Whatever approach you choose, be sure the code is readable and maintainable.