Come codificare un operatore di modulo (%) in C / C ++ / Obj-C che gestisce numeri negativi

Uno dei miei animali odia le lingue derivate dalla C (come matematico)

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

Qual è la soluzione migliore?

Il C ++ consente la possibilità di modelli e sovraccarico dell’operatore, ma entrambi sono acque torbide per me. esempi ricevuti con gratitudine.

Prima di tutto vorrei sottolineare che non puoi nemmeno contare sul fatto che (-1) % 8 == -1 . l’unica cosa su cui puoi fare affidamento è che (x / y) * y + ( x % y) == x . Tuttavia, se il resto è negativo o meno è definito dall’implementazione .

Ora perché usare i modelli qui? Farebbe un sovraccarico per inte e long.

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

e ora puoi chiamarlo come mod (-1,8) e sembrerà essere 7.

Modifica: ho trovato un bug nel mio codice. Non funzionerà se b è negativo. Quindi penso che sia meglio:

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

Riferimento: C ++ 03 paragrafo 5.6 clausola 4:

L'operatore binario / produce il quoziente e l'operatore binario% restituisce il resto dalla divisione della prima espressione per il secondo. Se il secondo operando di / o% è zero, il comportamento non è definito; altrimenti (a / b) * b + a% b è uguale a a. Se entrambi gli operandi non sono negativi, il resto non è negativo; in caso contrario, il segno del resto è definito dall'implementazione .

Ecco una funzione C che gestisce il valore intero OR negativo o valori frazionali OR per entrambi gli OPERAND

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

Questa è sicuramente la soluzione più elegante dal punto di vista matematico. Tuttavia, non sono sicuro se sia efficace nella gestione degli interi. A volte errori di virgola mobile si insinuano durante la conversione di int -> fp -> int.

Sto usando questo codice per non-int s, e una funzione separata per int.

NOTA: è necessario intercettare N = 0!

Codice del tester:

 #include  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", x); 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; } 

