Praca modulo z liczbami ujemnymi

194

W programie C próbowałem poniższych operacji (aby sprawdzić zachowanie)

 x = 5 % (-3);
 y = (-5) % (3);
 z = (-5) % (-3); 

printf("%d ,%d ,%d", x, y, z); 

dał mi wyjście jak (2, -2 , -2)w gcc. Za każdym razem spodziewałem się pozytywnego wyniku. Czy moduł może być ujemny? Czy ktoś może wyjaśnić to zachowanie?

Alva
źródło
Możliwy duplikat stackoverflow.com/questions/4003232/...
James
1
możliwy duplikat operatora Modulo z wartościami ujemnymi
sugavaneshb

Odpowiedzi:

170

C99 wymaga, aby gdy a/bbył reprezentowalny:

(a/b) * b + a%b będzie równya

Logicznie ma to sens. Dobrze?

Zobaczmy, do czego to prowadzi:


Przykład A. 5/(-3)to-1

=> (-1) * (-3) + 5%(-3) =5

Może się to zdarzyć tylko wtedy, gdy 5%(-3)jest 2.


Przykład B. (-5)/3to-1

=> (-1) * 3 + (-5)%3 =-5

Może się to zdarzyć tylko wtedy, gdy (-5)%3jest-2

ArjunShankar
źródło
1
Czy kompilator powinien być wystarczająco inteligentny i wykrywać, że niepodpisany moduł inny niepodpisany jest zawsze dodatni? Obecnie (cóż, GCC 5.2) kompilator wydaje się myśleć, że „%” zwraca w tym przypadku „int”, zamiast „bez znaku”, nawet jeśli oba operandy są uint32_t lub większe.
Frederick Nord
@FrederickNord Czy masz przykład pokazujący to zachowanie ?
chux - Przywróć Monikę
10
Zrozum, że to, co opisujesz, jest zwykłym opisem mod (int / a) (skróconym). Ale możliwe jest również, że reguła to floor (a / b) (Knuth). W przypadku Knuth -5/3jest, -2a mod staje się 1. Krótko mówiąc: jeden moduł ma znak, który następuje po znaku dywidendy (obcięcie), drugi moduł ma znak, który następuje po znaku dzielnika (Knuth).
Izaak
1
Jest to przypadek, gdy standard C nie jest dokładnie tym, czego chcę. Nigdy nie chciałem obcinać do zera lub ujemnych liczb modulo, ale często chcę czegoś przeciwnego i muszę pracować wokół C.
Joe
143

%Operator C nie jest modulo operatora, ale pozostała operatora.

Moduły i pozostałe operatory różnią się pod względem wartości ujemnych.

W przypadku operatora reszty znak wyniku jest taki sam jak znak dywidendy, natomiast w przypadku operatora modulo znak wyniku jest taki sam jak dzielnik.

C definiuje %operację a % bjako:

  a == (a / b * b) + a % b

z /podziałem na liczby całkowite z obcięciem w kierunku 0. To obcięcie, które jest wykonywane w kierunku 0(a nie w kierunku ujemnej nieskończoności), które definiuje %jako operator reszty, a nie operator modulo.

ouah
źródło
8
Reszta jest wynikiem działania modulo z definicji. Nie powinno być czegoś takiego jak operator reszty, ponieważ nie ma czegoś takiego jak operacja reszty, nazywa się to modulo.
gronostaj
41
@gronostaj nie w CS. Spójrz na języki wyższego poziomu, takie jak Haskell lub Scheme, które definiują dwa różne operatory ( remainderoraz modulow Schemacie remi modw Haskell). Te specyfikacje operatorów różnią się w tych językach w zależności od sposobu podziału: obcięcie w kierunku 0 lub w kierunku ujemnej nieskończoności. Nawiasem mówiąc C Standardowy nigdy nazywa operatora modulo , po prostu wymienić mu operator% . %
ouah
2
Nie należy mylić z remainder funkcją w C, która implementuje pozostałą część IEEE z semantyką zaokrąglenia w kierunku najbliższego podziału
Eric
68

Na podstawie specyfikacji C99: a == (a / b) * b + a % b

Możemy napisać funkcję do obliczenia (a % b) == a - (a / b) * b!

int remainder(int a, int b)
{
    return a - (a / b) * b;
}

Do działania modulo możemy mieć następującą funkcję (zakładając b > 0)

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

Mój wniosek jest taki, że a % bw C jest operacją reszty, a NIE operacją modulo.

dewang
źródło
3
Nie daje to pozytywnych wyników, gdy bjest ujemne (a w rzeczywistości zarówno dla negatywnych, jak ri bnegatywnych daje wyniki mniejsze niż -b). Aby zapewnić pozytywne wyniki dla wszystkich danych wejściowych, których możesz użyć, r + abs(b)lub aby dopasować bznak s, możesz r*b < 0zamiast tego zmienić warunek na .
Martin Ender
@MartinEnder r + abs(b)to UB kiedy b == INT_MIN.
chux - Przywróć Monikę
60

