Rounding integer division (instead of truncating)

c math int rounding integer-division

177,518

Solution 1

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;
}

Solution 2

The standard idiom for integer rounding up is:

int a = (59 + (4 - 1)) / 4;

You add the divisor minus one to the dividend.

Solution 3

A code that works for any sign in dividend and divisor:

int divRoundClosest(const int n, const int d)
{
  return ((n < 0) ^ (d < 0)) ? ((n - d/2)/d) : ((n + d/2)/d);
}

In response to a comment "Why is this actually working?", we can break this apart. First, observe that n/d would be the quotient, but it is truncated towards zero, not rounded. You get a rounded result if you add half of the denominator to the numerator before dividing, but only if numerator and denominator have the same sign. If the signs differ, you must subtract half of the denominator before dividing. Putting all that together:

(n < 0) is false (zero) if n is non-negative
(d < 0) is false (zero) if d is non-negative
((n < 0) ^ (d < 0)) is true if n and d have opposite signs
(n + d/2)/d is the rounded quotient when n and d have the same sign
(n - d/2)/d is the rounded quotient when n and d have opposite signs

If you prefer a macro:

#define DIV_ROUND_CLOSEST(n, d) ((((n) < 0) ^ ((d) < 0)) ? (((n) - (d)/2)/(d)) : (((n) + (d)/2)/(d)))

The linux kernel macro DIV_ROUND_CLOSEST doesn't work for negative divisors!

Solution 4

You should instead use something like this:

int a = (59 - 1)/ 4 + 1;

I assume that you are really trying to do something more general:

int divide(x, y)
{
   int a = (x -1)/y +1;

   return a;
}

x + (y-1) has the potential to overflow giving the incorrect result; whereas, x - 1 will only underflow if x = min_int...

Solution 5

(Edited) Rounding integers with floating point is the easiest solution to this problem; however, depending on the problem set is may be possible. For example, in embedded systems the floating point solution may be too costly.

Doing this using integer math turns out to be kind of hard and a little unintuitive. The first posted solution worked okay for the the problem I had used it for but after characterizing the results over the range of integers it turned out to be very bad in general. Looking through several books on bit twiddling and embedded math return few results. A couple of notes. First, I only tested for positive integers, my work does not involve negative numerators or denominators. Second, and exhaustive test of 32 bit integers is computational prohibitive so I started with 8 bit integers and then mades sure that I got similar results with 16 bit integers.

I started with the 2 solutions that I had previously proposed:

#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)

#define DIVIDE_WITH_ROUND(N, D) (N == 0) ? 0:(N - D/2)/D + 1;

My thought was that the first version would overflow with big numbers and the second underflow with small numbers. I did not take 2 things into consideration. 1.) the 2nd problem is actually recursive since to get the correct answer you have to properly round D/2. 2.) In the first case you often overflow and then underflow, the two canceling each other out. Here is an error plot of the two (incorrect) algorithms:

This plot shows that the first algorithm is only incorrect for small denominators (0 < d < 10). Unexpectedly it actually handles large numerators better than the 2nd version.

Here is a plot of the 2nd algorithm:

As expected it fails for small numerators but also fails for more large numerators than the 1st version.

Clearly this is the better starting point for a correct version:

#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)

If your denominators is > 10 then this will work correctly.

A special case is needed for D == 1, simply return N. A special case is needed for D== 2, = N/2 + (N & 1) // Round up if odd.

D >= 3 also has problems once N gets big enough. It turns out that larger denominators only have problems with larger numerators. For 8 bit signed number the problem points are

if (D == 3) && (N > 75)) else if ((D == 4) && (N > 100)) else if ((D == 5) && (N > 125)) else if ((D == 6) && (N > 150)) else if ((D == 7) && (N > 175)) else if ((D == 8) && (N > 200)) else if ((D == 9) && (N > 225)) else if ((D == 10) && (N > 250))

(return D/N for these)

So in general the the pointe where a particular numerator gets bad is somewhere around
N > (MAX_INT - 5) * D/10

This is not exact but close. When working with 16 bit or bigger numbers the error < 1% if you just do a C divide (truncation) for these cases.

