c++ - 如何在处理负数的 C/C++/Obj-C 中编写模 (%) 运算符

Question

我最讨厌 C 派生语言（作为数学家）之一是

(-1) % 8 // comes out as -1, and not 7

fmodf(-1,8) // fails similarly

最好的解决方案是什么？

C++ 允许模板和运算符重载的可能性，但对我来说，这两者都是浑水。收到的例子很感激。

Answer 1

首先，我想指出，您甚至不能依赖(-1) % 8 == -1. 你唯一可以依靠的就是那个(x / y) * y + ( x % y) == x。但是，余数是否为负是实现定义的。

参考：C++03 第 5.6 段第 4 条：

二元 / 运算符产生商，二元 % 运算符产生第一个表达式除以第二个表达式的余数。如果 / 或 % 的第二个操作数为零，则行为未定义；否则 (a/b)*b + a%b 等于 a。如果两个操作数都是非负数，则余数是非负数；如果不是，则余数的符号是​​ implementation-defined。

这里它遵循一个处理两个负操作数的版本，以便从除数中减去余数的结果可以从被除数中减去，因此它将是实际除法的下限。结果为 7，而为 -3。mod(-1,8)mod(13, -8)

int mod(int a, int b)
{
   if(b < 0) //you can check for b == 0 separately and do what you want
     return -mod(-a, -b);   
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}

Answer 2

这是一个 C 函数，用于处理 BOTH OPERANDS 的正整数或负整数或小数值

#include <math.h>
float mod(float a, float N) {return a - N*floor(a/N);} //return in range [0, N)

从数学的角度来看，这无疑是最优雅的解决方案。但是，我不确定它在处理整数方面是否稳健。有时在转换 int -> fp -> int 时会出现浮点错误。

我将此代码用于非 int s，并为 int 使用单独的函数。

注意：需要捕获 N = 0！

测试代码：

#include <math.h>
#include <stdio.h>

float mod(float a, float N)
{
    float ret = a - N * floor (a / N);

    printf("%f.1 mod %f.1 = %f.1 \n", a, N, ret);

    return ret;
}

int main (char* argc, char** argv)
{
    printf ("fmodf(-10.2, 2.0) = %f.1  == FAIL! \n\n", fmodf(-10.2, 2.0));

    float x;
    x = mod(10.2f, 2.0f);
    x = mod(10.2f, -2.0f);
    x = mod(-10.2f, 2.0f);
    x = mod(-10.2f, -2.0f);

    return 0;
}

（注意：您可以直接从 CodePad 编译和运行它：http: //codepad.org/UOgEqAMA）

输出：

fmodf(-10.2, 2.0) = -0.20 == 失败！

10.2 模 2.0 = 0.2
10.2 模 -2.0 = -1.8
-10.2 模 2.0 = 1.8
-10.2 模 -2.0 = -0.2

Answer 3

我刚刚注意到 Bjarne Stroustrup 将其标记%为余数运算符，而不是模运算符。

我敢打赌，这是它在 ANSI C 和 C++ 规范中的正式名称，并且滥用术语已经蔓延开来。有人知道这是事实吗？

但如果是这种情况，那么 C 的 fmodf() 函数（可能还有其他函数）非常具有误导性。它们应该被标记为 fremf() 等

Answer 4

找到正模的最简单的通用函数是this-它适用于x的正值和负值。

int modulo(int x,int N){
    return (x % N + N) %N;
}

Answer 5

对于整数，这很简单。做就是了

(((x < 0) ? ((x % N) + N) : x) % N)

我认为这N是积极的并且在类型中具有代表性x。您最喜欢的编译器应该能够对此进行优化，这样它最终只需要在汇编程序中进行一次 mod 操作。

Answer 6

对于数学家来说，最好的解决方案是使用 Python。

C++ 运算符重载与它无关。您不能为内置类型重载运算符。你想要的只是一个函数。当然，您可以使用 C++ 模板为所有相关类型实现该功能，只需 1 段代码。

如果我没记错名称，标准 C 库提供fmod浮点类型。

对于整数，您可以定义一个始终返回非负余数（对应于欧几里得除法）的 C++ 函数模板...

#include <stdlib.h>  // abs

template< class Integer >
auto mod( Integer a, Integer b )
    -> Integer
{
    Integer const r = a%b;
    return (r < 0? r + abs( b ) : r);
}

...并且只写mod(a, b)而不是a%b.

这里类型Integer需要是有符号整数类型。

如果您想要余数的符号与除数的符号相同的常见数学行为，那么您可以执行例如

template< class Integer >
auto floor_div( Integer const a, Integer const b )
    -> Integer
{
    bool const a_is_negative = (a < 0);
    bool const b_is_negative = (b < 0);
    bool const change_sign  = (a_is_negative != b_is_negative);

    Integer const abs_b         = abs( b );
    Integer const abs_a_plus    = abs( a ) + (change_sign? abs_b - 1 : 0);

    Integer const quot = abs_a_plus / abs_b;
    return (change_sign? -quot : quot);
}

template< class Integer >
auto floor_mod( Integer const a, Integer const b )
    -> Integer
{ return a - b*floor_div( a, b ); }

