当前位置： 文江博客话题详情

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

发布于 2024-09-28 20:47:27 字数 199 浏览 8 评论 0原文

我（作为一名数学家）对 C 派生语言的一大厌恶是，

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

fmodf(-1,8) // fails similarly

什么是最好的解决方案？

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

原文

One of my pet hates of C-derived languages (as a mathematician) is that

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

fmodf(-1,8) // fails similarly

What's the best solution?

C++ allows the possibility of templates and operator overloading, but both of these are murky waters for me. examples gratefully received.

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（16）

妄想挽回 2024-10-05 20:47:27

首先，我想指出的是，您甚至不能依赖 (-1) % 8 == -1 的事实。您唯一可以信赖的是 (x / y) * y + ( x % y) == x。然而余数是否为负是由实现定义的。

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

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

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

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

First of all I'd like to note that you cannot even rely on the fact that (-1) % 8 == -1. the only thing you can rely on is that (x / y) * y + ( x % y) == x. However whether or not the remainder is negative is implementation-defined.

Reference: C++03 paragraph 5.6 clause 4:

The binary / operator yields the quotient, and the binary % operator yields the remainder from the division of the first expression by the second. If the second operand of / or % is zero the behavior is undefined; otherwise (a/b)*b + a%b is equal to a. If both operands are nonnegative then the remainder is nonnegative; if not, the sign of the remainder is implementation-defined.

Here it follows a version that handles both negative operands so that the result of the subtraction of the remainder from the divisor can be subtracted from the dividend so it will be floor of the actual division. mod(-1,8) results in 7, while mod(13, -8) is -3.

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;
}
回复 原文
自此以后，行同陌路 2024-10-05 20:47:27

这是一个处理两个操作数的正或负整数或小数值的 C 函数，从

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

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

我将此代码用于非 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 mod -2.0 = -0.2

Here is a C function that handles positive OR negative integer OR fractional values for BOTH OPERANDS

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

This is surely the most elegant solution from a mathematical standpoint. However, I'm not sure if it is robust in handling integers. Sometimes floating point errors creep in when converting int -> fp -> int.

I am using this code for non-int s, and a separate function for int.

NOTE: need to trap N = 0!

Tester code:

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

(Note: You can compile and run it straight out of CodePad: http://codepad.org/UOgEqAMA)

Output:

fmodf(-10.2, 2.0) = -0.20 == FAIL!

10.2 mod 2.0 = 0.2
10.2 mod -2.0 = -1.8
-10.2 mod 2.0 = 1.8
-10.2 mod -2.0 = -0.2

回复 原文
孤独陪着我 2024-10-05 20:47:27

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

我敢打赌这是它在 ANSI C & 中的正式名称。 C++ 规范，以及术语的滥用已经悄然出现。有人知道这一事实吗？

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

I have just noticed that Bjarne Stroustrup labels % as the remainder operator, not the modulo operator.

I would bet that this is its formal name in the ANSI C & C++ specifications, and that abuse of terminology has crept in. Does anyone know this for a fact?

But if this is the case then C's fmodf() function (and probably others) are very misleading. they should be labelled fremf(), etc

回复 原文
も星光 2024-10-05 20:47:27

求正模数的最简单的通用函数是这样的：
它适用于 x 的正值和负值。

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

The simplest general function to find the positive modulo would be this-
It would work on both positive and negative values of x.

int modulo(int x,int N){
    return (x % N + N) %N;
}
回复 原文
━╋う一瞬間旳綻放 2024-10-05 20:47:27

对于整数来说，这很简单。只要做

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

我假设 N 是正数并且可以用 x 类型表示的地方即可。您最喜欢的编译器应该能够对此进行优化，这样它最终只会在汇编器中进行一次 mod 操作。

For integers this is simple. Just do

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

where I am supposing that N is positive and representable in the type of x. Your favorite compiler should be able to optimize this out, such that it ends up in just one mod operation in assembler.

回复 原文
如歌彻婉言 2024-10-05 20:47:27

这是一个老问题的新答案，基于此 微软研究论文及其参考文献。

请注意，从 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（请参阅此问答了解源代码）。

对于截断除法，余数的符号等于被除数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);

欧几里得除法，余数的符号始终为非负。

Here's a new answer to an old question, based on this Microsoft Research paper and references therein.

Note that from C11 and C++11 onwards, the semantics of div has become truncation towards zero (see [expr.mul]/4). Furthermore, for D divided by d, C++11 guarantees the following about the quotient qT and remainder 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);

where signum maps to -1, 0, +1, depending on whether its argument is <, ==, > than 0 (see this Q&A for source code).

With truncated division, the sign of the remainder is equal to the sign of the dividend D, i.e. -1 % 8 == -1. C++11 also provides a std::div function that returns a struct with members quot and rem according to truncated division.

There are other definitions possible, e.g. so-called floored division can be defined in terms of the builtin truncated division

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

With floored division, the sign of the remainder is equal to the sign of the divisor d. In languages such as Haskell and Oberon, there are builtin operators for floored division. In C++, you'd need to write a function using the above definitions.

