wake-up-neo.com

Codieren eines Modulo-Operators (%) in C / C ++ / Obj-C, der negative Zahlen verarbeitet

Einer meiner Lieblingshasse von C-abgeleiteten Sprachen (als Mathematiker) ist das

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

fmodf(-1,8) // fails similarly

Was ist die beste Lösung?

C++ erlaubt die Möglichkeit von Vorlagen und das Überladen von Operatoren, aber beide sind für mich trübe Gewässer. Beispiele dankbar erhalten.

79
P i

Zunächst möchte ich festhalten, dass Sie sich nicht einmal darauf verlassen können, dass (-1) % 8 == -1. das einzige worauf du dich verlassen kannst ist, dass (x / y) * y + ( x % y) == x. Ob der Rest negativ ist oder nicht, ist implementierungsspezifisch .

Warum hier Vorlagen verwenden? Eine Überlastung für Ints und Longs würde ausreichen.

int mod (int a, int b)
{
   int ret = a % b;
   if(ret < 0)
     ret+=b;
   return ret;
}

und jetzt kannst du es wie mod (-1,8) nennen und es wird 7 erscheinen.

Bearbeiten: Ich habe einen Fehler in meinem Code gefunden. Es wird nicht funktionieren, wenn b negativ ist. Also ich denke das ist besser:

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

Verweis: C++ 03 Absatz 5.6 Satz 4:

Der binäre Operator liefert den Quotienten und der binäre Operator% den Rest aus der Division des ersten Ausdrucks durch den zweiten. Wenn der zweite Operand von/oder% Null ist, ist das Verhalten undefiniert. ansonsten ist (a/b) * b + a% b gleich a. Wenn beide Operanden nicht negativ sind, ist der Rest nicht negativ. Wenn nicht, ist das Vorzeichen des Rests implementierungsdefiniert .

72
Armen Tsirunyan

Hier ist eine C-Funktion, die positive OR negative Ganzzahlen OR Bruchzahlen für BEIDE OPERANDEN behandelt

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

Dies ist aus mathematischer Sicht sicherlich die eleganteste Lösung. Ich bin mir jedoch nicht sicher, ob es robust im Umgang mit ganzen Zahlen ist. Manchmal schleichen sich Gleitkommafehler bei der Konvertierung von int -> fp -> int ein.

Ich benutze diesen Code für nicht int s und eine separate Funktion für int.

HINWEIS: Muss N = 0 abfangen!

Testercode:

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

