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

u5i3ibmn  于 2022-12-03  发布在  其他
关注(0)|答案(5)|浏览(201)

在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语言中,有没有更有效的方法来做这件事?
请注意,这几乎与此问题相反:Fast ceiling of an integer division in C / C++

shyt4zoc

shyt4zoc1#

生成的代码中的汇编指令更少,我认为得到结果的路径更快。
对于具有大量寄存器的RISC机器,这一个更好,因为根本没有分支,它对流水线和该高速缓存很好。
对于x86实际上这并不重要。

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

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

yiytaume2#

div()标准C语言中的函数

我认为您应该看看<stdlib.h>中的div()函数(它们是标准的C函数,在所有版本的标准中都有定义,尽管链接到POSIX规范)。
C11标准§7.22.6.2规定:
div...函式会在单一运算中计算numer / denomnumer % denom
注意,C11在§6.5.5中指定了整数除法(C99也是类似的):
当整数被除时,/运算符的结果是去掉任何小数部分的代数商。105)
105)这通常称为“向零截断”。
但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的行。

#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)
dced5bon

dced5bon3#

泛除可以通过使用除法和模来执行。
没有理由避免模调用,因为现代编译器将除法和模优化为单个除法。

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

iq0todco4#

“底数除法”的余数要么是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)

幸运的是,在C99/C11之后,C/C/%的结果被标准化为“向零截断”(在此之前,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 =“底除法”商和余数;
  • 令q 0,r 0 =“截尾除法”商和余数。

假设B〉0,不幸的是,r 0在[-b+1,-1]中,然而我们可以很容易地得到r:r = r 0 +B,并且保证r在[1,b-1]中,这在“floor”范围内。对于b〈0的情况也是如此。
既然我们可以确定余数,我们也可以确定商。规则很简单:我们把B加到r 0上,然后从q 0中减去1。
最后,给出了C++11的floor除法的实现:

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)方法相比,这种方法有一个优点:如果除数是编译时常量,则只需要一次比较就可以确定结果。

wdebmtf2

wdebmtf25#

无分支版本:

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

https://godbolt.org/z/9n3637brs
我看到,对于其他答案,编译器生成条件跳转,这意味着更慢的代码。
做了一些性能测试,结果很有趣:

检查code generated by clang表明clang能够优化离开分支(if s和三元运算符)
因此,这表明:优化时首先测量:)。

相关问题