Yet another way is Euclidean division, which can also be defined in terms of the builtin truncated division

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

With Euclidean division, the sign of the remainder is always non-negative.

回复 原文
滥情稳全场 2024-10-05 20:47:27

对于数学家来说，最好的解决方案是使用 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 具有相同的约束，即它是有符号类型。


1 因为 Python 的整数除法向负无穷大舍入。

The best solution ¹for a mathematician is to use Python.

C++ operator overloading has little to do with it. You can't overload operators for built-in types. What you want is simply a function. Of course you can use C++ templating to implement that function for all relevant types with just 1 piece of code.

The standard C library provides fmod, if I recall the name correctly, for floating point types.

For integers you can define a C++ function template that always returns non-negative remainder (corresponding to Euclidian division) as ...

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

... and just write mod(a, b) instead of a%b.

Here the type Integer needs to be a signed integer type.

If you want the common math behavior where the sign of the remainder is the same as the sign of the divisor, then you can do e.g.

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

… with the same constraint on Integer, that it's a signed type.


¹ Because Python's integer division rounds towards negative infinity.

回复 原文
妥活 2024-10-05 20:47:27

哦，我也讨厌这样的 % 设计....

您可以将被除数转换为无符号，如下所示：

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

result = (offset + dividend) % divider

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

有一种特殊情况，其中除数为 2N（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 通常很慢。

Oh, I hate % design for this too....

You may convert dividend to unsigned in a way like:

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

result = (offset + dividend) % divider

where offset is closest to (-INT_MIN) multiple of module, so adding and subtracting it will not change modulo. Note that it have unsigned type and result will be integer. Unfortunately it cannot correctly convert values INT_MIN...(-offset-1) as they cause arifmetic overflow. But this method have advandage of only single additional arithmetic per operation (and no conditionals) when working with constant divider, so it is usable in DSP-like applications.

There's special case, where divider is 2N (integer power of two), for which modulo can be calculated using simple arithmetic and bitwise logic as

dividend&(divider-1)

for example

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

More common and less tricky way is to get modulo using this function (works only with positive divider):

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

This just correct result if it is negative.

Also you may trick:

(p%q + q)%q

It is very short but use two %-s which are commonly slow.

回复 原文
远昼 2024-10-05 20:47:27

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

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

I believe another solution to this problem would be use to variables of type long instead of int.

I was just working on some code where the % operator was returning a negative value which caused some issues (for generating uniform random variables on [0,1] you don't really want negative numbers :) ), but after switching the variables to type long, everything was running smoothly and the results matched the ones I was getting when running the same code in python (important for me as I wanted to be able to generate the same "random" numbers across several platforms.

回复 原文
分開簡單 2024-10-05 20:47:27

对于不使用分支且仅使用 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);
}

For a solution that uses no branches and only 1 mod, you can do the following

// 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);
}
回复 原文
调妓 2024-10-05 20:47:27
/* Warning: macro mod evaluates its arguments' side effects multiple times. */
#define mod(r,m) (((r) % (m)) + ((r)<0)?(m):0)

...或者只是习惯于获得同等类别的任何代表。

/* Warning: macro mod evaluates its arguments' side effects multiple times. */
#define mod(r,m) (((r) % (m)) + ((r)<0)?(m):0)

... or just get used to getting any representative for the equivalence class.

回复 原文
我ぃ本無心為│何有愛 2024-10-05 20:47:27

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++ 行为作为股息（分子）（相当于四舍五入到零）。

Example template for C++

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

With this template, the returned remainder will be zero or have the same sign as the divisor (denominator) (the equivalent of rounding towards negative infinity), instead of the C++ behavior of the remainder being zero or having the same sign as the dividend (numerator) (the equivalent of rounding towards zero).

回复 原文
爱要勇敢去追 2024-10-05 20:47:27
unsigned mod(int a, unsigned b) {
    return (a >= 0 ? a % b : b - (-a) % b);
}

unsigned mod(int a, unsigned b) {
    return (a >= 0 ? a % b : b - (-a) % b);
}
回复 原文
东风软 2024-10-05 20:47:27

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

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

This solution (for use when mod is positive) avoids taking negative divide or remainder operations all together:

int core_modulus(int val, int mod)
{
    if(val>=0)
        return val % mod;
    else
        return val + mod * ((mod - val - 1)/mod);
}
回复 原文
我家小可爱 2024-10-05 20:47:27
define  MOD(a, b)       ((((a)%(b))+(b))%(b))

define  MOD(a, b)       ((((a)%(b))+(b))%(b))
回复 原文
皓月长歌 2024-10-05 20:47:27

我会这样做：

((-1)+8) % 8

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

I would do:

((-1)+8) % 8

This adds the latter number to the first before doing the modulo giving 7 as desired. This should work for any number down to -8. For -9 add 2*8.

回复 原文
~没有更多了~

关于作者

恋竹姑娘

暂无简介

0 文章
0 评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

胡图图

文章 0 评论 0

zt006

文章 0 评论 0

z祗昰~

文章 0 评论 0

冰葑

文章 0 评论 0

野の

文章 0 评论 0

天空

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文