Jak zakodować operator modulo (%) w C / C ++ / Obj-C, który obsługuje liczby ujemne

Jedną z moich ulubionych nienawiści do języków wywodzących się z C (jako matematyka) jest to

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

fmodf(-1,8) // fails similarly

Jakie jest najlepsze rozwiązanie?

C ++ dopuszcza możliwość przeciążania szablonów i operatorów, ale oba te elementy są dla mnie mętne. przykłady otrzymane z wdzięcznością.

Przede wszystkim chciałbym zauważyć, że nie można nawet na tym polegać (-1) % 8 == -1. jedyne, na czym możesz polegać, to to (x / y) * y + ( x % y) == x. Jednak to, czy reszta jest ujemna, czy nie, jest zdefiniowane w ramach implementacji .

Dlaczego więc używać tutaj szablonów? Wystarczyłoby przeciążenie int i long.

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

a teraz możesz nazwać to jak mod (-1,8) i będzie wyglądać na 7.

Edycja: znalazłem błąd w moim kodzie. Nie zadziała, jeśli b jest ujemne. Więc myślę, że tak jest lepiej:

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

Odniesienie: C ++ 03 paragraf 5.6, klauzula 4:

Operator binarny / daje iloraz, a operator binarny% zwraca resztę z dzielenia pierwszego wyrażenia przez drugie. Jeśli drugi operand / lub% wynosi zero, zachowanie jest niezdefiniowane; w przeciwnym razie (a / b) * b + a% b jest równe a. Jeśli oba operandy są nieujemne, reszta jest nieujemna; jeśli nie, znak reszty jest określony przez implementację .

Oto funkcja C, która obsługuje dodatnie LUB ujemne liczby całkowite LUB wartości ułamkowe dla OBU OPERANDÓW

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

To z pewnością najbardziej eleganckie rozwiązanie z matematycznego punktu widzenia. Jednak nie jestem pewien, czy jest solidny w obsłudze liczb całkowitych. Czasami pojawiają się błędy zmiennoprzecinkowe podczas konwersji int -> fp -> int.

Używam tego kodu dla non-int i osobnej funkcji dla int.

UWAGA: trzeba uwięzić N = 0!

Kod testera:

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

