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

在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中

我想你应该看一下中的div()函数。 （它们是标准的C函数，并且在标准的所有版本中定义，尽管链接到POSIX规范。）

C11标准§7.22.6.2规定：

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

注意，C11指定§6.5.5中的整数除法（并且C99类似）：

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

^105）这通常被称为“截断为零”。

但C90（§6.3.5）更灵活但function更少：

当整数被分割并且除法不精确时。 如果两个操作数均为正，则/运算符的结果是小于代数商的最大整数， %运算符的结果为正。 如果任一操作数为负，则/运算符的结果是小于或等于代数商的最大整数还是大于或等于代数商的最小整数是实现 – 否定的，这是结果的符号%运算符。

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

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

Answer 4

“地板划分”的其余部分为0，或者与除数具有相同的符号。

 (the proof) a: dividend b: divisor q: quotient r: remainder q = floor(a/b) a = q * b + rr = a - q * b = (a/b - q) * b ~~~~~~~~~ ^ this factor in [0, 1) 

幸运的是，在C99 / C ++ 11之后，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 =“地板划分”的商和余数;
• 令q0，r0 =“截断分割”的商和余数。

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

现在我们可以修复余数，我们也可以修复商。 规则很简单：我们将b添加到r0，然后我们必须从q0中减去1。

作为结束，在C ++ 11中实现“floor division”：

 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)方法相比，此方法具有以下优点：如果除数是编译时常量，则只需要一次比较来修复结果。