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

Question

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

Answer 1

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

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