(Uwaga: możesz skompilować i uruchomić go bezpośrednio z CodePad: http://codepad.org/UOgEqAMA )

Wynik:

fmodf (-10,2, 2,0) = -0,20 == BŁĄD!

10,2 zmiana 2,0 = 0,2
10,2 zmiana -2,0 = -1,8
-10,2 zmiana 2,0 = 1,8
-10,2 zmiana -2,0 = -0,2

Właśnie zauważyłem, że Bjarne Stroustrup %określa jako operator reszty , a nie operator modulo.

Założę się, że to jest jego formalna nazwa w specyfikacji ANSI C i C ++ i że wkradło się nadużycie terminologii. Czy ktoś wie o tym na pewno?

Ale jeśli tak jest, to funkcja fmodf () w C (i prawdopodobnie inne) są bardzo mylące. powinny być oznaczone jako fremf () itp

Najprostszą funkcją ogólną do znalezienia dodatniego modulo byłoby to - działałoby zarówno na dodatnich, jak i ujemnych wartościach x.

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

W przypadku liczb całkowitych jest to proste. Po prostu zrób

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

gdzie, jak przypuszczam, Njest to pozytywne i możliwe do przedstawienia w typie x. Twój ulubiony kompilator powinien być w stanie to zoptymalizować, tak aby kończyło się tylko jedną operacją modyfikacji w asemblerze.

Najlepszym rozwiązaniem ¹ dla matematyka jest użycie Pythona.

Przeciążanie operatorów C ++ ma z tym niewiele wspólnego. Nie można przeciążać operatorów dla typów wbudowanych. To, czego chcesz, to po prostu funkcja. Oczywiście możesz użyć szablonów C ++, aby zaimplementować tę funkcję dla wszystkich odpowiednich typów za pomocą tylko 1 fragmentu kodu.

Standardowa biblioteka C zapewnia fmod, jeśli dobrze pamiętam nazwę, dla typów zmiennoprzecinkowych.

W przypadku liczb całkowitych można zdefiniować szablon funkcji C ++, który zawsze zwraca nieujemną resztę (odpowiadającą podziałowi euklidesowemu) jako ...

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

... i po prostu pisz mod(a, b)zamiast a%b.

Tutaj typ Integermusi być typem liczby całkowitej ze znakiem.

Jeśli chcesz typowego zachowania matematycznego, w którym znak reszty jest taki sam jak znak dzielnika, możesz np.

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

… Z tym samym ograniczeniem Integer, że jest to typ ze znakiem.

^{¹ Ponieważ dzielenie liczb całkowitych w Pythonie zaokrągla się w kierunku ujemnej nieskończoności.}

Och, za to też nienawidzę projektu% ....

Możesz zamienić dywidendę na niepodpisaną w następujący sposób:

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

result = (offset + dividend) % divider

gdzie offset jest najbliższy wielokrotności (-INT_MIN) modułu, więc dodawanie i odejmowanie go nie zmieni modulo. Zauważ, że ma on typ bez znaku, a wynik będzie liczbą całkowitą. Niestety nie może poprawnie przekonwertować wartości INT_MIN ... (- offset-1), ponieważ powodują one przepełnienie arytmetyczne. Ale ta metoda ma zaletę tylko jednej dodatkowej arytmetyki na operację (bez warunków warunkowych) podczas pracy ze stałym dzielnikiem, więc jest użyteczna w aplikacjach podobnych do DSP.

Istnieje specjalny przypadek, w którym dzielnik wynosi 2 ^N (całkowita potęga dwóch), dla którego modulo można obliczyć za pomocą prostej arytmetyki i logiki bitowej jako

dividend&(divider-1)

na przykład

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

Bardziej powszechnym i mniej skomplikowanym sposobem jest uzyskanie modulo za pomocą tej funkcji (działa tylko z dodatnim dzielnikiem):

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

To tylko poprawny wynik, jeśli jest ujemny.

Możesz też oszukać:

(p% q + q)% q

Jest bardzo krótki, ale używaj dwóch%, które są zwykle wolne.

Uważam, że innym rozwiązaniem tego problemu byłoby użycie zmiennych typu long zamiast int.

Właśnie pracowałem nad kodem, w którym operator% zwracał wartość ujemną, co powodowało pewne problemy (do generowania jednolitych zmiennych losowych na [0,1] tak naprawdę nie chcesz liczb ujemnych :)), ale po przełączeniu zmiennych na typ long, wszystko działało gładko, a wyniki były zgodne z tymi, które otrzymywałem podczas uruchamiania tego samego kodu w Pythonie (ważne dla mnie, ponieważ chciałem mieć możliwość generowania tych samych „losowych” liczb na kilku platformach.

Oto nowa odpowiedź na stare pytanie, oparta na artykule Microsoft Research i zawartych w nim odniesieniach.

Zauważ, że począwszy od C11 i C ++ 11, semantyka programu divstała się obcięta do zera (zobacz [expr.mul]/4). Ponadto, w przypadku Ddzielenia przez d, C ++ 11 gwarantuje następujące informacje o ilorazie qTi pozostałej częścirT

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

gdzie signummapuje do -1, 0, +1, w zależności od tego, czy jego argument jest <, ==,> niż 0 (zobacz ten Q&A dla kodu źródłowego).

W przypadku dzielenia obciętego znak reszty jest równy znakowi dywidendyD , tj -1 % 8 == -1. C ++ 11 zapewnia również std::divfunkcję, która zwraca strukturę ze składowymi quoti remwedług obciętego podziału.

Możliwe są inne definicje, np. Tak zwany podział ze stropem może być zdefiniowany za pomocą wbudowanego podziału obciętego

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

W przypadku dzielenia liczbowego znak reszty jest równy znakowi dzielnikad . W językach takich jak Haskell i Oberon istnieją wbudowane operatory dzielenia liczbowego. W C ++ trzeba by napisać funkcję przy użyciu powyższych definicji.

Jeszcze innym sposobem jest podział euklidesowy , który można również zdefiniować za pomocą wbudowanego podziału obciętego

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

W przypadku podziału euklidesowego znak reszty jest zawsze dodatni .

W przypadku rozwiązania, które nie wykorzystuje gałęzi i tylko 1 mod, możesz wykonać następujące czynności

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

/ * Ostrzeżenie: makro mod wielokrotnie ocenia efekty uboczne swoich argumentów. * /
# zdefiniować mod (r, m) (((r)% (m)) + ((r) <0)? (m): 0)

... lub po prostu przyzwyczaić się do znalezienia przedstawiciela klasy równoważności.

Przykładowy szablon dla C ++

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

W przypadku tego szablonu, zwrócona reszta będzie równa zero lub będzie miała ten sam znak co dzielnik (mianownik) (odpowiednik zaokrąglenia w kierunku ujemnej nieskończoności), zamiast zachowania C ++ reszty równej zero lub mającej ten sam znak co dywidenda ( licznik) (odpowiednik zaokrąglenia w kierunku zera).

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

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

To rozwiązanie (używane, gdy modjest dodatnie) pozwala uniknąć jednoczesnego wykonywania ujemnych operacji dzielenia lub reszty:

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

Chciałbym zrobić:

((-1)+8) % 8 

To dodaje drugą liczbę do pierwszej przed wykonaniem modulo, dając 7 zgodnie z życzeniem. To powinno działać dla dowolnej liczby do -8. Dla -9 dodaj 2 * 8.