patterncppCritical
Fast ceiling of an integer division in C / C++
Viewed 0 times
divisionfastintegerceiling
Problem
Given integer values
The obvious approach involves something like:
This requires an extra comparison and multiplication; and other methods I've seen (used in fact) involve casting as a
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?Solution
For positive numbers where you want to find the ceiling (q) of x when divided by y.
To round up ...
or (avoiding overflow in x+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 != 0Code Snippets
unsigned int x, y, q;q = (x + y - 1) / y;q = 1 + ((x - 1) / y); // if x != 0Context
Stack Overflow Q#2745074, score: 559
Revisions (0)
No revisions yet.