For 16 bit signed numbers the tests would be

if ((D == 3) && (N >= 9829)) else if ((D == 4) && (N >= 13106)) else if ((D == 5) && (N >= 16382)) else if ((D == 6) && (N >= 19658)) else if ((D == 7) && (N >= 22935)) else if ((D == 8) && (N >= 26211)) else if ((D == 9) && (N >= 29487)) else if ((D == 10) && (N >= 32763))

Of course for unsigned integers MAX_INT would be replaced with MAX_UINT. I am sure there is an exact formula for determining the largest N that will work for a particular D and number of bits but I don't have any more time to work on this problem...

(I seem to be missing this graph at the moment, I will edit and add later.) This is a graph of the 8 bit version with the special cases noted above:![8 bit signed with special cases for 0 < N <= 10 3

Note that for 8 bit the error is 10% or less for all errors in the graph, 16 bit is < 0.1%.

View more solutions

177,518

Author by

Admin

Updated on January 21, 2022

Comments

Admin over 2 years
I was curious to know how I can round a number to the nearest whole number. For instance, if I had:
```
int a = 59 / 4;
```
which would be 14.75 if calculated in floating point; how can I store the result as 15 in "a"?
visual_learner about 14 years

What if you want to perform a mathematical round (14.75 to 15, 14.25 to 14)?
Jonathan Leffler about 14 years

Ugh...then you have to think...add (n - 1) / 2, more or less. For n == 4, you want x % n ∈ { 0, 1 } to round down, and x % n ∈ { 2, 3 } to round up. So, you need to add 2, which is n / 2. For n == 5, you want x % n ∈ { 0, 1, 2 } to round down, and x % n ∈ { 3, 4 } to round up, so you need to add 2 again...hence: int i = (x + (n / 2)) / n;?
Yousf about 14 years

Note that this is FLOATING pointer solution. I recommend that you use integer operation for many reasons.
0xC0DEFACE about 14 years

What problems? I've used this before and have never encountered a problem.
caf over 12 years

This does not work correctly for negative numbers - consider divide(-59, 4).
caf over 12 years

What about negative x and/or n?
Jonathan Leffler over 12 years

@caf: work it out for yourself. Hint: int abs(int n); (from Standard C) and int signum(int n) { return (n < 0) ? -1 : (n > 0) ? +1 : 0; } might come in handy.
caf over 12 years

@JonathanLeffler: Right, but it's starting to get surprisingly non-trivial - more so again if you also want to handle the case where x + n / 2 overflows...
Michael Dorgan over 12 years

Because on systems without a FPU, this makes really, really, bad code.
0xC0DEFACE over 12 years

That makes perfect sense, however should this even compile for a target that cant support floating point?
Sean Middleditch about 12 years

that's the problem. the OP's question is solvable without using any floating point at all, and so will not be dependent on FPU support being present or being good. also, faster (in the event that lots of these need to be calculated) on most architectures, including those with otherwise fantastic FPU support. also note that your solution could be problematic for larger numbers where floats cannot accurately represent the integer values given.
nad2000 over 11 years

61.0 / 30.0 = 2.03333(3). So round up should be 2, but (61-1)/30+1=3
Gurgeh over 11 years

@nad2000 why would 2.0333.. rounded up be 2?
Andrew about 11 years

Your parentheses are making me dizzy.
David about 11 years

This does not work if x = 0. The intended result of x/y rounding up if x = 0 is 0. Yet this solution yields a result of 1. The other solution comes up with the correct answer.
chux - Reinstate Monica almost 11 years

This method works for positive int. But if the divisor or dividend is negative it produces an incorrect answer. The hint to @caf does not work either.
Adrian McCarthy almost 11 years

-1, this gives the wrong answer for many values when sizeof(int) >= sizeof(float). For example, a 32-bit float uses some bits to represent the exponent, and thus it cannot exactly represent every 32-bit int. So 12584491 / 3 = 4194830.333..., which should round down to 4194830, but, on my machine which cannot represent 12584491 exactly in a float, the above formula rounds up to 4194831, which is wrong. Using double is safer.
Adrian McCarthy almost 11 years

The (original) title and the question asked for two different things. The title said rounding up (which is what you've answered), but the body says round to nearest (which is what the accepted answer attempts).
Justin almost 11 years

Sure, it looks like a bad case of LISP, but omitting the parentheses around each argument and then evaluating ABS(4 & -1) is worse.
chux - Reinstate Monica over 10 years

Is typeof() part of C or a compiler specific extension?
chux - Reinstate Monica over 10 years

A typical float (IEEE) limits the useful range of this solution to abs(a/b) < 16,777,216.
chux - Reinstate Monica over 10 years

Aside from int values near min/max int, this is the best solution so far.
Cornstalks over 10 years

@chux: It's a GCC extension. It's not a part of standard C.
WayneJ over 10 years

Actually, this answer is not correct at all. It works for a few numbers but fails on quite a few. See my better (I hope) answer later on in the thread.
Brent Bradburn about 10 years

As noted by @caf in a comment to another answer, overflow is a risk with this approach to rounding (since it modifies the numerator prior to the division), so this function isn't appropriate if you are pushing the range limits of int.
Groo almost 10 years

This doesn't make sense. Your float solution is rounding the number to its nearest integer, while the second one is returning the ceiling.
0xC0DEFACE almost 10 years

Ah Sorry. I adjusted the implementation to also round rather than ceil
Oleg Vazhnev over 9 years

this doesn't work at all for negative numbers, try std::cout << "exact: " << (-8.0f / 2.0f) << std::endl; and std::cout << "rounded: " << (int) (-8.0f / 2.0f + 0.5f) << std::endl;. first -4 and rounded is -3. for negative you should -0.5 instead of 0.5
0xC0DEFACE over 9 years

@javapowered, yes. That's why the function only operates on unsigned ints.
Peter Cordes over 9 years

neat way to check for signed vs. unsigned args in a macro, so unsigned args can leave out the branch and extra instructions entirely.
Peter Cordes over 9 years

see @PauliusZ's answer for Linux's DIV_ROUND_CLOSEST macro, which uses GNU C typeof() to be safe with inputs like i++, and will work right for negative numbers when used with signed operands.
Brent Bradburn about 9 years

By the way, if you happen to be dividing by a power of two (which also implies a positive divisor), you can take advantage of the fact that signed-shift-right has the effect of division with round-towards-negative infinity (unlike the division operator which rounds towards zero) to avoid the use of any conditional logic. So the formula becomes return (n+(1<<shift>>1))>>shift;, which simplifies to the form (n+C)>>shift (where C=(1<<shift>>1) if shift happens to be a constant.
Doug McClean over 8 years

Doesn't this round up too often when the divisor is anything other than 2?
Brent Bradburn about 8 years

The "mid-value bias" concern only relates to the case of exactly 0.5 between integers, so is esoteric to be sure. For some kind of graphical representation, for example, you might want to see continuity around zero rather than symmetry.
phuclv about 8 years

this is always rounding up like ceil function, not a proper rounding
phuclv about 8 years

He want's ROUND, not CEIL
KrisWebDev about 8 years

Just beware that c = (INT_MAX + (4 - 1)) / 4; gives c = -536870911 due to integer overflow...
chux - Reinstate Monica about 8 years

Do not see a need for if(denominator == 1) return numerator;. What is its purpose?
Malcolm McLean about 7 years

Really the question is why you want to represent values like this as an integer type. double holds perfect integers up to 2^53 and allows you to easily specify how errors will be rounded.
Ciro Santilli OurBigBook.com about 7 years

Or maybe lround.
WayneJ over 6 years

You are correct. The first macro was incorrect (I found this out the hard way.) This turned out to be harder that I expected. I updated the post acknowledging the incorrectness and include some further discussion.
phuclv about 5 years

this is the worst solution. Doing 2 slow divisions are not people want to do. And b can be obtained by truncating a instead of doing another division
phuclv about 5 years

the & in ((a ^ b) & 0x80000000) >> 31; is redundant, since the low bits will be thrown away after the shift anyway
Tobias Marschall almost 5 years

Why is this actually working? What´s the mathematical concept behind this?
user3607601 almost 5 years

It should be noted that this is a rearrangement of some mathematics which intends to add 0.5 to the numerator. This has the effect of forcing any number that has a decimal part of 0.5 or greater, to instead have an integer part made 1 greater than it previously was. Adding denominator/2 to the numerator, results in 0.5 being added to the calculated number. This works also, for negative numbers as the denominators negative sign is cancelled upon division by itself.
Andrew Falanga almost 5 years

@MalcolmMcLean I cannot speak to all cases, but there are environments which do now permit floating point operations. It is entirely impossible when programming in UEFI and difficult (to potentially unrecommended) in the Linux Kernel
Kami Kaze almost 5 years

If this answer is qrong why wouldn't you just delete it?
Gabriel Staples over 4 years

Your edit nails it! However, I prefer the macro or gcc statement expression type-free form of integer division with rounding, so I wrote it up and described it in detail here: stackoverflow.com/questions/2422712/…
VLL about 4 years

@TobiasMarschall This is equivalent to floor(n / d + 0.5), where n and d are floats.
chqrlie about 4 years

Definitely TLDR
Gabriel Staples about 4 years

Copy the code chunks. Delete all the comments. Each of the 3 approaches is like 1 to 4 lines. The details of what's really happening and how it works merit the verbose explanations as a teaching platform, however.
chqrlie about 4 years

int sgn = n >> (sizeof(n)*8-1); // 0 or -1: NO, the behavior is not defined by the C Standard. You should use int sgn = ~(n < 0);
Gabriel Staples about 4 years

This answer's short. You wanna see a long one? stackoverflow.com/questions/44034633/…
chqrlie about 4 years

The short answer is flawed: ROUND_DIVIDE(-3 , 4) evaluates to 0, which is not the nearest whole integer. The lengthy explanations do not address this problem at all. (int)round(-3.0 / 4.0) would evaluate to -1.
Gabriel Staples about 4 years

I'll fix it when I get the chance (within the next 48 hrs or so). I've been using these for years but just on positive numbers. It just requires switching the addition to subtraction if either the numerator or denominator, but not both, is negative.
Gabriel Staples about 4 years

And if I stated that wrong I'll figure it out when I go to fix it. It's super late. I'll add negative numbers to my test cases too.
DosMan about 4 years

My concern is about speed and size for an ARM microcontroller. The expression ~(n < 0) generates one more instruction. Besides, the original expression will work on any architecture using 8-bit bytes and two's complement, which I think describes all modern machines.
Gabriel Staples about 4 years

I haven't forgotten about this. My hunch was correct about swapping addition for subtraction under certain cases, requiring a logical XOR based on the negativity of each input. I'm in the process of rewriting this answer completely on my local computer first, fixing it to handle negative numbers, & also adding macros to round down and round up. When done, I'll have something like DIVIDE_ROUNDUP(), DIVIDE_ROUNDDOWN(), and DIVIDE_ROUNDNEAREST(), all of which will handle both positive and negative integer inputs. Hopefully then I'll win your upvote. I certainly will be using these myself.
Gabriel Staples about 4 years

Ok I've got all the code and unit tests done and it works perfectly! I've done all 3 functions I mention in the previous comment using macros, gcc/clang statement expresions, and C++ function templates, and it all works. I've run dozens of tests with both positive and negative inputs. Run it for yourself here: github.com/ElectricRCAircraftGuy/eRCaGuy_hello_world/tree/…. See the .cpp file. Run the .sh file to see the test output, or just look at the .txt file which contains sample output from when I ran it. Next I just need to update my answer here.
Jan Schultke almost 3 years

The code in the edit doesn't work. divRoundClosest(1, 5) is equal to 1.
ericbn almost 3 years

Hi @Michael. Maybe you should move the EDIT you added here to a separate answer, so comments regarding that specific code can be discussed separately.
gg99 about 2 years

That's typically the kind of function that begs for constexpr-ness. And that would remove the need for a macro version.
Cris Luengo about 2 years

I've rolled back @Micheal's answer because it doesn't work. For that version, divRoundClosest(1, 5) results in 1, as mentioned above, and even divRoundClosest(0, 5) results in 1!