Rounding integer division instead of truncating

Question

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

User · Answer

Some alternatives for division by 4  return x 4    x 2   2   return x 4    x   4  gt   2    Or in general  division by any power of 2  return x y   x  y 2    2        or return  x  gt  gt  i      x  gt  gt  i - 1   amp  1       with y   2 i   It works by rounding up if the fractional part   0 5  i e  the first digit   base 2  In binary it s equivalent to adding the first fractional bit to the result  This method has an advantage in architectures with a flag register  because the carry flag will contain the last bit that was shifted out  For example on x86 it can be optimized into  shr eax  i adc eax  0   It s also easily extended to support signed integers  Notice that the expression for negative numbers is   x - 1  y     x - 1   y 2   amp  1    we can make it work for both positive and negative values with  int t   x    x  gt  gt  31   return  t  gt  gt  i      t  gt  gt  i - 1   amp  1

User · Answer

I ran into the same difficulty  The code below should work for positive integers   I haven t compiled it yet but I tested the algorithm on a google spreadsheet  I know  wtf  and it was working   unsigned int integer div round nearest unsigned int numerator  unsigned int denominator        unsigned int rem      unsigned int floor      unsigned int denom div 2          check error cases     if denominator    0          return 0       if denominator    1          return numerator          Compute integer division and remainder     floor   numerator denominator      rem   numerator denominator          Get the rounded value of the denominator divided by two     denom div 2   denominator 2      if denominator 2          denom div 2            If the remainder is bigger than half of the denominator  adjust value     if rem  gt   denom div 2          return floor 1      else         return floor

User · Answer

TLDR  Here s a macro  use it      To do  numer denom   rounded to the nearest whole integer  use   define ROUND DIVIDE numer  denom     numer     denom    2     denom     Usage example   int num   ROUND DIVIDE 13 7      13 7   1 857 -- gt  rounds to 2  so num is 2   Full answer   Some of these answers are crazy looking  Codeface nailed it though   See  0xC0DEFACE s answer here   I really like the type-free macro or gcc statement expression form over the function form  however  so  I wrote this answer with a detailed explanation of what I m doing  ie  why this mathematically works  and put it into 2 forms   1  Macro form  with detailed commentary to explain the whole thing        brief      ROUND DIVIDE numerator denominator   round to the nearest whole integer when doing                   integer  division only      details    This works on  integers only  since it assumes integer truncation will take place automatically                 during the division        notes      The concept is this  add 1 2 to any number to get it to round to the nearest whole integer                 after integer trunction                  Examples   2 74   0 5   3 24 -- gt  3 when truncated                            2 99   0 5   3 49 -- gt  3 when truncated                            2 50   0 5   3 00 -- gt  3 when truncated                            2 49   0 5   2 99 -- gt  2 when truncated                            2 00   0 5   2 50 -- gt  2 when truncated                            1 75   0 5   2 25 -- gt  2 when truncated                 To add 1 2 in integer terms  you must do it  before  the division  This is achieved by                  adding 1 2 denominator  which is  denominator 2   to the numerator before the division                  ie   rounded division    numer   denom 2  denom                     Proof    1 2 is the same as  denom 2  denom  Therefore   numer denom    1 2 becomes                   numer denom     denom 2  denom  They have a common denominator  so combine terms and you get                   numer   denom 2  denom  which is the answer above       param in   numerator   any integer type numerator  ex  uint8 t  uint16 t  uint32 t  int8 t  int16 t  int32 t  etc      param in   denominator any integer type denominator  ex  uint8 t  uint16 t  uint32 t  int8 t  int16 t  int32 t  etc      return     The result of the  numerator denominator  division rounded to the nearest  whole integer    define ROUND DIVIDE numerator  denominator     numerator     denominator    2     denominator     2  GCC Statement Expression form   See a little more on gcc statement expressions here        brief       gcc statement expression  form of the above macro  define ROUND DIVIDE2 numerator  denominator                                                                                      typeof    numerator  numerator     numerator                  typeof    denominator  denominator     denominator          numerator     denominator    2    denominator                  3  C   Function Template form    Added Mar  Apr  2020    include  lt limits gt      Template form for C    with type checking to ensure only integer types are passed in   template  lt typename T gt  T round division T numerator  T denominator           Ensure only integer types are passed in  as this round division technique does NOT work on        floating point types since it assumes integer truncation will take place automatically        during the division         - The following static assert allows all integer types  including their various  const             volatile   and  const volatile  variations  but prohibits any floating point type          such as  float    double   and  long double           - Reference page  https   en cppreference com w cpp types numeric limits is integer     static assert std  numeric limits lt T gt   is integer   Only integer types are allowed         return  numerator   denominator 2  denominator      Run  amp  test some of this code here    OnlineGDB  integer rounding during division   Related Answers    Fixed Point Arithmetic in C Programming - in this answer I go over how to do integer rounding to the nearest whole integer  then tenth place  1 decimal digit to the right of the decimal   hundredth place  2 dec digits   thousandth place  3 dec digits   etc  Search the answer for the section in my code comments called BASE 2 CONCEPT  for more details  A related answer of mine on gcc s statement expressions  MIN and MAX in C The function form of this with fixed types  Rounding integer division  instead of truncating  What is the behavior of integer division  For rounding up instead of to nearest integer  follow this similar pattern  Rounding integer division  instead of truncating    References    https   www tutorialspoint com cplusplus cpp templates htm   todo  test this for negative inputs  amp  update this answer if it works     define ROUND DIVIDE numer  denom    numer  lt  0      denom  lt  0      numer  -  denom    2     denom      numer     denom    2     denom

