在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++
5条答案
按热度按时间shyt4zoc1#
生成的代码中的汇编指令更少,我认为得到结果的路径更快。
对于具有大量寄存器的RISC机器,这一个更好,因为根本没有分支,它对流水线和该高速缓存很好。
对于x86实际上这并不重要。
yiytaume2#
div()
标准C语言中的函数我认为您应该看看
<stdlib.h>
中的div()
函数(它们是标准的C函数,在所有版本的标准中都有定义,尽管链接到POSIX规范)。C11标准§7.22.6.2规定:
div
...函式会在单一运算中计算numer / denom
和numer % denom
。注意,C11在§6.5.5中指定了整数除法(C99也是类似的):
当整数被除时,
/
运算符的结果是去掉任何小数部分的代数商。105)105)这通常称为“向零截断”。
但C90(§6.3.5)更灵活,但用处不大:
当整数被除且除法不精确时,如果两个操作数都为正,则
/
运算符的结果是小于代数商的最大整数,并且%
运算符的结果为正。如果其中一个操作数为负,/
运算符的结果是小于或等于代数商的最大整数还是大于的最小整数、或等于代数商的值是由实现定义的,%
运算符的结果的符号也是如此。floor_div()
的第一个字母使用
div()
的所请求的floor_div()
的计算代码是整洁的。测试代码
下面代码中的打印格式非常精确地适合示例数据。(最好始终使用
%4d
和%-4d
,但扩展性更强)。此代码打印长度为89个字符加上换行符的行;更一般的布局将打印长度为109的行。测试输出
dced5bon3#
泛除可以通过使用除法和模来执行。
没有理由避免模调用,因为现代编译器将除法和模优化为单个除法。
iq0todco4#
“底数除法”的余数要么是0,要么与除数具有相同的符号。
幸运的是,在C99/C11之后,C/C中
/
和%
的结果被标准化为“向零截断”(在此之前,C中的库函数div
和C++中的std::div
扮演着相同的角色)。让我们比较一下“底数除法”和“截尾除法”,重点看余数的取值范围:
为便于讨论:
假设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除法的实现:
与著名的
(a < 0) ^ (b < 0)
方法相比,这种方法有一个优点:如果除数是编译时常量,则只需要一次比较就可以确定结果。wdebmtf25#
无分支版本:
https://godbolt.org/z/9n3637brs
我看到,对于其他答案,编译器生成条件跳转,这意味着更慢的代码。
做了一些性能测试,结果很有趣:
检查code generated by clang表明clang能够优化离开分支(
if
s和三元运算符)因此,这表明:优化时首先测量:)。