c++ - C ++中的欧几里得整数模

Question

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

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);
}

Answer 2

试试(x%m + m)%m结果是否一定是肯定的。

围绕这个或任何变体编写你自己的函数，并且不要挂在库上——你花费的时间比你想做的要多。为您需要的简单功能启动您自己的库（工具箱）。

Answer 3

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

5 % 4 为 1，以此类推。

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

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

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)))