C++中的欧几里得整数取模

Question

我在哪里可以找到一个计算整数欧几里得除法余数的实现或库，0 <= r < |n|？

- NaomiJO

Answer 1

在C++98和C++03版本的C++语言中，内置除法（位/和%运算符）可以是欧几里得除法也可以是非欧几里得除法 - 这是实现定义的。然而，大多数实现将商向零截断，这很不幸是非欧几里得除法。

在大多数实现中，5 / -3 = -1且5 % -3 = -2。在欧几里得除法中，5 / -3 = -2且5 % -3 = 1。

C++11要求整数除法为非欧几里得除法：它要求实现将结果向零截断。

如您所见，问题只出现在负数上。所以，您可以通过使用运算符%并校正负余数来轻松地自行实现欧几里得除法。

int euclidean_remainder(int a, int b)
{
  assert(b != 0);
  int r = a % b;
  return r >= 0 ? r : r + std::abs(b);
}

- AnT stands with Russia

Answer 2

如果结果必须为正数，请尝试使用(x%m + m)%m。

围绕此功能或其任何变体编写自己的函数，并不要因库而卡住——你花在询问上的时间比直接执行它还要长。为您需要的简单函数启动自己的库（工具箱）。

- Richard Sitze

---

是的，这个可以用，谢谢。难道没有实现这个函数的库吗？这似乎是相当常见的... - NaomiJO

由于两个“％”操作涉及整数除法，因此此方法速度过慢。可以构建@AnT答案的无分支版本，它将仅使用单个“％”操作。 - plasmacel

Answer 3

这是一个简单的运算符：%。

例如，5 % 4 的结果为1等等。

编辑： 正如已经指出的那样，根据你的实现，这不一定是欧几里德模。

#define EUCMOD(a, b)  (a < 0 ? (((a % b) + b) % b) : (a % b))

- Brandon

---

请注意，此代码仅适用于整数。如果您需要浮点数模数，请使用“fmod”函数。例如：fmod(3.3, 2.4) 的结果为 0.9。 - chris

不，我说的是欧几里得除法。(-5)%4是-1，但应该是3。正如我在问题中所说，余数r应该在0和n之间，而在我的例子中它是负数。 - NaomiJO

@NaomiJO，如果你真的需要，可以将a％b中的b加到结果上，如果结果是负数。 - chris

这实际上是不正确的。在大多数实现中，除法会将结果截断为零-这是非欧几里得除法。这意味着“％”的结果可能是负数：这已经是非欧几里得的了。 - AnT stands with Russia

由于两个“％”操作涉及整数除法，因此此方法速度过慢。可以构建@AnT答案的无分支版本，它将仅使用单个“％”操作。 - plasmacel

Answer 4

我真的很喜欢布兰登的答案，但我开始遇到一些奇怪的错误。

经过测试，我发现 EUCMOD 宏的扩展会干扰操作的优先级。

因此，我建议将其用作函数而不是宏。

int eucmod(const int a, const int b)
{
    return (a < 0 ? (((a % b) + b) % b) : (a % b));
}

或者加上一些括号

#define EUCMOD(a,b) ((a) < 0 ? ((((a) % (b)) + (b)) % (b)) : ((a) % (b)))

- DieChopper