C++ 中的欧几里德整数模

Question

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

Answer 1

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

在大多数实现中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);
}

Answer 2

围绕这个或任何变体编写你自己的函数，不要沉迷于库——你花在询问上的时间比直接做它的时间还要多。为您需要的简单功能启动您自己的库（工具箱）。