计算大于或等于a/b的最小整数的最简单方法是什么？

Question

r,a并且b是整数.

我需要最便宜的计算,因为在代码的关键部分.我发现 :

r = (a / b) + (((a % b) != 0) ? 1 : 0);

如果b是2的幂,则a / b可以替换为a >> log2(b)

而a % b与a & (b-1)这应该节省大量的计算时间.

你知道更好的解决方案吗？

Answer 1

val r = (a + b - 1) / b

例如:

scala> for(a <- 1 to 10; b <- 1 to a) println("a: "+a+"\tb: "+b+"\tr: "+((a+b-1)/b))
a: 1    b: 1    r: 1
a: 2    b: 1    r: 2
a: 2    b: 2    r: 1
a: 3    b: 1    r: 3
a: 3    b: 2    r: 2
a: 3    b: 3    r: 1
a: 4    b: 1    r: 4
a: 4    b: 2    r: 2
a: 4    b: 3    r: 2
a: 4    b: 4    r: 1
a: 5    b: 1    r: 5
a: 5    b: 2    r: 3
a: 5    b: 3    r: 2
a: 5    b: 4    r: 2
a: 5    b: 5    r: 1
a: 6    b: 1    r: 6
a: 6    b: 2    r: 3
a: 6    b: 3    r: 2
a: 6    b: 4    r: 2
a: 6    b: 5    r: 2
a: 6    b: 6    r: 1
a: 7    b: 1    r: 7
a: 7    b: 2    r: 4
a: 7    b: 3    r: 3
a: 7    b: 4    r: 2
a: 7    b: 5    r: 2
a: 7    b: 6    r: 2
a: 7    b: 7    r: 1
a: 8    b: 1    r: 8
a: 8    b: 2    r: 4
a: 8    b: 3    r: 3
a: 8    b: 4    r: 2
a: 8    b: 5    r: 2
a: 8    b: 6    r: 2
a: 8    b: 7    r: 2
a: 8    b: 8    r: 1
a: 9    b: 1    r: 9
a: 9    b: 2    r: 5
a: 9    b: 3    r: 3
a: 9    b: 4    r: 3
a: 9    b: 5    r: 2
a: 9    b: 6    r: 2
a: 9    b: 7    r: 2
a: 9    b: 8    r: 2
a: 9    b: 9    r: 1
a: 10   b: 1    r: 10
a: 10   b: 2    r: 5
a: 10   b: 3    r: 4
a: 10   b: 4    r: 3
a: 10   b: 5    r: 2
a: 10   b: 6    r: 2
a: 10   b: 7    r: 2
a: 10   b: 8    r: 2
a: 10   b: 9    r: 2
a: 10   b: 10   r: 1

这确实是假设的a并且b是积极的.如果其中一个是负的,这取决于是否司是对称或地板(现代语言和平台是对称的),以及信号a和b.

如果a*b >= 0,则公式按给定的方式工作.如果除法是对称的a*b < 0,那么a / b给出正确的答案.

Answer 2

在标题中你会问"最简单" - 但问题暗示了最"有效".你需要哪一个？在实践中,最简单的并不总是等同于最有效的.

因此,如果你需要最简单的方法,你可能应该使用你的语言的天花板功能(通常称为ceil),如果你需要最有效的 - 这实际上很大程度上取决于你正在使用的处理器(它是否实现了硬件和其他这样的因素)

另外,我对log2的性能持怀疑态度 - 但我可能错了.但有一件事很清楚:为优化而优化几乎总是不是一个好主意.