Nie sądzę, że trzeba sprawdzać, czy liczba jest ujemna.

Prostą funkcją znalezienia pozytywnego modulo byłoby:

Edycja: Zakładając N > 0iN + N - 1 <= INT_MAX

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

Będzie to działać zarówno dla dodatnich, jak i ujemnych wartości x.

Oryginalny PS: też jak podkreślił @chux, Jeśli x i N może osiągnąć coś podobnego INT_MAX-1 i INT_MAX odpowiednio, po prostu zastąpić intz long long int.

A jeśli przekraczają również granice długich długich (tj. W pobliżu LLONG_MAX), wówczas osobno zajmiemy się przypadkami dodatnimi i ujemnymi, jak opisano w innych odpowiedziach tutaj.

Udayraj Deshmukh
źródło
1
Zauważ, że kiedy N < 0wynik może być ujemny jak w modulo(7, -3) --> -2. x % N + NMoże również przepełnić intmatematykę, która jest niezdefiniowanym zachowaniem. np. modulo(INT_MAX - 1,INT_MAX)może spowodować -3.
chux - Przywróć Monikę
Tak, w takim przypadku możesz po prostu użyć long long intlub osobno zająć się przypadkiem negatywnym (kosztem utraty prostoty).
Udayraj Deshmukh
9

Inne odpowiedzi wyjaśniły w C99 lub później, podział liczb całkowitych obejmujący argumenty ujemne zawsze jest skracany do zera .

Zauważ, że w C89 , czy zaokrąglenie wyniku w górę, czy w dół jest zdefiniowane w implementacji. Ponieważ (a/b) * b + a%bjest równy awe wszystkich standardach, wynik %angażowania argumentów ujemnych jest również zdefiniowany w C89.

Yu Hao
źródło
5

Czy moduł może być ujemny?

%może być ujemna, ponieważ jest operatorem reszty , reszta po dzieleniu, a nie po podziale Euclidean . Od C99 wynik może być 0, ujemny lub dodatni.

 // a % b
 7 %  3 -->  1  
 7 % -3 -->  1  
-7 %  3 --> -1  
-7 % -3 --> -1  

Modulo PO chciała to klasyczny euklidesowa modulo , nie %.

Za każdym razem spodziewałem się pozytywnego wyniku.

Aby wykonać moduł euklidesowy, który jest dobrze zdefiniowany za każdym razem, gdy a/bjest zdefiniowany, a,bmają dowolny znak, a wynik nigdy nie jest ujemny:

int modulo_Euclidean(int a, int b) {
  int m = a % b;
  if (m < 0) {
    // m += (b < 0) ? -b : b; // avoid this form: it is UB when b == INT_MIN
    m = (b < 0) ? m - b : m + b;
  }
  return m;
}

modulo_Euclidean( 7,  3) -->  1  
modulo_Euclidean( 7, -3) -->  1  
modulo_Euclidean(-7,  3) -->  2  
modulo_Euclidean(-7, -3) -->  2   
chux - Przywróć Monikę
źródło
2

Wynik działania Modulo zależy od znaku licznika, a zatem otrzymujesz -2 dla y i z

Oto odniesienie

http://www.chemie.fu-berlin.de/chemnet/use/info/libc/libc_14.html

Division Integer

W tej sekcji opisano funkcje przeprowadzania podziału na liczby całkowite. Funkcje te są nadmiarowe w bibliotece GNU C, ponieważ w GNU C operator „/” zawsze zaokrągla w kierunku zera. Ale w innych implementacjach C „/” może zaokrąglać się inaczej z argumentami negatywnymi. div i ldiv są przydatne, ponieważ określają sposób zaokrąglania ilorazu: w kierunku zera. Reszta ma ten sam znak, co licznik.

Kartik Anand
źródło
5
Odwołujesz się do tekstu o ANSI C. Jest to dość stara norma C. Nie jestem pewien, czy tekst jest poprawny w odniesieniu do ANSI C, ale zdecydowanie nie w odniesieniu do C99. W C99 w paragrafie 6.5.5 zdefiniowano dzielenie liczb całkowitych tak, aby zawsze było zmniejszane do zera.
Palec
2

W matematyce, z której wywodzą się te konwencje, nie można twierdzić, że arytmetyka modulo powinna dać wynik dodatni.

Na przykład.

1 mod 5 = 1, ale może również wynosić -4. Oznacza to, że 1/5 daje resztę 1 z 0 lub -4 z 5. (Oba współczynniki 5)

