整除向下取整

Question

有没有一种简单、高效且正确的方法（即不涉及转换为/从double）在C#中执行向下取整整数除法（例如，类似于Python提供的{{link1：链接}}）。

换句话说，以下是一个高效的版本，它不会遭受长/双精度转换损失。

(long)(Math.Floor((double) a / b))

或者必须自己实现，例如

static long FlooredIntDiv(long a, long b)
{
    if (a < 0)
    {
        if (b > 0)
            return (a - b + 1) / b;
        // if (a == long.MinValue && b == -1) // see *) below
        //    throw new OverflowException();
    }
    else if (a > 0)
    {
        if (b < 0)
            return (a - b - 1) / b;
    }
    return a / b;
}

*) 尽管 C# 4 规范在除法运算符上 未明确说明 是否在 unchecked 内引发 OverflowException，但实际上它确实会引发（在我的系统上），而且 Visual Studio .NET 2003 版本 甚至强制要求它引发：

如果左操作数是最小的可表示 int 或 long 值，右操作数为 -1，则无论该操作是否发生在 checked 或 unchecked 上下文中，都会在此情况下始终引发 System.OverflowException。

编辑

关于 checked 和 unchecked 的划掉语句都很好，但实际上 checked 只是一个编译时概念，所以无论调用函数的代码是否在 checked 中，我的函数是否应该包装或抛出异常都取决于我。

- Evgeniy Berezovsky

---

你的意思是，有没有其他方法来避免直接将结果传递给 Math.Floor 函数？ - Pierre-Luc Pineault

整数除法已经执行这个操作了，不是字面上调用“Math.Floor”，但结果是一样的，它会切掉整个小数部分。“Math.Floor”在这种情况下是多余的。 - Marko Gresak

@mremp：仅适用于正结果。请参阅 OP 的表格以获取“floor”负结果的示例，这些结果与 C# / 运算符实现不同。 - Peter Duniho

哦，是的@PeterDuniho，我忘了那个…… - Marko Gresak

不是解决方案，但我认为你的代码可能会在某些边缘情况下失败。 var a = long.MinValue; var b = -1L; 或 var a = long.MaxValue; var b = -1L;。 - publicgk

Answer 1

你可以尝试这个：

if (((a < 0) ^ (b < 0)) && (a % b != 0))
{
   return (a/b - 1);
}
else
{
   return (a/b);
}

编辑（在下面的评论中进行了一些讨论）：

如果不使用if-else，我会这样做：

return (a/b - Convert.ToInt32(((a < 0) ^ (b < 0)) && (a % b != 0)));

注意：Convert.ToInt32(bool value) 方法也需要跳转，请参见该方法的实现。

return value? Boolean.True: Boolean.False;

从理论上讲，不可能计算 a = long.MinValue 和 b = -1L 的除法，因为预期的结果是 a/b = abs(long.MinValue) = long.MaxValue + 1 > long.MaxValue。（long 的范围是 –9,223,372,036,854,775,808 到 9,223,372,036,854,775,807。）

- Bhaskar

---

PS: ^ 是异或运算符 - Bhaskar

谢谢L16H7。在实现我的FlooredIntDiv时，我开始采用了与您的解决方案类似的方法，这是同样有效的，我相信它与我的解决方案一样正确（我还没有想过您的解决方案是否能捕获所有的0边界情况），但我选择了if/else路线，因为我认为这更容易阅读。因此，它等效于我的示例实现，但既不更容易也不更有效。 - Evgeniy Berezovsky

通常，一个“高效”的公式不应该使用任何“if”语句或类似的语句。它应该纯粹基于低级算术运算符。 - SF Lee

@L16H7，我只是想说（正如我的问题现在所澄清的那样）- 你和我都没有“错误”的实现-对于打翻苹果车我很抱歉。然而，如果有简单有效的解决方案，我仍然很感兴趣。 - Evgeniy Berezovsky

结果是什么？我也很感兴趣。聊天链接无法使用。 - alelom

Answer 2

您不需要自己实现这个功能，Math类提供了一个内置方法来执行欧几里得除法：Math.DivRem()

唯一的缺点是您必须为余数提供一个可分配的变量：

long remainder;
long quotient = Math.DivRem(a, b, out remainder);

- Mathias R. Jessen

---

Math.DivRem 的返回值与 a / b 相同，因此调用 Math.DivRem 是不必要的。至于 a / b 的问题：如果 a 或 b 为负数，则它不会给出向下取整的结果。 - Evgeniy Berezovsky

Answer 3

在任何正常的编程语言中（遵循我们正常操作顺序的语言），它的工作方式是-1.0/3.0等同于-(1.0/3.0)，即-0.3333...。因此，如果您想将其转换为int，实际上需要考虑的是强制转换/向下取整运算符，而不是除法。因此，如果您想要这种行为，必须使用(int)Math.Floor(a/b)或自定义代码。

- piojo

---

谢谢，我删除了我的回答中的那部分。我在计算物理学中学到的一些概念因滥用而变得混乱，并以不合理的方式重新组合。有关哪些操作的哪些部分应该被转换的规则/指南，旨在由于浮点精度不准确而丢失最少信息，但自从大学以来我就没有真正使用过这些规则，所以已经忘记了具体细节。 - piojo

Answer 4

如果两个参数a和b都是长整型（或任何其他整数类型）

long c = a/b;

在C＃中，向下取整整数除法与Python类似。没有任何需要转换的内容。它甚至在处理器级别上使用适当的整数操作。

所有C＃中的操作都基于它们的类型执行。

- user6110389

---

整数除法向零取整，所以如果a或b为负数，则结果将向上取整而不是向下取整。 - Tim Styles