C++ currently offers only truncating integer division. As a consequence, the remainder operator's sign is same as the sign of the dividend. Alternative rounding modes and remainder sign behaviour are useful.
This proposal adds an <intdiv> header containing free functions for obtaining the quotient and remainder for different rounding modes, such as rounding towards the nearest integer, towards the infinities, etc.
Alternative rounding modes are frequently required to solve different problems with division. The user has to implement these modes by hand, and naive implementations (e.g.[1][2]) suffer mainly from these issues:
- additional overflow cases are introduced through:
- the use of
std::absonstd::numeric_limits<Int>::min()or - addition/subtraction on the operands prior to division
- the use of
- multiple distinct divisions take place
- negative operands are often not supported, or handled incorrectly
- (also see a non-exhaustive list of these mistakes being made online)
Sometimes, users also emulate these integer divisions by using float and std::floor, or other floating point types and rounding functions.
However, this does not guarantee precise results and is very expensive on platforms without hardware-supported floating point numbers.
Since integer divisions are basic mathematical operations, and implementing them in a robust and performant way is non-trivial, I propose a new <intdiv> header with functions that yield the quotient or remainder for alternative rounding modes.
Add a new feature-test macro in [version.syn]:
#define __cpp_lib_intdiv 202304L // also in <intdiv>
Add a new subclause 28.9 Integer division functions [intdiv] to clause 28 Numerics library [numerics]
The header
<intdiv>provides components to compute quotients and remainders of divisions between integers, using a variety of rounding modes.// all freestanding namespace std { // [intdiv.div], integer quotient functions template <class T> constexpr T div_down(T dividend, T divisor); template <class T> constexpr T div_up(T dividend, T divisor); template <class T> constexpr T div_floor(T dividend, T divisor); template <class T> constexpr T div_ceil(T dividend, T divisor); template <class T> constexpr T div_round_down(T dividend, T divisor); template <class T> constexpr T div_round_up(T dividend, T divisor); template <class T> constexpr T div_round_floor(T dividend, T divisor); template <class T> constexpr T div_round_ceil(T dividend, T divisor); template <class T> constexpr T div_round_even(T dividend, T divisor); template <class T> constexpr T div_round_odd(T dividend, T divisor); template <class T> constexpr T div_euclid(T dividend, T divisor); // [intdiv.rem], integer remainder functions template <class T> constexpr T rem_down(T dividend, T divisor); template <class T> constexpr T rem_floor(T dividend, T divisor); template <class T> constexpr T rem_euclid(T dividend, T divisor); } // namespace stdtemplate <class T> constexpr T div_down(T dividend, T divisor);1 Constraints:
Tis an integral type ([basic.fundamental]).2 Returns: The quotient
qof the divisiondividend / divisor, rounded towards zero. The behaviour is undefined ifdivisor == 0or ifqis not representable byT.[Note 1: this is the behaviour of the division operator.
[expr.mul]--end note]
[Note 2: This function is intended to allow the user to express the choice of rounding modes explicitly. --end note]
template <class T> constexpr T div_up(T dividend, T divisor);3 Constraints:
Tis an integral type ([basic.fundamental]).4 Returns: The quotient
qof the divisiondividend / divisor, rounded away from zero. The behaviour is undefined ifdivisor == 0or ifqis not representable byT.
template <class T> constexpr T div_floor(T dividend, T divisor);5 Constraints:
Tis an integral type ([basic.fundamental]).6 Returns: The quotient
qof the divisiondividend / divisor, rounded towards negative infinity. The behaviour is undefined ifdivisor == 0or ifqis not representable byT.
template <class T> constexpr T div_ceil(T dividend, T divisor);7 Constraints:
Tis an integral type ([basic.fundamental]).8 Returns: The quotient
qof the divisiondividend / divisor, rounded towards positive infinity. The behaviour is undefined ifdivisor == 0or ifqis not representable byT.
template <class T> constexpr T div_round_down(T dividend, T divisor);9 Constraints:
Tis an integral type ([basic.fundamental]).10 Returns: The quotient
qof the divisiondividend / divisor, rounded towards the nearest integer. Exact ties are rounded towards zero. The behaviour is undefined ifdivisor == 0or ifqis not representable byT.[Note: 3 An exact tie occurs when the quotient is the midpoint of two integers. --end note]
template <class T> constexpr T div_round_up(T dividend, T divisor);11 Constraints:
Tis an integral type ([basic.fundamental]).12 Returns: The quotient
qof the divisiondividend / divisor, rounded towards the nearest integer. Exact ties are rounded towards zero. The behaviour is undefined ifdivisor == 0or ifqis not representable byT.
template <class T> constexpr T div_round_floor(T dividend, T divisor);13 Constraints:
Tis an integral type ([basic.fundamental]).14 Returns: The quotient
qof the divisiondividend / divisor, rounded towards the nearest integer. Exact ties are rounded towards negative infinity. The behaviour is undefined ifdivisor == 0or ifqis not representable byT.
template <class T> constexpr T div_round_ceil(T dividend, T divisor);15 Constraints:
Tis an integral type ([basic.fundamental]).16 Returns: The quotient
qof the divisiondividend / divisor, rounded towards the nearest integer. Exact ties are rounded towards positive infinity. The behaviour is undefined ifdivisor == 0or ifqis not representable byT.
template <class T> constexpr T div_round_even(T dividend, T divisor);17 Constraints:
Tis an integral type ([basic.fundamental]).18 Returns: The quotient
qof the divisiondividend / divisor, rounded towards the nearest integer. Exact ties are rounded towards the next quotient which is a multiple of two. The behaviour is undefined ifdivisor == 0or ifqis not representable byT.
template <class T> constexpr T div_round_odd(T dividend, T divisor);19 Constraints:
Tis an integral type ([basic.fundamental]).20 Returns: The quotient
qof the divisiondividend / divisor, rounded towards the nearest integer. Exact ties are rounded towards the next quotient which is not a multiple of two. The behaviour is undefined ifdivisor == 0or ifqis not representable byT.template <class T> constexpr T div_euclid(T dividend, T divisor);21 Constraints:
Tis an integral type ([basic.fundamental]).22 Returns: The quotient
qof the Euclidean divisiondividend / divisor, i.e. towards negative infinity whendivisoris positive, and towards positive infinity whendivisoris negative. The behaviour is undefined ifdivisor == 0or ifqis not representable byT.template <class T> constexpr T rem_down(T dividend, T divisor);1 Constraints:
Tis an integral type ([basic.fundamental]).2 Returns: The remainder
rof the divisionq = div_down(dividend, divisor), such thatq * divisor + r == dividend. The behaviour is undefined ifdivisor == 0or if the quotientdividend / divisoris not representable byT.[Note 1: The sign of the remainder is equal to the sign of the
dividend. --end note]
[Note 2: The result is equal todividend % divisorwhere%is the builtin remainder operator. --end note]
[Note 3: This function is intended to let the user express their choice of remainder operation explicitly. --end note]
template <class T> constexpr T rem_floor(T dividend, T divisor);3 Constraints:
Tis an integral type ([basic.fundamental]).4 Returns: The remainder
rof the divisionq = div_floor(dividend, divisor), such thatq * divisor + r == dividend. The behaviour is undefined ifdivisor == 0or if the quotientdividend / divisoris not representable byT.[Note 4: The sign of the remainder is equal to the sign of the
divisor. --end note]
template <class T> constexpr T rem_euclid(T dividend, T divisor);5 Constraints:
Tis an integral type ([basic.fundamental]).6 Returns: The remainder
rof the divisionq = div_euclid(dividend, divisor), such thatq * divisor + r == dividend. The behaviour is undefined ifdivisor == 0or if the quotientdividend / divisoris not representable byT.[Note 5: The remainder is non-negative. --end note]
The name is modeled after the [utility.intcmp] section.
It would have been possible to use an existing header such as <utility>, <numeric>, or<cmath> for these functions, but there are simply too many.
There is also growth potential; in the future, this header may contain:
- division functions that allow mixed signedness operations
- division functions that yield both the quotient and the remainder simultaneously
- division utilities such as fast_division
The proposal uses the well-established round, trunc, floor, and ceil names which are also found among the common mathematical functions.
However, we deviate from this in the case of trunc, since it has no well-established counterpart and use Java's terminology instead.
It has also been commonly suggested to use a scheme such as:
div_to_zerodiv_from_zerodiv_to_pos_infdiv_to_nearest_ties_to_zero- ...
The main reason to avoid this scheme is the verbosity. Functions in this header are intended to be used frequently in user's expressions, and extreme verbosity hurts ergonomics.
Division towards the infinities as well as division towards/away from zero are commonly useful for programming. The same applies to rounding division and all of its tie-breaking modes.
These tie breaks are useful because they don't skew the distribution when mapping from a wider range onto a narrower range of values. Rounding to the infinities makes it more likely to obtain greater/lower values. Rounding to zero or away from it makes it more likely to obtain greater/lower magnitudes. Rounding to even/odd quotients may have the most desirable statistical properties.
Also see StackOverflow - What is HALF_EVEN rounding for?.
Euclidean divison has some uses in theoretical computer science and cryptography, but exists primarily as a counterpart to rem_euclid.
Not every division function has a matching remainder function, because some are trivially implemented and less useful:
rem_downresults in the same sign as the dividend- a hypothetical
rem_upwould result in the opposite sign and can be trivially implemented by negating the result ofrem_down rem_floorresults in the same sign as the divisor- a hypothetical
rem_ceilwould result in the opposite sign and can be trivially implemented by negating the result ofrem_floor rem_euclidresults in non-negative remainder- a hypothetical function with a negative remainder could be trivially implemented by negating the result of
rem_euclid
Remainder functions for the div_round family of functions would result in a remainder that changes sign based on whether the rounded quotient is closer to the next lower/higher value.
This is substantially less useful compared to the other remainder functions.
The proposal currently reject mixed sign arguments. There are two ways of handling them:
This option is very difficult to implement and even if done correctly, would result in runtime penalties.
For example, it is possible for an unsigned divisor to not be representible by the dividend's type.
- for divison towards zero, this always results in zero
- for division away from zero, this results in the signum of the dividend
- for flooring division, this results in
-1for all negative numbers,0otherwise - for ceiling division, this results in:
0for all negative numbers, except for the minimum, which may result in-11for all positive numbers
- for rounding division, this requires a comparison between the dividend and half of the divisor
- the result is one of
-1,0, or1 - special cases for the minimum representible dividend may be needed
- ties need to be broken correctly, which can be difficult for maximum representible dividend
- the result is one of
As can be seen, the added logic can be non-trivial.
If a divisor is overly large, the result is always representible, but not in the case of an overly large dividend.
Dividing by -1 would always result in a value which is too large to fit the signed type.
We also need to consider whether the resulting type should be signed or unsigned:
- a signed type could never fit the result of a division of an overly large dividend by
1, unless it is the minimum signed value - an unsigned type could never fit the result of a division of an integer by
-1, unless the dividend is zero
Neither option is obviously more correct than the other.
B: Declare cases where one operand has a value not representible by the other as undefined behaviour
In this case, the result type can be the common type, or its std::make_signed counterpart if exactly one of the argument types is signed.
While this solution appears elegant, it declares many valid divisions such as -1 / UINT_MAX as undefined behaviour, which is intuitively wrong.
While this option is by far the simplest, the implementation of different rounding modes is greatly simplified for unsigned types.
A function template may perform better (even on debug builds) with a special case for unsigned types.
It also makes no sense to restrict division to just signed integers, since it is a fundamental operation that can be performed between all integers.
Division between unsigned types is also useful, e.g. ceiling division may be used to determine how many chunks of size n are required to fit a quantity x: std::div_ceil(n, x).
The types involved in this operation are frequently unsigned, so this restriction would inconvenience the user.
Aforementioned edge cases like huge divisors and dividends are relatively uncommon.
The user of these functions should know how they want to handle them if needed, and which resulting type to choose.
This choice may be specific to the user's domain and must not be mandated by the standard library.
The <division> header can be used as a basis which correctly handles all of the regular cases, and typically it is sufficient.
Disallowing mixed sign operations also makes it possible to implement option A or B in the future, as a mostly non-breaking change.
A common way[1] to implement ceiling division is by adjusting the dividend before division:
(x + y - 1) / y // ceiling division
(x + y / 2) / y // rounding divisionHowever, this technique can easily overflow near the minimum and maximum representible values for the divisor.
It also does not handle negative quotients correctly: div_ceil(-3, -2) -> 3 != ceil(-3. / -2.) -> 2 for the above code.
A naive modulus function[2] can also suffer from multiple issues:
int positive_modulo(int i, int n) {
return (i % n + n) % n;
}Just as in the first example, we may overflow for very large n.
This implementation also requires two distinct divisions, which can be very expensive on some architectures.
q = (x + y - 1) / y;
// or avoiding overflow in x+y
q = 1 + ((x - 1) / y); // if x != 0ceiling division by Ganesh Kamath - 'Code Frenzy', accessed 2023-04-06
Problems:
- integer overflow when subtracting from
x - no support for signed operands
Found via: First Google search result for "c++ ceiling integer division", most upvoted answer
q = x/y + (x % y != 0);ceiling division by Miguel Figueiredo, accessed 2023-04-06
Problems:
- no support for negative operands
Found via: First Google search result for "c++ ceiling integer division"
q = (x % y) ? x / y + 1 : x / y;ceiling division by Tatsuyuki Ishi, accessed 2023-04-06
Problems:
- incorrect handling of negative operands (
div_ceil(-1, 2) => 1)
Found via: First Google search result for "c++ ceiling integer division"
int div_ceil(int numerator, int denominator)
{
std::div_t res = std::div(numerator, denominator);
return res.rem ? (res.quot + 1) : res.quot;
}ceiling division by Nathan Ernst, accessed 2023-04-06
Problems:
- incorrect handling of negative operands (
div_ceil(-1, 2) => 1)
Found via: First Google search result for "c++ ceiling integer division"
int div_ceil(int x, int y) {
return x / y + (x % y > 0);
}ceiling division by cubuspl42, accessed 2023-04-06
Problems:
- incorrect handling of negative operands (
div_ceil(-1, 2) => 1)
Found via: First Google search result for "c++ ceiling integer division"
q = (x > 0)? 1 + (x - 1)/y: (x / y);ceiling division by Ben Voigt, accessed 2023-04-06
Problems:
- no support for negative
y
Found via: First Google search result for "c++ ceiling integer division"
q = x/y + !!(x % y);ceiling division by Greg Kramida, accessed 2023-04-06
Problems:
- no support for negative operands
Found via: First Google search result for "c++ ceiling integer division"
q = x/y + !!(x % y);ceiling division by Greg Kramida, accessed 2023-04-06
Problems:
- no support for negative operands
Found via: First Google search result for "c++ ceiling integer division"
int ceili(int numerator, int denominator)
{
return (numerator / denominator + (numerator % denominator != 0));
}ceiling division by Ken Gregg, accessed 2023-04-06
Problems:
- incorrect handling of negative operands (
div_ceil(-1, 2) => 1)
Found via: 2nd Google search result for "c++ ceiling integer division"
q = x / y;
if (q * y < x)
q++;ceiling division by Shubh Pachori, accessed 2023-04-06
Problems:
- incorrect handling of negative operands (
div_ceil(1, -2) => 1)
Found via: 3rd Google search result for "c++ ceiling integer division"
long floordiv (long num, long den)
{
if (0 < (num^den))
return num/den;
else
{
ldiv_t res = ldiv(num,den);
return (res.rem)? res.quot-1
: res.quot;
}
}flooring division by Ichthyo, accessed 2023-04-06
Problems:
- GCC and clang emit
call ldivorcall div, preventing further optimizations
Found via: 1st Google search result for "c++ flooring integer division"
static int div_floor(int a, int b) {
return (a ^ b) < 0 && a ? (1 - abs(a)) / abs(b) - 1 : a / b;
}
static int div_round(int a, int b) {
return (a ^ b) < 0 ? (a - b / 2) / b : (a + b / 2) / b;
}
static int div_ceil(int a, int b) {
return (a ^ b) < 0 || !a ? a / b : (abs(a) - 1) / abs(b) + 1;
}Rounding Modes For Integer Division by njohnny84, accessed 2023-04-06
Problems:
div_floorusesabs(a)andabs(b)which is undefined behaviour if either isINT_MINdiv_roundoverflows ona + b / 2fora=INT_MAX,b >= 2- it is unclear to the reader how exact ties are handled
div_ceilusesabs(a)andabs(b)which is undefined behaviour if either isINT_MIN
Found via: 4th Google search result for "rounding integer division c++"
There are some correct implementations online, but they are very difficult to discover. The most popular solutions typically don't support negative values or support them incorrectly. Having a reliable implementation in the standard library would be of great benefit.