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

The Question :

273 people think this question is useful

Given integer values x and y, C and C++ both return as the quotient q = x/y the floor of the floating point equivalent. I’m interested in a method of returning the ceiling instead. For example, ceil(10/5)=2 and ceil(11/5)=3.

The obvious approach involves something like:

q = x / y;
if (q * y < x) ++q;

This requires an extra comparison and multiplication; and other methods I’ve seen (used in fact) involve casting as a float or double. Is there a more direct method that avoids the additional multiplication (or a second division) and branch, and that also avoids casting as a floating point number?

The Question Comments :
  • the divide instruction often returns both quotient and remainder at the same time so there’s no need to multiply, just q = x/y + (x % y != 0); is enough
  • @LưuVĩnhPhúc that comment should be the accepted answer, imo.
  • @LưuVĩnhPhúc Seriously you need to add that as the answer. I just used that for my answer during a codility test. It worked like a charm though I am not certain how the mod part of the answer works but it did the job.
  • @AndreasGrapentin the answer below by Miguel Figueiredo was submitted nearly a year before Lưu Vĩnh Phúc left the comment above. While I understand how appealing and elegant Miguel’s solution is, I’m not inclined to change the accepted answer at this late date. Both approaches remain sound. If you feel strongly enough about it, I suggest you show your support by up-voting Miguel’s answer below.
  • Strange, I have not seen any sane measurement or analysis of the proposed solutions. You talk about speed on near-the-bone, but there is no discussion of architectures, pipelines, branching instructions and clock cycles.

The Answer 1

413 people think this answer is useful

For positive numbers

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

The Answer 2

89 people think this answer is useful

For positive numbers:

    q = x/y + (x % y != 0);

The Answer 3

59 people think this answer is useful

Sparky’s answer is one standard way to solve this problem, but as I also wrote in my comment, you run the risk of overflows. This can be solved by using a wider type, but what if you want to divide long longs?

Nathan Ernst’s answer provides one solution, but it involves a function call, a variable declaration and a conditional, which makes it no shorter than the OPs code and probably even slower, because it is harder to optimize.

My solution is this:

q = (x % y) ? x / y + 1 : x / y;

It will be slightly faster than the OPs code, because the modulo and the division is performed using the same instruction on the processor, because the compiler can see that they are equivalent. At least gcc 4.4.1 performs this optimization with -O2 flag on x86.

In theory the compiler might inline the function call in Nathan Ernst’s code and emit the same thing, but gcc didn’t do that when I tested it. This might be because it would tie the compiled code to a single version of the standard library.

As a final note, none of this matters on a modern machine, except if you are in an extremely tight loop and all your data is in registers or the L1-cache. Otherwise all of these solutions will be equally fast, except for possibly Nathan Ernst’s, which might be significantly slower if the function has to be fetched from main memory.

The Answer 4

19 people think this answer is useful

You could use the div function in cstdlib to get the quotient & remainder in a single call and then handle the ceiling separately, like in the below

#include <cstdlib>
#include <iostream>

int div_ceil(int numerator, int denominator)
{
        std::div_t res = std::div(numerator, denominator);
        return res.rem ? (res.quot + 1) : res.quot;
}

int main(int, const char**)
{
        std::cout << "10 / 5 = " << div_ceil(10, 5) << std::endl;
        std::cout << "11 / 5 = " << div_ceil(11, 5) << std::endl;

        return 0;
}

The Answer 5

12 people think this answer is useful

How about this? (requires y non-negative, so don’t use this in the rare case where y is a variable with no non-negativity guarantee)

q = (x > 0)? 1 + (x - 1)/y: (x / y);

I reduced y/y to one, eliminating the term x + y - 1 and with it any chance of overflow.

I avoid x - 1 wrapping around when x is an unsigned type and contains zero.

For signed x, negative and zero still combine into a single case.

Probably not a huge benefit on a modern general-purpose CPU, but this would be far faster in an embedded system than any of the other correct answers.

The Answer 6

8 people think this answer is useful

There’s a solution for both positive and negative x but only for positive y with just 1 division and without branches:

int ceil(int x, int y) {
    return x / y + (x % y > 0);
}

Note, if x is positive then division is towards zero, and we should add 1 if reminder is not zero.

If x is negative then division is towards zero, that’s what we need, and we will not add anything because x % y is not positive

The Answer 7

5 people think this answer is useful

I would have rather commented but I don’t have a high enough rep.

As far as I am aware, for positive arguments and a divisor which is a power of 2, this is the fastest way (tested in CUDA):

//example y=8
q = (x >> 3) + !!(x &amp; 7);

For generic positive arguments only, I tend to do it like so:

q = x/y + !!(x % y);

The Answer 8

3 people think this answer is useful

This works for positive or negative numbers:

q = x / y + ((x % y != 0) ? !((x > 0) ^ (y > 0)) : 0);

If there is a remainder, checks to see if x and y are of the same sign and adds 1 accordingly.

The Answer 9

2 people think this answer is useful

simplified generic form,

int div_up(int n, int d) {
    return n / d + (((n < 0) ^ (d > 0)) &amp;&amp; (n % d));
} //i.e. +1 iff (not exact int &amp;&amp; positive result)

For a more generic answer, C++ functions for integer division with well defined rounding strategy

The Answer 10

-2 people think this answer is useful

Compile with O3, The compiler performs optimization well.

q = x / y;
if (x % y)  ++q;

Add a Comment