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

Question

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

9

在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 ++中快速向上取整的整数除法

- ideasman42

这取决于您的编译器、目标、优化设置、编译器版本等。 - too honest for this site

2

当然，确切的优化取决于编译器版本。尽管如此，通常会询问有关函数的高效C实现 - 例如，这几乎是与此问题相反的问题：https://dev59.com/OHE85IYBdhLWcg3wgDvd - ideasman42

5个回答

5

`div()`标准C函数

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

C11标准§7.22.6.2指定：

div …函数在单个操作中计算numer / denom和numer % denom。

请注意，C11在§6.5.5中指定整数除法（C99类似）：

当整数相除时，/运算符的结果是代数商，任何小数部分都会被舍弃。¹⁰⁵⁾

¹⁰⁵⁾这通常称为“向零取整”。

但是C90（§6.3.5）更加灵活但不太实用：

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

`floor_div()`

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

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

测试代码

下面代码中的打印格式非常精确地针对了样本数据。(使用%4d和%-4d会更好，但更加费力)。此代码打印长度为89个字符加换行符的行；更一般的布局将打印长度为109的行。两者都无法避免SO上的水平滚动条。

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

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

static void test_floor_div(int n, int d)
{
    assert(d != 0);
    printf(   "%3d/%-2d = %-3d (%3d)", +n, +d, floor_div(+n, +d), +n / +d);
    printf(";  %3d/%-3d = %-4d (%4d)", +n, -d, floor_div(+n, -d), +n / -d);
    if (n != 0)
    {
        printf(";  %4d/%-2d = %-4d (%4d)", -n, +d, floor_div(-n, +d), -n / +d);
        printf(";  %4d/%-3d = %-3d (%3d)", -n, -d, floor_div(-n, -d), -n / -d);
    }
    putchar('\n');
}

int main(void)
{
    int numerators[] = { 0, 1, 2, 4, 9, 23, 291 };
    enum { NUM_NUMERATORS = sizeof(numerators) / sizeof(numerators[0]) };
    int denominators[] = { 1, 2, 3, 6, 17, 23 };
    enum { NUM_DENOMINATORS = sizeof(denominators) / sizeof(denominators[0]) };

    for (int i = 0; i < NUM_NUMERATORS; i++)
    {
        for (int j = 0; j < NUM_DENOMINATORS; j++)
            test_floor_div(numerators[i], denominators[j]);
        putchar('\n');
    }

    return 0;
}

测试输出

  0/1  = 0   (  0);    0/-1  = 0    (   0)
  0/2  = 0   (  0);    0/-2  = 0    (   0)
  0/3  = 0   (  0);    0/-3  = 0    (   0)
  0/6  = 0   (  0);    0/-6  = 0    (   0)
  0/17 = 0   (  0);    0/-17 = 0    (   0)
  0/23 = 0   (  0);    0/-23 = 0    (   0)

  1/1  = 1   (  1);    1/-1  = -1   (  -1);    -1/1  = -1   (  -1);    -1/-1  = 1   (  1)
  1/2  = 0   (  0);    1/-2  = -1   (   0);    -1/2  = -1   (   0);    -1/-2  = 0   (  0)
  1/3  = 0   (  0);    1/-3  = -1   (   0);    -1/3  = -1   (   0);    -1/-3  = 0   (  0)
  1/6  = 0   (  0);    1/-6  = -1   (   0);    -1/6  = -1   (   0);    -1/-6  = 0   (  0)
  1/17 = 0   (  0);    1/-17 = -1   (   0);    -1/17 = -1   (   0);    -1/-17 = 0   (  0)
  1/23 = 0   (  0);    1/-23 = -1   (   0);    -1/23 = -1   (   0);    -1/-23 = 0   (  0)

  2/1  = 2   (  2);    2/-1  = -2   (  -2);    -2/1  = -2   (  -2);    -2/-1  = 2   (  2)
  2/2  = 1   (  1);    2/-2  = -1   (  -1);    -2/2  = -1   (  -1);    -2/-2  = 1   (  1)
  2/3  = 0   (  0);    2/-3  = -1   (   0);    -2/3  = -1   (   0);    -2/-3  = 0   (  0)
  2/6  = 0   (  0);    2/-6  = -1   (   0);    -2/6  = -1   (   0);    -2/-6  = 0   (  0)
  2/17 = 0   (  0);    2/-17 = -1   (   0);    -2/17 = -1   (   0);    -2/-17 = 0   (  0)
  2/23 = 0   (  0);    2/-23 = -1   (   0);    -2/23 = -1   (   0);    -2/-23 = 0   (  0)

  4/1  = 4   (  4);    4/-1  = -4   (  -4);    -4/1  = -4   (  -4);    -4/-1  = 4   (  4)
  4/2  = 2   (  2);    4/-2  = -2   (  -2);    -4/2  = -2   (  -2);    -4/-2  = 2   (  2)
  4/3  = 1   (  1);    4/-3  = -2   (  -1);    -4/3  = -2   (  -1);    -4/-3  = 1   (  1)
  4/6  = 0   (  0);    4/-6  = -1   (   0);    -4/6  = -1   (   0);    -4/-6  = 0   (  0)
  4/17 = 0   (  0);    4/-17 = -1   (   0);    -4/17 = -1   (   0);    -4/-17 = 0   (  0)
  4/23 = 0   (  0);    4/-23 = -1   (   0);    -4/23 = -1   (   0);    -4/-23 = 0   (  0)

  9/1  = 9   (  9);    9/-1  = -9   (  -9);    -9/1  = -9   (  -9);    -9/-1  = 9   (  9)
  9/2  = 4   (  4);    9/-2  = -5   (  -4);    -9/2  = -5   (  -4);    -9/-2  = 4   (  4)
  9/3  = 3   (  3);    9/-3  = -3   (  -3);    -9/3  = -3   (  -3);    -9/-3  = 3   (  3)
  9/6  = 1   (  1);    9/-6  = -2   (  -1);    -9/6  = -2   (  -1);    -9/-6  = 1   (  1)
  9/17 = 0   (  0);    9/-17 = -1   (   0);    -9/17 = -1   (   0);    -9/-17 = 0   (  0)
  9/23 = 0   (  0);    9/-23 = -1   (   0);    -9/23 = -1   (   0);    -9/-23 = 0   (  0)

 23/1  = 23  ( 23);   23/-1  = -23  ( -23);   -23/1  = -23  ( -23);   -23/-1  = 23  ( 23)
 23/2  = 11  ( 11);   23/-2  = -12  ( -11);   -23/2  = -12  ( -11);   -23/-2  = 11  ( 11)
 23/3  = 7   (  7);   23/-3  = -8   (  -7);   -23/3  = -8   (  -7);   -23/-3  = 7   (  7)
 23/6  = 3   (  3);   23/-6  = -4   (  -3);   -23/6  = -4   (  -3);   -23/-6  = 3   (  3)
 23/17 = 1   (  1);   23/-17 = -2   (  -1);   -23/17 = -2   (  -1);   -23/-17 = 1   (  1)
 23/23 = 1   (  1);   23/-23 = -1   (  -1);   -23/23 = -1   (  -1);   -23/-23 = 1   (  1)

