为了账号安全,请及时绑定邮箱和手机立即绑定

如何确保整数除法总是四舍五入?

如何确保整数除法总是四舍五入?

MYYA 2019-07-23 15:59:54
如何确保整数除法总是四舍五入?我想确保在必要时整数除以整数。有比这更好的方法吗?有很多铸件正在进行中。:-)(int)Math.Ceiling((double)myInt1 / myInt2)
查看完整描述

3 回答

?
繁花不似锦

TA贡献1851条经验 获得超4个赞

获得整数算术是正确的。正如迄今为止已经充分证明的那样,当你尝试做一个“聪明”的伎俩时,你犯错误的可能性很大。当发现一个缺陷时,更改代码以修复缺陷而不考虑修复是否破坏其他东西并不是一个很好的解决问题的技术。到目前为止,我们已经考虑了五种不同的错误整数算术解决方案来解决这个完全不是特别困难的问题。

解决整数算术问题的正确方法 - 即增加第一次得到正确答案的可能性的方法 - 是仔细处理问题,一次一步地解决问题,并使用良好的工程原理所以。

首先阅读您要替换的内容的规范。整数除法的规范明确规定:

  1. 该部门将结果舍入为零

  2. 当两个操作数具有相同符号时,结果为零或正,当两个操作数具有相反符号时,结果为零或负

  3. 如果左操作数是最小的可表示的int而右操作数是-1,则发生溢出。[...]它是实现定义的,是否抛出[ArithmeticException]或溢出未报告,结果值是左操作数的值。

  4. 如果右操作数的值为零,则抛出System.DivideByZeroException。

我们想要的是一个整数除法函数,它计算商但是总是向上舍入结果,而不是总是向零

所以写一个该函数的规范。我们的函数int DivRoundUp(int dividend, int divisor)必须为每个可能的输入定义行为。这种未定义的行为令人深感担忧,所以让我们消除它。我们会说我们的操作有这个规范:

  1. 如果除数为零,则抛出操作

  2. 如果dividend为int.minval且divisor为-1,则抛出操作

  3. 如果没有余数 - 除法是'偶数' - 那么返回值就是整数商

  4. 否则,它返回大于商的最小整数,也就是说,它总是向上舍入。

现在我们有一个规格,所以我们知道我们可以提出一个可测试的设计。假设我们添加了一个额外的设计标准,即只用整数算法解决问题,而不是将商计算为double,因为在问题陈述中明确拒绝了“双重”解决方案。

那么我们必须计算什么?显然,为了满足我们的规范,同时只保留整数算术,我们需要知道三个事实。首先,什么是整数商?第二,没有剩余部门吗?第三,如果没有,是通过向上或向下舍入计算的整数商?

既然我们有规范和设计,我们就可以开始编写代码了。

public static int DivRoundUp(int dividend, int divisor){
  if (divisor == 0 ) throw ...
  if (divisor == -1 && dividend == Int32.MinValue) throw ...
  int roundedTowardsZeroQuotient = dividend / divisor;
  bool dividedEvenly = (dividend % divisor) == 0;
  if (dividedEvenly) 
    return roundedTowardsZeroQuotient;

  // At this point we know that divisor was not zero 
  // (because we would have thrown) and we know that 
  // dividend was not zero (because there would have been no remainder)
  // Therefore both are non-zero.  Either they are of the same sign, 
  // or opposite signs. If they're of opposite sign then we rounded 
  // UP towards zero so we're done. If they're of the same sign then 
  // we rounded DOWN towards zero, so we need to add one.

  bool wasRoundedDown = ((divisor > 0) == (dividend > 0));
  if (wasRoundedDown) 
    return roundedTowardsZeroQuotient + 1;
  else
    return roundedTowardsZeroQuotient;}

这个聪明吗?不,很美?不,短?没有。根据规格正确吗?我相信,但我还没有完全测试过它。虽然它看起来很不错。

我们这里是专业人士; 使用良好的工程实践。研究您的工具,指定所需的行为,首先考虑错误情况,并编写代码以强调其明显的正确性。当你发现一个bug时,在你随机开始交换比较方向并破坏已经有效的东西之前,先考虑一下你的算法是否存在严重缺陷。


查看完整回答
反对 回复 2019-07-23
?
梵蒂冈之花

TA贡献1900条经验 获得超5个赞

最终的基于int的答案

对于有符号整数:

int div = a / b;if (((a ^ b) >= 0) && (a % b != 0))
    div++;

对于无符号整数:

int div = a / b;if (a % b != 0)
    div++;

这个答案的原因

整数除法' /'被定义为舍入为零(规范的7.7.2),但我们想要四舍五入。这意味着否定答案已经正确舍入,但需要调整肯定答案。

非零肯定答案很容易被发现,但是零答案有点棘手,因为这可能是负值的四舍五入或者是正值的四舍五入。

最安全的选择是通过检查两个整数的符号是否相同来检测答案何时应为正。^在这种情况下,对两个值的整数xor运算符' '将导致0符号位,这意味着非负结果,因此检查(a ^ b) >= 0确定在舍入之前结果应为正。另请注意,对于无符号整数,每个答案显然都是正数,因此可以省略此检查。

剩下的唯一检查是否发生任何舍入,为此a % b != 0将完成工作。

得到教训

算术(整数或其他)并不像看起来那么简单。始终谨慎思考。

此外,虽然我的最终答案可能不像浮点回答那样“简单”或“明显”或者甚至“快速”,但它对我来说具有非常强大的救赎品质; 我现在已经通过答案进行了推理,所以我确定它是正确的(直到有人更聪明地告诉我 - 在Eric的方向偷偷地看一眼 - )。

为了得到浮点答案的确定性,我必须做更多(可能更复杂)的思考是否存在浮点精度可能会妨碍的任何条件,以及是否Math.Ceiling可能在'恰到好处'的投入上不受欢迎的东西。

走过的路

更换(注意我更换了第二myInt1myInt2,假设这是你的意思):

(int)Math.Ceiling((double)myInt1 / myInt2)

有:

(myInt1 - 1 + myInt2) / myInt2

唯一需要注意的是,如果myInt1 - 1 + myInt2溢出您正在使用的整数类型,您可能无法得到您期望的结果。

原因这是错误的:-1000000和3999应该给-250,这给出-249

编辑:
考虑到这与负值的其他整数解决方案具有相同的错误myInt1,可能更容易做类似的事情:

int rem;int div = Math.DivRem(myInt1, myInt2, out rem);if (rem > 0)
  div++;

这应该div只使用整数运算给出正确的结果。

原因这是错误的:-1和-5应该给1,这给出0

编辑(再一次,有感觉):
除法运算符向零舍入; 对于负面结果,这是完全正确的,因此只有非负面结果需要调整。还考虑到DivRem只做了a /和a %,让我们跳过调用(从简单的比较开始,以避免在不需要时进行模数计算):

int div = myInt1 / myInt2;if ((div >= 0) && (myInt1 % myInt2 != 0))
    div++;

原因这是错误的:-1和5应该给0,这给出1

(在我自己的最后一次尝试的辩护中,我不应该尝试一个合理的答案,而我的头脑告诉我,我睡了2个小时)


查看完整回答
反对 回复 2019-07-23
?
慕雪6442864

TA贡献1812条经验 获得超5个赞

到目前为止,所有答案似乎都过于复杂。

在C#和Java中,对于正红利和除数,您只需要:

( dividend + divisor - 1 ) / divisor

资料来源:编号转换,Roland Backhouse,2001年


查看完整回答
反对 回复 2019-07-23
  • 3 回答
  • 0 关注
  • 1146 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信