cinteger-divisionfloor-division

Fast floor of a signed integer division in C / C++


In C a floor division can be done, eg:

int floor_div(int a, int b) {
    int d = a / b;
    if (a < 0 != b < 0) {  /* negative output (check inputs since 'd' isn't floored) */
        if (d * a != b) {  /* avoid modulo, use multiply instead */
            d -= 1;        /* floor */
        }
    }
    return d;
}

But this seems like it could be simplified.

Is there a more efficient way to do this in C?


Note that this is nearly the reverse of this question: Fast ceiling of an integer division in C / C++


Solution

  • Floored division can be performed by using a division and modulo.

    There is no reason to avoid the modulo call since modern compilers optimize a divide & modulo into a single divide.

    int floor_div(const int a, const int b) {
        const int d = a / b;
        const int r = a % b;  /* Optimizes into single division. */
        return r ? (d - ((a < 0) ^ (b < 0))) : d;
    }