291/1  = 291 (291);  291/-1  = -291 (-291);  -291/1  = -291 (-291);  -291/-1  = 291 (291)
291/2  = 145 (145);  291/-2  = -146 (-145);  -291/2  = -146 (-145);  -291/-2  = 145 (145)
291/3  = 97  ( 97);  291/-3  = -97  ( -97);  -291/3  = -97  ( -97);  -291/-3  = 97  ( 97)
291/6  = 48  ( 48);  291/-6  = -49  ( -48);  -291/6  = -49  ( -48);  -291/-6  = 48  ( 48)
291/17 = 17  ( 17);  291/-17 = -18  ( -17);  -291/17 = -18  ( -17);  -291/-17 = 17  ( 17)
291/23 = 12  ( 12);  291/-23 = -13  ( -12);  -291/23 = -13  ( -12);  -291/-23 = 12  ( 12)

- Jonathan Leffler

感谢您提供的全面答案和测试。然而，我研究了一下，并发现至少在glibc中，div不是内置函数。虽然这个答案是正确的，但我不确定是否想在性能关键代码上使用它。请参见生成的汇编代码：https://godbolt.org/g/9QmyFn - ideasman42

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

- ideasman42

1

"地板除法"的余数要么是0，要么与除数具有相同的符号。"

(the proof)  
a: dividend  b: divisor
q: quotient  r: remainder

q = floor(a/b)
a = q * b + r  
r = a - q * b = (a/b - q) * b  
                ~~~~~~~~~
                    ^ this factor in [0, 1)

幸运的是，在C/C++中，除法和取模运算的结果在C99/C++11之后被标准化为“向零截断”（在此之前，C语言的库函数div和C++的std::div扮演了相同的角色）。

让我们比较“向下取整除法”和“截断除法”，重点关注余数的范围：

       "floor"     "truncate"
b>0    [0, b-1]    [-b+1, b-1]
b<0    [b+1, 0]    [b+1, -b-1]

为了方便讨论：

令 a, b = 被除数和除数；
令 q, r = "向下取整除法" 的商和余数；
令 q0, r0 = "截断除法" 的商和余数。

假设 b>0，不幸的是，r0在[-b+1, -1]范围内。但我们可以很容易地得到 r：r = r0+b，并且保证r在[1，b-1]范围内，这是“向下”范围内的。当b<0时也是如此。

既然我们可以修正余数，那么我们也可以修正商。规则很简单：我们将b加到r0上，然后从q0中减去1。

最后，以下是C++11中“向下取整除法”的实现：

void floor_div(int& q, int& r, int a, int b)
{
    int q0 = a / b;
    int r0 = a % b;
    if (b > 0){
        q = r0 >= 0 ? q0 : q0 - 1;
        r = r0 >= 0 ? r0 : r0 + b;
    }
    else {
        q = r0 <= 0 ? q0 : q0 - 1;
        r = r0 <= 0 ? r0 : r0 + b;
    }
}

与著名的 (a < 0) ^ (b < 0) 方法相比，这种方法具有优势：如果除数是编译时常量，则只需要进行一次比较即可修正结果。

- kevinjwz

0

无分支版本：

int floor_div(int x, int y)
{
    return x / y - (x % y != 0) * ((x < 0) ^ (y < 0));
}

https://godbolt.org/z/9n3637brs

我看到其他答案中编译器生成了条件跳转，这意味着代码会变慢。

进行了一些性能测试，结果很有趣：

gcc我的函数速度最快，但差异微不足道
clang我的函数排名第三，比第二和第三慢10％

检查clang生成的代码表明，clang能够优化掉分支（if和三元运算符）

因此，这表明：在优化时先进行测量 :)

- Marek R

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- 0___________ · Accepted Answer

我认为生成的代码中少一些汇编指令，能更快地得到结果。

对于寄存器数量庞大的RISC机器来说，这个更好，因为没有分支，有利于流水线和缓存。

对于x86架构，实际上并不重要。

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


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

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

div()标准C函数

floor_div()

测试代码

测试输出

`div()`标准C函数

`floor_div()`