C++ functions for integer division with well defin

问题:

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?)

回答1:

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

回答2:

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.

回答3:

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.