Division with negative dividend, but rounded towards negative infinity?

Question

Consider the following code (in C++11):

int a = -11, b = 3;
int c = a / b;
// now c == -3

C++11 specification says that division with a negative dividend is rounded toward zero.

It is quite useful for there to be a operator or function to do division with rounding toward negative infinity (e.g. for consistency with positive dividends when iterating a range), so is there a function or operator in the standard library that does what I want? Or perhaps a compiler-defined function/intrinsic that does it in modern compilers?

I could write my own, such as the following (works only for positive divisors):

int div_neg(int dividend, int divisor){
    if(dividend >= 0) return dividend / divisor;
    else return (dividend - divisor + 1) / divisor;
}

But it would not be as descriptive of my intent, and possibly not be as optimized a standard library function or compiler intrinsic (if it exists).

Answer 1

I'm not aware of any intrinsics for it. I would simply apply a correction to standard division retrospectively.

int div_floor(int a, int b)
{
    int res = a / b;
    int rem = a % b;
    // Correct division result downwards if up-rounding happened,
    // (for non-zero remainder of sign different than the divisor).
    int corr = (rem != 0 && ((rem < 0) != (b < 0)));
    return res - corr;
}

Note it also works for pre-C99 and pre-C++11, i.e. without standarization of rounding division towards zero.

Answer 2

Here's another possible variant, valid for positive divisors and arbitrary dividends.

int div_floor(int n, int d) {
    return n >= 0 ? n / d : -1 - (-1 - n) / d;
}

Explanation: in the case of negative n, write q for (-1 - n) / d, then -1 - n = qd + r for some r satisfying 0 <= r < d. Rearranging gives n = (-1 - q)d + (d - 1 - r). It's clear that 0 <= d - 1 - r < d, so d - 1 - r is the remainder of the floor division operation, and -1 - q is the quotient.

Note that the arithmetic operations here are all safe from overflow, regardless of the internal representation of signed integers (two's complement, ones' complement, sign-magnitude).

Assuming two's complement representation for signed integers, a good compiler should optimise the two -1-* operations to bitwise negation operations. On my x86-64 machine, the second branch of the conditional gets compiled to the following sequence:

notl    %edi
movl    %edi, %eax
cltd
idivl   %esi
notl    %eax