C/C++ 中带符号整数除法的快速下限

Question

在 C 中可以进行楼层划分，例如：

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

但这似乎可以简化。

在 C 中有没有更有效的方法来做到这一点？

---

请注意，这几乎与这个问题相反：C/C++ 中整数除法的快速上限

Answer 1

生成的代码中的汇编指令更少，我认为获得结果的路径更快。

对于具有大量寄存器的 RISC 机器来说，这个更好，因为根本没有分支，而且它有利于管道和缓存。

对于 x86 实际上没有关系。

int floor_div3(int a, int b) {
    int d = a / b;


    return d * b == a ? d : d - ((a < 0) ^ (b < 0));
}

Answer 2

div()标准 C 中的函数

\n

我认为你应该看看div()的函数<stdlib.h>。（尽管它们链接到 POSIX 规范，但它们是标准 C 函数，并在该标准的所有版本中定义。）

\n

C11 标准 \xc2\xa77.22.6.2 指定：

\n

\n

div\xe2\x80\xa6 函数计算numer / denom并numer % denom单个操作中

\n

\n

请注意，C11 在 \xc2\xa76.5.5 中指定整数除法（C99 类似）：

\n

\n

当整数相除时，运算符的结果/是代数商，并丢弃任何小数部分。^105）

\n

¹⁰⁵⁾这通常称为“向零截断”。

\n

\n

但 C90 (\xc2\xa76.3.5) 更灵活但不太有用：

\n

\n

当整数相除并且相除不精确时。如果两个操作数都为正，则运算符的结果/是小于代数商的最大整数，并且%运算符的结果为正。如果任一操作数为负，则运算符的结果/是小于或等于代数商的最大整数还是大于或等于代数商的最小整数是实现定义的，与运算结果的符号相同%操作员。

\n

\n

floor_div()

\n

floor_div()所请求使用的计算代码div()干净整洁。

\n

int floor_div(int a, int b)\n{\n    assert(b != 0);\n    div_t r = div(a, b);\n    if (r.rem != 0 && ((a < 0) ^ (b < 0)))\n        r.quot--;\n    return r.quot;\n}\n

\n

测试代码

\n

下面代码中的打印格式是根据示例数据精确定制的。%4d（使用起来和贯穿始终会更好，但更广泛%-4d）。此代码打印长度为 89 个字符加换行符的行；更一般的布局将打印长度为 109 的行。两者都没有避免 SO 上的水平滚动条。

\n

#include <assert.h>\n#include <stdio.h>\n#include <stdlib.h>\n\nstatic int floor_div(int a, int b)\n{\n    assert(b != 0);\n    div_t r = div(a, b);\n    if (r.rem != 0 && ((a < 0) ^ (b < 0)))\n        r.quot--;\n    return r.quot;\n}\n\nstatic void test_floor_div(int n, int d)\n{\n    assert(d != 0);\n    printf(   "%3d/%-2d = %-3d (%3d)", +n, +d, floor_div(+n, +d), +n / +d);\n    printf(";  %3d/%-3d = %-4d (%4d)", +n, -d, floor_div(+n, -d), +n / -d);\n    if (n != 0)\n    {\n        printf(";  %4d/%-2d = %-4d (%4d)", -n, +d, floor_div(-n, +d), -n / +d);\n        printf(";  %4d/%-3d = %-3d (%3d)", -n, -d, floor_div(-n, -d), -n / -d);\n    }\n    putchar(\'\\n\');\n}\n\nint main(void)\n{\n    int numerators[] = { 0, 1, 2, 4, 9, 23, 291 };\n    enum { NUM_NUMERATORS = sizeof(numerators) / sizeof(numerators[0]) };\n    int denominators[] = { 1, 2, 3, 6, 17, 23 };\n    enum { NUM_DENOMINATORS = sizeof(denominators) / sizeof(denominators[0]) };\n\n    for (int i = 0; i < NUM_NUMERATORS; i++)\n    {\n        for (int j = 0; j < NUM_DENOMINATORS; j++)\n            test_floor_div(numerators[i], denominators[j]);\n        putchar(\'\\n\');\n    }\n\n    return 0;\n}\n

\n

测试输出

