C#中的整数除法向下取整（负数情况）

Question

有没有一种方法可以在C#中进行整数除法（不使用浮点或十进制数，我需要保持速度很快），并向下舍入数字？

默认的除法只是舍弃小数部分。请考虑：

 1 / 2 = 0 // That is correct
-1 / 2 = 0 // ... but I want to get (-1) here!

我的部门将采用正数和负数作为除数。我无需使用if语句，因为分支会太耗费时间（该操作在实时游戏引擎中将频繁运行）...

- PiotrK

---

在将负数除以它之前，从中减去1（对于非负数不要这样做）。 - user2819245

@elgonzo 我不知道这个数字是否为负数。它可以是正数也可以是负数。 - PiotrK

@elgonzo 我需要 if 或其他分支形式，但这是非常昂贵的操作。 - PiotrK

“floating for int.max”是什么意思？浮点数和整数一样只由1和0组成。我能理解你不想使用"Decimal"，但浮点数和双精度浮点数也不会减缓运行速度。 - Crowcoder

@elgonzo 哦，这个不错！你能把它发表为答案吗？ - PiotrK

Answer 1

除以2可以通过移位操作实现。在@elgonzo（已被删除）提到了C#的右移特性后，我决定查看它是如何工作的，并且它似乎正是你想要的：

var result = number >> 1;

以下是结果：

11 -> 5
10 -> 5
2 -> 1
1 -> 0
-1 -> -1
-2 -> -1
-32 -> -16
-33 -> -17

int.MaxValue和MinValue也适用。

就性能而言，这似乎比当前已接受的使用模数运算符的答案快近两倍。 在我的计算机上，将（同样的）100000000个随机数除以一个简单的右移花费2.17秒，而使用具有模数的版本需要花费3.1至4.0秒。

分支版本似乎执行速度与模数版本相同：明显比简单的右移慢。

- oerkelens

---

哎呀！看不到树林只因为眼前的树木太多了。这里，送你我的点赞。（值得一提的是，我已删除了过于复杂的答案，以免分散大家对解决方案简洁性的注意力。嘿，我可以把这归咎于周末吗？;-P） - user2819245

@elgonzo 嗯，你确实为我指明了正确的方向，谢谢你:) - oerkelens

Answer 2

如果您想将a除以b：

不会因溢出而失败的方法：

int res = a / b;
return (a < 0 && a != b * res) ? res - 1 : res;

以下方法可能会因为负溢出而失败。

int mod = a % b;
if (mod < 0) {
  mod += b;
}
return (a - mod) / b;

因为`a % b`可能是负数，所以在使用`mod +=b`时会出现问题。 更简洁的写法：

return (a - (a % b + b) % b) / b;

还有更加清晰的解释：

return a >= 0 ? a / b : (a - b + 1) / b;

- user2956272

---

我刚刚明白了负溢出的风险。 - user2956272

请注意，在考虑 CPU 分支预测能力时，模数运算可能比简单分支更加昂贵（尽管对于某些最近的 CPU 漏洞（如 Spectre/Meltdown）的缓解措施可能会对分支预测性能增益产生影响）。 - user2819245

有三个版本使用分支，第四个版本使用2个模运算。我建议测试性能... - oerkelens

经过测试，看起来所有这些选项都比简单的n>>1慢得多，而完成同样的工作。 - oerkelens

@oerkelens，当然。但是n >> 1只能被2整除。您需要处理其他整数。 - user2956272

我不确定是否是这种情况（OP似乎对此有些不太清楚）。但如果是这种情况，OP对分支的厌恶似乎是没有根据的，因为它并不比其他选择表现更好 :) - oerkelens