10

I want something in C++ that lets me do efficient integer division with specified rounding behavior, something like this:

div_down(-4,3)        ==> -2
div_up(4,3)           ==> 2
div_to_zero(-4,3)     ==> -1
div_to_nearest(5,3)   ==> 2

I'd like it to detect target machine behavior at compile time and generate the appropriate optimal implementations. Something similar for modulus would also be nice, abstracting out the undefined behavior for negative operands at compile time.

Does this exist?

If not, what's a nice way to make it? I can think of a few possible approaches:

  • Try to implement them as single expressions that statically optimize
  • Use constant expressions to detect target behavior and choose from multiple implementations, parhaps using templates (but how exactly?)
Björn Pollex
  • 75,346
  • 28
  • 201
  • 283
jedediah
  • 1,179
  • 9
  • 20
  • See this SO question: http://stackoverflow.com/questions/319880/integer-division-rounding-with-negatives-in-c Although there might be an update for C++11. – Sjoerd Nov 15 '11 at 13:50

3 Answers3

6

This is what I've got so far, with the precondition d > 0. They all seem to work, but can they be simplified?

int div_down(int n, int d) {
  if (n < 0) {
    return -((d - n - 1) / d);
  } else {
    return n / d;
  }
}

int div_up(int n, int d) {
  if (n < 0) {
    return -(-n / d);
  } else {
    return (n + d - 1) / d;
  }
}

int div_to_zero(int n, int d) {
  return n / d;
}

int div_to_nearest(int n, int d) {
  if (n < 0) {
    return (n - d/2 + 1) / d;
  } else {
    return (n + d/2) / d;
  }
}
jedediah
  • 1,179
  • 9
  • 20
  • 1
    This is probably better than Atif's answer because [`if`s are usually faster than bit tricks](http://stackoverflow.com/a/33785191/603688). – Dan Nov 18 '15 at 21:22
5

An old post, but here it goes. Kindly accept & rate it if you like. 

int div_to_zero(int n, int d) { return n / d; }
//as per C++11 standard note 80

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

int div_down(int n, int d) {
    return n / d - (((n > 0) ^ (d > 0)) && (n % d));
} //i.e. +1 iff (not exact int && negative result)

int div_to_nearest(int n, int d) {
    return (2*n - d + 2*(true&&(n<0^d>0))*d) / (2*d); 
} //i.e. +-0.5 as per pre-rounding result sign, then div_to-zero 
//it however rounds numbers like +/- 3.5 towards 0 and not even.

Note: most modern compilers will use a single division operation for n/d and n%d used in conjunction. So performance wise these are best reducing memory moves.

Atif Hussain
  • 412
  • 5
  • 9
  • The comment on (at the end of, which isn't entirely commonplace) `div_down` is a copy&paste-error (CnPE)). In `div_to_nearest`, you make do without using the `%` operator - which others tried to achieve for all functions sought. – greybeard Nov 19 '15 at 06:50
1

The last draft of C++11, n3242 which is almost identical to the actual C++11 standard, says this in 5.6 point 4 (page 118):

For integral operands the / operator yields the algebraic quotient with any fractional part discarded; (see note 80)

Note 80 states (note that notes are non-normative):

80) This is often called truncation towards zero.

For completeness, Point 4 goes on to state:

if the quotient a/b is representable in the type of the result, (a/b)*b + a%b is equal to a.

which can be shown to require the sign of a%b to be the same as the sign of a (when not zero).

Note: The actual C++11 standard is not legally online available. However, the drafts are. Luckily, the differences between the last draft (N3242) and the actual standard are small. See this answer.

NOTE: I am not sure which compilers adhere to the C++11 standard yet.

So div_to_zero() is the regular / division.

For the other functions, I'm afraid you'll have to test the signs of a and b and adjust accordingly. Sometimes, an additional check whether a%b equals zero might be needed. So we're looking at 12 test cases per function here (3 for the sign or zeroness of a, times 2 for the sign of b, times 2 whether a%b equals zero or not).

That's too much for me to get right right now, so maybe someone else will jump in and provide the correct answer.

I'm aware that I have not answered your question, but the info above seemed valuable and was too large to fit in a comment.

Community
  • 1
  • 1
Sjoerd
  • 6,837
  • 31
  • 44
  • N3290 is said to be identical to the actual C++11 standard. N3242 is merely _almost_ identical. ;-] – ildjarn Nov 15 '11 at 20:21
  • @ildjarn You're right; I'll edit the text. For others: see http://stackoverflow.com/questions/7238958/iso-c-standard-draft But as there is no (legal) online version of N3290, I still have to rely on N3242. – Sjoerd Nov 16 '11 at 01:26
  • Oh, N3242 is perfectly fine for referencing because of the no-longer-attainable status of N3290. I was just being pedantic. :-] – ildjarn Nov 16 '11 at 01:32
  • @ildjarn Thanks for correcting! Maybe it doesn't matter much in this case, but it might prevent future problems. After all, when quoting standard documents (or drafts of those), one should not be too careless with words ;) – Sjoerd Nov 16 '11 at 01:42