User · Answer

As written  you re performing integer arithmetic  which automatically just truncates any decimal results  To perform floating point arithmetic  either change the constants to be floating point values   int a   round 59 0   4     Or cast them to a float or other floating point type   int a   round  float 59   4     Either way  you need to do the final rounding with the round   function in the math h header  so be sure to  include  lt math h gt  and use a C99 compatible compiler

User · Answer

Borrowing from  ericbn I prefere defines like   define DIV ROUND INT n d      n   lt  0      d   lt  0        n  -  d  2   d        n     d  2   d    or if you work only with unsigned ints  define DIV ROUND UINT n d      n     d  2   d

User · Answer

Here s my solution  I like it because I find it more readable and because it has no branching  neither ifs nor ternaries    int32 t divide int32 t a  int32 t b      int32 t resultIsNegative     a   b   amp  0x80000000   gt  gt  31    int32 t sign   resultIsNegative -2 1    return  a    b   2   sign     b      Full test program that illustrates intended behaviour    include  lt stdint h gt   include  lt assert h gt   int32 t divide int32 t a  int32 t b      int32 t resultIsNegative     a   b   amp  0x80000000   gt  gt  31    int32 t sign   resultIsNegative -2 1    return  a    b   2   sign     b     int main       assert divide 0  3     0      assert divide 1  3     0     assert divide 5  3     2      assert divide -1  3     0     assert divide -5  3     -2      assert divide 1  -3     0     assert divide 5  -3     -2      assert divide -1  -3     0     assert divide -5  -3     2

User · Answer

try using math ceil function that makes rounding up  Math Ceil

User · Answer

For some algorithms you need a consistent bias when  nearest  is a tie      round-to-nearest with mid-value bias towards positive infinity int div nearest  int n  int d           if  d lt 0  n  -1  d  -1     return  abs n    d- n lt 0 1 0   gt  gt 1   d     n lt 0  -1  1          This works regardless of the sign of the numerator or denominator     If you want to match the results of round N  double D   floating-point division and rounding   here are a few variations that all produce the same results   int div nearest  int n  int d           int r  n lt 0 -1  1   abs d  gt  gt 1      eliminates a division    int r   n lt 0   d lt 0  -1  1   d 2      basically the same as  ericbn    int r  n d lt 0 -1  1   d 2      small variation from  ericbn    return  n r  d         Note  The relative speed of  abs d  gt  gt 1  vs   d 2  is likely to be platform dependent

User · Answer

The standard idiom for integer rounding up is   int a    59    4 - 1     4    You add the divisor minus one to the dividend

User · Answer

double a 59 0 4  int b 59 4  if a-b gt  0 5       b      printf   d  b      let exact float value of 59 0 4 be x here it is 14 750000  let smallest integer less than x be y here it is 14  if x-y lt 0 5 then y is the solution else y 1 is the solution

User · Answer

Safer C code  unless you have other methods of handling  0    return   divisor  gt  0       dividend     divisor - 1      divisor     dividend   This doesn t handle the problems that occur from having an incorrect return value as a result of your invalid input data  of course

User · Answer

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   lt  d   lt  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  amp  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   amp  amp   N  gt  75     else if   D    4   amp  amp   N  gt  100     else if   D    5   amp  amp   N  gt  125     else if   D    6   amp  amp   N  gt  150     else if   D    7   amp  amp   N  gt  175     else if   D    8   amp  amp   N  gt  200     else if   D    9   amp  amp   N  gt  225     else if   D    10   amp  amp   N  gt  250       return D N for these   So in general the the pointe where a particular numerator gets bad is somewhere around N  gt   MAX INT - 5    D 10   This is not exact but close  When working with 16 bit or bigger numbers the error  lt  1  if you just do a C divide  truncation  for these cases   For 16 bit signed numbers the tests would be  if   D    3   amp  amp   N  gt    9829   else if   D    4   amp  amp   N  gt   13106   else if   D    5   amp  amp   N  gt   16382   else if   D    6   amp  amp   N  gt   19658   else if   D    7   amp  amp   N  gt   22935   else if   D    8   amp  amp   N  gt   26211   else if   D    9   amp  amp   N  gt   29487   else if   D    10   amp  amp   N  gt   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  lt  N  lt   10 3  Note that for 8 bit the error is 10  or less for all errors in the graph  16 bit is  lt  0 1

User · Answer

int a  b  int c   a   b  if a   b    c        Checking if there is a remainder allows you to manually roundup the quotient of integer division

User · Answer