... 具有相同的约束Integer，它是有符号类型。

---

^{¹ 因为 Python 的整数除法向负无穷大舍入。}

Answer 7

这是一个老问题的新答案，基于这篇Microsoft Research 论文和其中的参考资料。

请注意，从 C11 和 C++11 开始， 的语义div已变为向零截断（请参阅参考资料[expr.mul]/4）。此外，对于D除以d，C++11 保证以下关于商qT和余数rT

auto const qT = D / d;
auto const rT = D % d;
assert(D == d * qT + rT);
assert(abs(rT) < abs(d));
assert(signum(rT) == signum(D) || rT == 0);

其中signum映射到 -1、0、+1，具体取决于其参数是否为 <、==、> 而不是 0（有关源代码，请参阅此 Q&A）。

对于截断除法，余数的符号等于被除数的符号D，即-1 % 8 == -1。C++11 还提供了一个函数，该函数根据截断除法std::div返回一个带有成员的结构quot。rem

还有其他可能的定义，例如可以根据内置的截断除法来定义所谓的下限除法

auto const I = signum(rT) == -signum(d) ? 1 : 0;
auto const qF = qT - I;
auto const rF = rT + I * d;
assert(D == d * qF + rF);
assert(abs(rF) < abs(d));
assert(signum(rF) == signum(d));

使用地板除法，余数的符号等于除数的符号d。在 Haskell 和 Oberon 等语言中，有用于底除法的内置运算符。在 C++ 中，您需要使用上述定义编写一个函数。

还有一种方法是欧几里得除法，也可以根据内置的截断除法来定义

auto const I = rT >= 0 ? 0 : (d > 0 ? 1 : -1);
auto const qE = qT - I;
auto const rE = rT + I * d;
assert(D == d * qE + rE);
assert(abs(rE) < abs(d));
assert(signum(rE) >= 0);

使用欧几里得除法，余数的符号总是非负的。

Answer 8

哦，我也讨厌为此设计%....

您可以通过以下方式将股息转换为无符号：

unsigned int offset = (-INT_MIN) - (-INT_MIN)%divider

result = (offset + dividend) % divider

其中 offset 最接近模块的 (-INT_MIN) 倍数，因此加减它不会改变模数。请注意，它具有无符号类型，结果将是整数。不幸的是，它无法正确转换值 INT_MIN...(-offset-1)，因为它们会导致 arifmetic 溢出。但是这种方法在使用常量除法器时每个操作只有一个附加算术（并且没有条件）具有优势，因此它可用于类似 DSP 的应用程序中。

有一种特殊情况，除数为 2 ^N（2 的整数幂），可以使用简单的算术和按位逻辑计算模数

dividend&(divider-1)

例如

x mod 2 = x & 1
x mod 4 = x & 3
x mod 8 = x & 7
x mod 16 = x & 15

更常见且不那么棘手的方法是使用此函数获取模数（仅适用于正除法器）：

int mod(int x, int y) {
    int r = x%y;
    return r<0?r+y:r;
}

如果结果是否定的，这只是正确的结果。

你也可以欺骗：

(p%q + q)%q

它很短，但使用了两个通常很慢的 %-s。

Answer 9

我相信这个问题的另一种解决方案是使用 long 而不是 int 类型的变量。

我只是在处理一些代码，其中 % 运算符返回一个负值，这导致了一些问题（为了在 [0,1] 上生成统一的随机变量，你真的不想要负数:)），但是在将变量切换为输入long，一切运行顺利，结果与我在python中运行相同代码时得到的结果相匹配（对我来说很重要，因为我希望能够在多个平台上生成相同的“随机”数字。

Answer 10

对于不使用分支且仅使用 1 个 mod 的解决方案，您可以执行以下操作

// Works for other sizes too,
// assuming you change 63 to the appropriate value
int64_t mod(int64_t x, int64_t div) {
  return (x % div) + (((x >> 63) ^ (div >> 63)) & div);
}

Answer 11

/* 警告：宏 mod 多次评估其参数的副作用。*/
#define mod(r,m) (((r) % (m)) + ((r)<0)?(m):0)

...或者只是习惯于为等价类找任何代表。

Answer 12

C++ 的示例模板

template< class T >
T mod( T a, T b )
{
    T const r = a%b;
    return ((r!=0)&&((r^b)<0) ? r + b : r);
}

使用此模板，返回的余数将为零或与除数（分母）具有相同的符号（相当于向负无穷舍入），而不是余数为零或与被除数具有相同符号的 C++ 行为 (分子）（相当于向零舍入）。

Answer 13

define  MOD(a, b)       ((((a)%(b))+(b))%(b))

Answer 14

unsigned mod(int a, unsigned b) {
    return (a >= 0 ? a % b : b - (-a) % b);
}

Answer 15

此解决方案（在mod为正时使用）避免同时进行负除法或余数运算：

int core_modulus(int val, int mod)
{
    if(val>=0)
        return val % mod;
    else
        return val + mod * ((mod - val - 1)/mod);
}

Answer 16

我会做：

((-1)+8) % 8 

这会将后一个数字添加到第一个数字，然后根据需要进行模数 7。这应该适用于低至 -8 的任何数字。为 -9 添加 2*8。