(Nota: puoi compilare ed eseguire direttamente da CodePad: http://codepad.org/UOgEqAMA )

Produzione:

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

Ho appena notato che Bjarne Stroustrup etichetta % come operatore restante , non come operatore modulo.

Scommetto che questo è il suo nome formale nelle specifiche ANSI C & C ++ e che l’abuso di terminologia si è insinuato. Qualcuno lo sa per certo?

Ma se questo è il caso, la funzione di fmodf () di C (e probabilmente di altri) è molto fuorviante. dovrebbero essere etichettati come fremf (), ecc

Per interi questo è semplice. Basta fare

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

dove suppongo che N sia positivo e rappresentabile nel tipo di x . Il tuo compilatore preferito dovrebbe essere in grado di ottimizzarlo, in modo che finisca con una sola operazione di mod in assembler.

La migliore soluzione per un matematico è usare Python.

L’overloading dell’operatore C ++ ha poco a che fare con questo. Non è ansible sovraccaricare gli operatori per i tipi predefiniti. Quello che vuoi è semplicemente una funzione. Naturalmente puoi usare il template C ++ per implementare quella funzione per tutti i tipi rilevanti con solo 1 pezzo di codice.

La libreria C standard fornisce fmod , se richiamo il nome correttamente, per i tipi a virgola mobile.

Per i numeri interi è ansible definire un modello di funzione C ++ che restituisce sempre un resto non negativo (corrispondente alla divisione euclidea) come …

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

... e basta scrivere mod(a, b) invece di a%b .

Qui il tipo Integer deve essere un tipo intero con segno.

Se vuoi il comportamento matematico comune in cui il segno del resto è uguale al segno del divisore, allora puoi fare ad esempio

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

... con lo stesso vincolo su Integer , che è un tipo firmato.


¹ Perché la divisione intera di Python arrotonda all'infinito negativo.

La più semplice funzione generale per trovare il modulo positivo sarebbe questa: funzionerebbe su entrambi i valori positivi e negativi di x.

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

Oh, odio% design anche per questo ….

Puoi convertire il dividendo in unsigned in un modo come:

 unsigned int offset = (-INT_MIN) - (-INT_MIN)%divider result = (offset + dividend) % divider 

dove offset è più vicino a (-INT_MIN) multiplo del modulo, quindi l’aggiunta e la sottrazione non cambieranno modulo. Si noti che ha un tipo senza segno e il risultato sarà intero. Sfortunatamente non può convertire correttamente i valori INT_MIN … (- offset-1) poiché causano un overflow amagnetico. Ma questo metodo ha il vantaggio di un’unica aritmetica addizionale per operazione (e senza condizionali) quando si lavora con un divisore costante, quindi è utilizzabile in applicazioni simili a DSP.

C’è un caso speciale, in cui il divisore è 2 N (potenza intera di due), per cui il modulo può essere calcolato utilizzando la semplice logica aritmetica e bit a bit come

 dividend&(divider-1) 

per esempio

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

Più comune e meno complicato è ottenere modulo usando questa funzione (funziona solo con il separatore positivo):

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

Questo risultato è corretto se è negativo.

Inoltre puoi ingannare:

(p% q + q)% q

È molto breve ma usa due% -s che sono normalmente lenti.

Credo che un’altra soluzione a questo problema potrebbe essere utilizzata per variabili di tipo long anziché int.

Stavo solo lavorando su un codice in cui l’operatore% stava restituendo un valore negativo che ha causato alcuni problemi (per generare variabili casuali uniformi su [0,1] in realtà non vuoi numeri negativi :)), ma dopo aver cambiato le variabili in digita a lungo, tutto procedeva senza intoppi ei risultati corrispondevano a quelli che stavo ricevendo quando eseguivo lo stesso codice in python (importante per me perché volevo essere in grado di generare gli stessi numeri “casuali” su più piattaforms.

 / * Attenzione: la mod macro valuta gli effetti collaterali degli argomenti più volte.  * /
 #define mod (r, m) (((r)% (m)) + ((r) <0)? (m): 0)

... o semplicemente abituarsi a ottenere qualsiasi rappresentante per la class di equivalenza.

Ecco una nuova risposta a una vecchia domanda, basata su questo documento di ricerca Microsoft e riferimenti in esso.

Nota che da C11 e C ++ 11 in poi, la semantica di div è diventata troncamento verso zero (vedi [expr.mul]/4 ). Inoltre, per D diviso per d , C ++ 11 garantisce quanto segue sul quoziente qT e resto 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)); 

dove signum esegue il mapping su -1, 0, +1, a seconda che il suo argomento sia < , ==,> di 0 (vedere questo Q & A per il codice sorgente).

Con la divisione troncata, il segno del resto è uguale al segno del dividendo D , cioè -1 % 8 == -1 . C ++ 11 fornisce anche una funzione std::div che restituisce una struct con membri quot e rem base alla divisione troncata.

Ci sono altre definizioni possibili, ad esempio la cosiddetta divisione pavimentata può essere definita in termini di divisione troncata incorporata

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

Con la divisione pavimentata, il segno del resto è uguale al segno del divisore d . In lingue come Haskell e Oberon, ci sono operatori integrati per la divisione floored. In C ++, avresti bisogno di scrivere una funzione usando le definizioni di cui sopra.

Un altro modo è la divisione euclidea , che può anche essere definita in termini di divisione troncata incorporata

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

Con la divisione euclidea, il segno del resto è sempre positivo .

Esempio di modello per C ++

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

Con questo modello, il resto restituito sarà zero o avrà lo stesso segno del divisore (denominatore) (l'equivalente di arrotondamento verso l'infinito negativo), invece del comportamento C ++ del resto è zero o con lo stesso segno del dividendo ( numeratore) (l'equivalente di arrotondamento verso lo zero).

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

Questa soluzione (da usare quando mod è positiva) evita di prendere tutte le operazioni negative di divisione o resto tutte insieme:

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

Farei:

 ((-1)+8) % 8 

Questo aggiunge il secondo numero al primo prima di fare il modulo dando 7 come desiderato. Questo dovrebbe funzionare per qualsiasi numero fino a -8. Per -9 aggiungi 2 * 8.