C / C ++中有符号整数除法的快速地板
Fast floor of a signed integer division in 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 中有更有效的方法吗？
请注意，这几乎与这个问题相反：Fast ceiling of an integer division in C / C++
我认为生成代码中的汇编指令更少，结果路径更快。
对于有大量寄存器的 RISC 机器，这个更好，因为根本没有分支，它有利于管道和缓存。
对于 x86 其实没关系。
int floor_div3(int a, int b) {
int d = a / b;
return d * b == a ? d : d - ((a < 0) ^ (b < 0));
}
div() 标准 C 中的函数
我认为您应该看看 <stdlib.h> 中的 div() 函数。 （它们是标准的 C 函数，并且在标准的所有版本中都有定义，尽管 link 符合 POSIX 规范。）
C11 标准 §7.22.6.2 规定：
The div … functions compute numer / denom and numer % denom in a single operation.
请注意，C11 在 §6.5.5 中指定了整数除法（C99 类似）：
When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded.105)
105) This is often called "truncation toward zero".
但 C90 (§6.3.5) 更灵活但用处不大：
When integers are divided and the division is inexact. if both operands are positive the result of the / operator is the largest integer less than the algebraic quotient and the result of the % operator is positive. If either operand is negative, whether the result of the / operator is the largest integer less than or equal to the algebraic quotient or the smallest integer greater than or equal to the algebraic quotient is implementation-defined, as is the sign of the result of the % operator.
floor_div()
请求的floor_div()使用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)
可以使用除法和取模来执行带底除法。
没有理由避免模调用，因为现代编译器将除法和取模优化为单个除法。
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;
}
"floor division" 的余数要么为 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之后标准化为"truncated towards zero"。 （在此之前，C 中的库函数 div 和 C++ 中的 std::div 起着相同的作用）。
我们来比较一下"floor division"和"truncate division"，关注余数的范围：
"floor" "truncate"
b>0 [0, b-1] [-b+1, b-1]
b<0 [b+1, 0] [b+1, -b-1]
为了方便讨论：
- 设a,b = 被除数和除数；
- 令 q, r = "floor division" 的商和余数;
- 令 q0, r0 = "truncate division" 的商和余数。
假设b>0，不幸的是，r0在[-b+1,-1]中。然而我们可以很容易地得到r：r = r0+b，而且r保证在[1, b-1]，也就是在"floor"范围内。 b<0.
的情况也是如此
既然我们可以求余数，那么我们也可以求商。规则很简单：我们将 b 加到 r0，然后我们必须从 q0 中减去 1。
作为结尾，"floor division"在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)方法相比，这种方法有一个优点：如果除数是编译时常量，只需要比较一次就可以确定结果。
在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++
我认为生成代码中的汇编指令更少，结果路径更快。
对于有大量寄存器的 RISC 机器，这个更好，因为根本没有分支，它有利于管道和缓存。
对于 x86 其实没关系。
int floor_div3(int a, int b) {
int d = a / b;
return d * b == a ? d : d - ((a < 0) ^ (b < 0));
}
div() 标准 C 中的函数
我认为您应该看看 <stdlib.h> 中的 div() 函数。 （它们是标准的 C 函数，并且在标准的所有版本中都有定义，尽管 link 符合 POSIX 规范。）
C11 标准 §7.22.6.2 规定：
The
div… functions computenumer / denomandnumer % denomin a single operation.
请注意，C11 在 §6.5.5 中指定了整数除法（C99 类似）：
When integers are divided, the result of the
/operator is the algebraic quotient with any fractional part discarded.105)105) This is often called "truncation toward zero".
但 C90 (§6.3.5) 更灵活但用处不大：
When integers are divided and the division is inexact. if both operands are positive the result of the
/operator is the largest integer less than the algebraic quotient and the result of the%operator is positive. If either operand is negative, whether the result of the/operator is the largest integer less than or equal to the algebraic quotient or the smallest integer greater than or equal to the algebraic quotient is implementation-defined, as is the sign of the result of the%operator.
floor_div()
请求的floor_div()使用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)
可以使用除法和取模来执行带底除法。
没有理由避免模调用，因为现代编译器将除法和取模优化为单个除法。
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;
}
"floor division" 的余数要么为 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之后标准化为"truncated towards zero"。 （在此之前，C 中的库函数 div 和 C++ 中的 std::div 起着相同的作用）。
我们来比较一下"floor division"和"truncate division"，关注余数的范围：
"floor" "truncate"
b>0 [0, b-1] [-b+1, b-1]
b<0 [b+1, 0] [b+1, -b-1]
为了方便讨论：
- 设a,b = 被除数和除数；
- 令 q, r = "floor division" 的商和余数;
- 令 q0, r0 = "truncate division" 的商和余数。
假设b>0，不幸的是，r0在[-b+1,-1]中。然而我们可以很容易地得到r：r = r0+b，而且r保证在[1, b-1]，也就是在"floor"范围内。 b<0.
的情况也是如此既然我们可以求余数，那么我们也可以求商。规则很简单：我们将 b 加到 r0，然后我们必须从 q0 中减去 1。
作为结尾，"floor division"在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)方法相比，这种方法有一个优点：如果除数是编译时常量，只需要比较一次就可以确定结果。