Podobnie, -1 mod 5 = -1, ale może również wynosić 4. Oznacza to, że -1/5 daje resztę -1 z 0 lub 4 z -5. (Oba czynniki 5)

W celu dalszej lektury zapoznaj się z klasami równoważności w matematyce.

DarkPurple141
źródło
Klasa równoważności jest inną koncepcją, a moduł jest definiowany w bardzo ścisły sposób. Powiedzmy, że mamy dwie liczby całkowite aa b, b <> 0. Zgodnie z twierdzeniem o podziale euklidesowym istnieje dokładnie jedna para liczb całkowitych m, rgdzie a = m * b + ri 0 <= r < abs( b ). Jest rto wynik (matematycznego) działania modulo i z definicji nie jest ujemne. Więcej lektur i dalsze linki na Wikipedii: en.wikipedia.org/wiki/Euclidean_division
Ister
To nie jest prawda. 1 mod 5jest zawsze 1. -4 mod 5może być również 1, ale są to różne rzeczy.
FelipeC
2

Zgodnie ze standardem C99 , sekcja 6.5.5. Operatory multiplikacyjne , wymagane są:

(a / b) * b + a % b = a

Wniosek

Znak wyniku pozostałej operacji, zgodnie z C99, jest taki sam jak dywidendy.

Zobaczmy kilka przykładów ( dividend / divisor):

Gdy tylko dywidenda jest ujemna

(-3 / 2) * 2  +  -3 % 2 = -3

(-3 / 2) * 2 = -2

(-3 % 2) must be -1

Gdy tylko dzielnik jest ujemny

(3 / -2) * -2  +  3 % -2 = 3

(3 / -2) * -2 = 2

(3 % -2) must be 1

Gdy zarówno dzielnik, jak i dywidenda są ujemne

(-3 / -2) * -2  +  -3 % -2 = -3

(-3 / -2) * -2 = -2

(-3 % -2) must be -1

6.5.5 Operatory multiplikatywne

Składnia

  1. wyrażenie multiplikatywne:
    • cast-expression
    • multiplicative-expression * cast-expression
    • multiplicative-expression / cast-expression
    • multiplicative-expression % cast-expression

Ograniczenia

  1. Każdy z argumentów powinien mieć typ arytmetyczny. Argumenty operatora % mają typ całkowity.

Semantyka

  1. Zwykłe konwersje arytmetyczne są wykonywane na operandach.

  2. Wynik operatora binarnego * jest iloczynem operandów.

  3. Wynikiem operatora / jest iloraz podziału pierwszego operandu przez drugi; wynikiem operatora % jest reszta. W obu operacjach, jeśli wartość drugiego operandu wynosi zero, zachowanie jest niezdefiniowane.

  4. Po podzieleniu liczb całkowitych wynikiem operatora / jest iloraz algebraiczny z odrzuconą dowolną częścią ułamkową [1]. Jeżeli iloraz a/bjest reprezentowalny, wyrażenie (a/b)*b + a%bpowinno być równe a.

[1]: Jest to często nazywane „obcięciem do zera”.

Ricardo Biehl Pasquali
źródło
1

Operator modułu podaje resztę. Operator modułu c zwykle przyjmuje znak licznika

  1. x = 5% (-3) - tutaj licznik jest dodatni, stąd daje 2
  2. y = (-5)% (3) - tutaj licznik jest ujemny, stąd daje wynik -2
  3. z = (-5)% (-3) - tutaj licznik jest ujemny, stąd wynika -2

Również operator modułu (reszty) może być używany tylko z liczbą całkowitą i nie może być stosowany z liczbą zmiennoprzecinkową.

Kavya
źródło
2
Byłoby miło, gdybyś mógł wykonać kopię zapasową za pomocą linków do zasobów zewnętrznych.
J ... S
1

Uważam, że bardziej użyteczne jest myślenie modtak, jak jest zdefiniowane w abstrakcyjnej arytmetyki; nie jako operacja, ale jako cała inna klasa arytmetyki, z różnymi elementami i różnymi operatorami. Oznacza to, że dodanie mod 3nie jest tym samym, co „normalne” dodanie; to jest; dodawanie liczb całkowitych.

Więc kiedy to zrobisz:

5 % -3

Próbujesz odwzorować liczbę całkowitą 5 na element w zestawie mod -3. Są to elementy mod -3:

{ 0, -2, -1 }

Więc:

0 => 0, 1 => -2, 2 => -1, 3 => 0, 4 => -2, 5 => -1

Powiedz, że musisz pozostać z jakiegoś powodu 30 godzin, ile godzin pozostało ci z tego dnia? 30 mod -24.

Ale to, co implementuje C mod, nie jest resztą. W każdym razie chodzi o to, że zwracanie negatywów ma sens.

FelipeC
źródło