(Hinweis: Sie können es direkt aus CodePad kompilieren und ausführen: http://codepad.org/UOgEqAMA )

Ausgabe:

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

11
P i

Ich habe gerade bemerkt, dass Bjarne Stroustrup % als Rest Operator, nicht der Modulo Operator.

Ich würde wetten, dass dies der formale Name in den ANSI C & C++ - Spezifikationen ist und dass sich ein Missbrauch der Terminologie eingeschlichen hat. Kennt jemand dies für eine Tatsache?

Aber wenn dies der Fall ist, dann sind die fmodf () -Funktionen von C (und wahrscheinlich auch andere) sehr irreführend. sie sollten mit fremf () usw. beschriftet sein

7
P i

Für ganze Zahlen ist dies einfach. Mach einfach

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

wo ich nehme, dass N positiv und in der Art von x darstellbar ist. Ihr bevorzugter Compiler sollte dies optimieren können, so dass es in Assembler nur zu einer Mod-Operation kommt.

5
Jens Gustedt

Die einfachste allgemeine Funktion, um das positive Modulo zu finden, wäre diese: Sie würde sowohl mit positiven als auch mit negativen Werten von x arbeiten.

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

Die beste Lösung für einen Mathematiker ist die Verwendung von Python.

Das Überladen von C++ - Operatoren hat wenig damit zu tun. Sie können Operatoren für integrierte Typen nicht überladen. Was Sie wollen, ist einfach eine Funktion. Natürlich können Sie C++ - Vorlagen verwenden, um diese Funktion für alle relevanten Typen mit nur 1 Codeteil zu implementieren.

Die Standard-C-Bibliothek bietet fmod für Gleitkommatypen, wenn ich mich richtig erinnere.

Für Ganzzahlen können Sie eine C++ - Funktionsvorlage definieren, die immer einen nicht negativen Rest (entsprechend der Euklidischen Division) zurückgibt als ...

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

... und schreibe einfach mod(a, b) anstelle von a%b.

Hier muss der Typ Integer ein ganzzahliger Typ mit Vorzeichen sein.

Wenn Sie das allgemeine mathematische Verhalten wünschen, bei dem das Vorzeichen des Rests mit dem Vorzeichen des Divisors identisch ist, können Sie z.

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

… Mit der gleichen Einschränkung für Integer, dass es sich um einen signierten Typ handelt.


¹ Weil sich die Ganzzahldivision von Python gegen negative Unendlichkeit rundet.

Oh, ich hasse% Design auch dafür ....

Sie können Dividenden auf folgende Weise in nicht signierte konvertieren:

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

result = (offset + dividend) % divider

wenn der Versatz dem (-INT_MIN) Vielfachen des Moduls am nächsten liegt, wird durch Hinzufügen und Subtrahieren das Modulo nicht geändert. Beachten Sie, dass es vorzeichenlosen Typ hat und das Ergebnis eine Ganzzahl ist. Leider können die Werte INT_MIN ... (- offset-1) nicht korrekt konvertiert werden, da sie einen arifmetischen Überlauf verursachen. Diese Methode hat jedoch den Vorteil, dass nur eine einzige zusätzliche Arithmetik pro Operation (und keine Bedingungen) beim Arbeiten mit einem konstanten Teiler vorhanden ist, sodass sie in DSP-ähnlichen Anwendungen verwendet werden kann.

Es gibt einen Sonderfall, bei dem der Teiler 2 istN (ganzzahlige Zweierpotenz), für die Modulo mit einfacher Arithmetik und bitweiser Logik berechnet werden kann

dividend&(divider-1)

beispielsweise

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

Häufiger und weniger knifflig ist es, Modulo mit dieser Funktion zu erhalten (funktioniert nur mit positivem Teiler):

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

Dies ist genau das richtige Ergebnis, wenn es negativ ist.

Auch können Sie betrügen:

(p% q + q)% q

Es ist sehr kurz, aber verwenden Sie zwei% -s, die normalerweise langsam sind.

2
Vovanium

Ich glaube, eine andere Lösung für dieses Problem wäre die Verwendung von Variablen vom Typ long anstelle von int.

Ich habe gerade an einem Code gearbeitet, bei dem der% -Operator einen negativen Wert zurückgab, der einige Probleme verursachte (zum Erzeugen einheitlicher Zufallsvariablen auf [0,1] möchten Sie eigentlich keine negativen Zahlen :)), aber nach dem Umschalten der Variablen auf Typ Long, alles lief reibungslos und die Ergebnisse stimmten mit denen überein, die ich beim Ausführen des gleichen Codes in python (wichtig für mich, da ich die gleichen "Zufallszahlen" generieren wollte über mehrere Plattformen.

2
david

Hier ist eine neue Antwort auf eine alte Frage, basierend auf diesem Microsoft Research Paper und den darin enthaltenen Referenzen.

Beachten Sie, dass ab C11 und C++ 11 die Semantik von div zu einer Kürzung in Richtung Null geworden ist (siehe [expr.mul]/4). Außerdem garantiert C++ 11 für D geteilt durch d Folgendes über den Quotienten qT und den Rest 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));

dabei ist signum -1, 0, +1 zugeordnet, je nachdem, ob sein Argument <, ==> als 0 ist (siehe diese F & A für den Quellcode).

Bei abgeschnittener Division ist das Vorzeichen des Restes gleich dem Vorzeichen der Dividende D, d. H. -1 % 8 == -1. C++ 11 bietet auch ein std::div Funktion, die eine Struktur mit Mitgliedern quot und rem entsprechend der abgeschnittenen Division zurückgibt.

Es sind andere Definitionen möglich, z. Eine sogenannte geschossige Unterteilung kann in Bezug auf die eingebaute abgeschnittene Unterteilung definiert werden

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

Bei einer geschossweisen Division ist das Vorzeichen des Restes gleich dem Vorzeichen des Divisors d. In Sprachen wie Haskell und Oberon gibt es eingebaute Operatoren für die Unterteilung von Fußböden. In C++ müssen Sie eine Funktion mit den obigen Definitionen schreiben.

Ein weiterer Weg ist die euklidische Division , die auch durch die eingebaute verkürzte Division definiert werden kann

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) != -1);

Bei der euklidischen Division ist das Vorzeichen des Restes immer positiv .

1
TemplateRex
/* Warnung: Der Makro-Mod wertet die Nebenwirkungen seiner Argumente mehrmals aus. */
 # definiere mod (r, m) (((r)% (m)) + ((r) <0)? (m): 0) 

... oder gewöhnen Sie sich einfach daran, einen Vertreter für die Äquivalenzklasse zu finden.

1
Eric Towers

Beispielvorlage für C++

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

Bei dieser Vorlage ist der zurückgegebene Rest Null oder hat das gleiche Vorzeichen wie der Divisor (Nenner) (das Äquivalent der Rundung gegen die negative Unendlichkeit), anstatt dass das C++ - Verhalten des Restes Null ist oder das gleiche Vorzeichen wie der Dividend hat ( Zähler) (das Äquivalent der Rundung auf Null).

0
rcgldr