\n

  0/1  = 0   (  0);    0/-1  = 0    (   0)\n  0/2  = 0   (  0);    0/-2  = 0    (   0)\n  0/3  = 0   (  0);    0/-3  = 0    (   0)\n  0/6  = 0   (  0);    0/-6  = 0    (   0)\n  0/17 = 0   (  0);    0/-17 = 0    (   0)\n  0/23 = 0   (  0);    0/-23 = 0    (   0)\n\n  1/1  = 1   (  1);    1/-1  = -1   (  -1);    -1/1  = -1   (  -1);    -1/-1  = 1   (  1)\n  1/2  = 0   (  0);    1/-2  = -1   (   0);    -1/2  = -1   (   0);    -1/-2  = 0   (  0)\n  1/3  = 0   (  0);    1/-3  = -1   (   0);    -1/3  = -1   (   0);    -1/-3  = 0   (  0)\n  1/6  = 0   (  0);    1/-6  = -1   (   0);    -1/6  = -1   (   0);    -1/-6  = 0   (  0)\n  1/17 = 0   (  0);    1/-17 = -1   (   0);    -1/17 = -1   (   0);    -1/-17 = 0   (  0)\n  1/23 = 0   (  0);    1/-23 = -1   (   0);    -1/23 = -1   (   0);    -1/-23 = 0   (  0)\n\n  2/1  = 2   (  2);    2/-1  = -2   (  -2);    -2/1  = -2   (  -2);    -2/-1  = 2   (  2)\n  2/2  = 1   (  1);    2/-2  = -1   (  -1);    -2/2  = -1   (  -1);    -2/-2  = 1   (  1)\n  2/3  = 0   (  0);    2/-3  = -1   (   0);    -2/3  = -1   (   0);    -2/-3  = 0   (  0)\n  2/6  = 0   (  0);    2/-6  = -1   (   0);    -2/6  = -1   (   0);    -2/-6  = 0   (  0)\n  2/17 = 0   (  0);    2/-17 = -1   (   0);    -2/17 = -1   (   0);    -2/-17 = 0   (  0)\n  2/23 = 0   (  0);    2/-23 = -1   (   0);    -2/23 = -1   (   0);    -2/-23 = 0   (  0)\n\n  4/1  = 4   (  4);    4/-1  = -4   (  -4);    -4/1  = -4   (  -4);    -4/-1  = 4   (  4)\n  4/2  = 2   (  2);    4/-2  = -2   (  -2);    -4/2  = -2   (  -2);    -4/-2  = 2   (  2)\n  4/3  = 1   (  1);    4/-3  = -2   (  -1);    -4/3  = -2   (  -1);    -4/-3  = 1   (  1)\n  4/6  = 0   (  0);    4/-6  = -1   (   0);    -4/6  = -1   (   0);    -4/-6  = 0   (  0)\n  4/17 = 0   (  0);    4/-17 = -1   (   0);    -4/17 = -1   (   0);    -4/-17 = 0   (  0)\n  4/23 = 0   (  0);    4/-23 = -1   (   0);    -4/23 = -1   (   0);    -4/-23 = 0   (  0)\n\n  9/1  = 9   (  9);    9/-1  = -9   (  -9);    -9/1  = -9   (  -9);    -9/-1  = 9   (  9)\n  9/2  = 4   (  4);    9/-2  = -5   (  -4);    -9/2  = -5   (  -4);    -9/-2  = 4   (  4)\n  9/3  = 3   (  3);    9/-3  = -3   (  -3);    -9/3  = -3   (  -3);    -9/-3  = 3   (  3)\n  9/6  = 1   (  1);    9/-6  = -2   (  -1);    -9/6  = -2   (  -1);    -9/-6  = 1   (  1)\n  9/17 = 0   (  0);    9/-17 = -1   (   0);    -9/17 = -1   (   0);    -9/-17 = 0   (  0)\n  9/23 = 0   (  0);    9/-23 = -1   (   0);    -9/23 = -1   (   0);    -9/-23 = 0   (  0)\n\n 23/1  = 23  ( 23);   23/-1  = -23  ( -23);   -23/1  = -23  ( -23);   -23/-1  = 23  ( 23)\n 23/2  = 11  ( 11);   23/-2  = -12  ( -11);   -23/2  = -12  ( -11);   -23/-2  = 11  ( 11)\n 23/3  = 7   (  7);   23/-3  = -8   (  -7);   -23/3  = -8   (  -7);   -23/-3  = 7   (  7)\n 23/6  = 3   (  3);   23/-6  = -4   (  -3);   -23/6  = -4   (  -3);   -23/-6  = 3   (  3)\n 23/17 = 1   (  1);   23/-17 = -2   (  -1);   -23/17 = -2   (  -1);   -23/-17 = 1   (  1)\n 23/23 = 1   (  1);   23/-23 = -1   (  -1);   -23/23 = -1   (  -1);   -23/-23 = 1   (  1)\n\n291/1  = 291 (291);  291/-1  = -291 (-291);  -291/1  = -291 (-291);  -291/-1  = 291 (291)\n291/2  = 145 (145);  291/-2  = -146 (-145);  -291/2  = -146 (-145);  -291/-2  = 145 (145)\n291/3  = 97  ( 97);  291/-3  = -97  ( -97);  -291/3  = -97  ( -97);  -291/-3  = 97  ( 97)\n291/6  = 48  ( 48);  291/-6  = -49  ( -48);  -291/6  = -49  ( -48);  -291/-6  = 48  ( 48)\n291/17 = 17  ( 17);  291/-17 = -18  ( -17);  -291/17 = -18  ( -17);  -291/-17 = 17  ( 17)\n291/23 = 12  ( 12);  291/-23 = -13  ( -12);  -291/23 = -13  ( -12);  -291/-23 = 12  ( 12)\n

\n

Answer 3

地板除法可以通过使用除法和模来执行。

没有理由避免模调用，因为现代编译器将除法和模数优化为单个除法。

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