The following correctly rounds the quotient to the nearest integer for both positive and negative operands WITHOUT floating point or conditional branches  see assembly output below   Assumes N-bit 2 s complement integers    define ASR x    x   lt  0   -1   0      Compiles into a  N-1 -bit arithmetic shift right  define ROUNDING x y     y  2 -  ASR  x   y    amp   y     int RoundedQuotient int x  int y          return  x   ROUNDING x y     y          The value of ROUNDING will have the same sign as the dividend  x  and half the magnitude of the divisor  y   Adding ROUNDING to the dividend thus increases its magnitude before the integer division truncates the resulting quotient  Here s the output of the gcc compiler with -O3 optimization for a 32-bit ARM Cortex-M4 processor   RoundedQuotient                    Input parameters  r0   x  r1   y     eor     r2  r1  r0             r2   x y     and     r2  r1  r2  asr  31    r2   ASR x y   amp  y     add     r3  r1  r1  lsr  31    r3    y  lt  0    y   1   y     rsb     r3  r2  r3  asr  1     r3   y 2 -  ASR x y   amp  y      add     r0  r0  r3             r0   x    y 2 -  ASR x y   amp  y      sdiv    r0  r0  r1             r0    x   ROUNDING x y     y     bx      lr                     Returns r0   rounded quotient

User · Answer

From Linux kernel  GPLv2          Divide positive or negative dividend by positive divisor and round    to closest integer  Result is undefined for negative divisors and    for negative dividends if the divisor variable type is unsigned       define DIV ROUND CLOSEST x  divisor                                                typeof x    x   x                     typeof divisor    d   divisor                    typeof x  -1   gt  0                         typeof divisor  -1   gt  0       x   gt  0                    x        d    2        d                      x  -     d    2        d

User · Answer

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

User · Answer

A code that works for any sign in dividend and divisor   int divRoundClosest const int n  const int d      return   n  lt  0     d  lt  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  lt  0  is false  zero  if n is non-negative  d  lt  0  is false  zero  if d is non-negative   n  lt  0     d  lt  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   lt  0      d   lt  0        n  -  d  2   d        n     d  2   d      The linux kernel macro DIV ROUND CLOSEST doesn t work for negative divisors   EDIT  This will work without overflow   int divRoundClosest  int A  int B     if A lt 0      if B lt 0          return  A    -B 1  2    B   1      else         return  A     B 1  2    B - 1  else     if B lt 0          return  A -  -B 1  2    B - 1      else         return  A -   B 1  2    B   1

User · Answer

int divide x y    int quotient   x y   int remainder   x y   if remainder  0    return quotient   int tempY   divide y 2    if remainder gt  tempY    quotient     return quotient      eg 59 4 Quotient   14  tempY   2  remainder   3  remainder    tempY hence quotient   15

User · Answer

If you re dividing positive integers you can shift it up  do the division and then check the bit to the right of the real b0  In other words  100 8 is 12 5 but would return 12  If you do  100 lt  lt 1  8  you can check b0 and then round up after you shift the result back down

User · Answer

define CEIL a  b     a     b        a     b    gt  0   1   0     Another useful MACROS  MUST HAVE     define MIN a  b      a   lt   b      a     b    define MAX a  b      a   gt   b      a     b    define ABS a         a   lt  0    - a     a

User · Answer

The fundamental rounding divide algorithm  as presented by previous contributors  is to add half the denominator to the numerator before division  This is simple when the inputs are unsigned  not quite so when signed values are involved  Here are some solutions that generate optimal code by GCC for ARM  thumb-2    Signed   Unsigned  inline int DivIntByUintRnd int n  uint d                int sgn   n  gt  gt   sizeof n  8-1      0 or -1     return  n    int    d   2    sgn  - sgn      int d       The first code line replicates the numerator sign bit through an entire word  creating zero  positive  or -1  negative   On the second line  this value  if negative  is used to negate the rounding term using 2 s complement negation  complement and increment  Previous answers used a conditional statement or multiply to achieve this   Signed   Signed  inline int DivIntRnd int n  int d               int rnd   d   2      return  n     n   d   lt  0   -rnd   rnd     d       I found I got the shortest code with the conditional expression  but only if I helped the compiler by computing the rounding value d 2  Using 2 s complement negation is close   inline int DivIntRnd int n  int d               int sgn    n   d   gt  gt   sizeof n  8-1        0 or -1     return  n     d   sgn  - sgn    2    d       Division by Powers of 2  While integer division truncates toward zero  shifting truncates toward negative infinity  This makes a rounding shift much simpler  as you always add the rounding value regardless of the sign of the numerator   inline int ShiftIntRnd int n  int s           return   n  gt  gt   s - 1     1   gt  gt  1    inline uint ShiftUintRnd uint n  int s        return   n  gt  gt   s - 1     1   gt  gt  1      The expression is the same  generating different code based on type   so a macro or overloaded function could work for both   The traditional method  the way rounding division works  would be to add half the divisor  1  lt  lt   s-1   Instead we shift one less  add one  and then do the final shift  This saves creating a non-trivial value  even if constant  and the machine register to put it in

User · Answer

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

[c] Rounding integer division (instead of truncating)

Examples related to c

Examples related to math

Examples related to int

Examples related to rounding

Examples related to integer-division