Pytanie C ++ Najlepszy sposób na dzielenie liczb całkowitych i pozostałe


Zastanawiam się tylko, czy chcę dzielić a-b, i jestem zainteresowany zarówno wynikiem c, jak i resztą (np. Powiedz, że mam liczbę sekund i chcę podzielić to na minuty i sekundy), jaki jest najlepszy sposób na chodzić o tym?

Czy może być

int c = (int)a / b;
int d = a % b;

lub

int c = (int)a / b;
int d = a - b * c;

lub

double tmp = a / b;
int c = (int)tmp;
int d = (int)(0.5+(tmp-c)*b);

lub

może istnieje magiczna funkcja, która daje jedno na raz?


76
2017-08-15 20:21


pochodzenie


wszystkie poniższe odpowiedzi wydają się rozsądne, chciałbym tylko dodać, że wszelkie mucking z double (Twój ostatni element) wydaje mi się złym pomysłem, skończysz z liczbami, które nie ustawiają się w linii i mogą kosztować wydajność i rozmiar pliku wykonywalnego (zawsze był to problem dla mnie w niektórych systemach wbudowanych). - nhed
Trzeci to Zła opcja: co jeśli tmp = 54.999999999999943157? To powiedziawszy, casting w starym stylu nigdy nie jest mądrym posunięciem. - jimifiki


Odpowiedzi:


Na x86 reszta jest produktem ubocznym samego podziału, więc każdy przyzwoity kompilator powinien móc go po prostu użyć (i nie wykonywać div jeszcze raz). Prawdopodobnie dzieje się tak również w innych architekturach.

Instrukcja: DIV src

Uwaga: niepodpisany podział. Dzieli akumulator (AX) przez "src". Jeśli dzielnik   jest wartością bajtową, wynik jest podawany do AL i pozostała do AH. Jeśli dzielnik   jest wartością słowa, a następnie DX: AX jest dzielone przez "src" i wynik jest zapisywany   w AX a pozostała część jest przechowywana w DX.

int c = (int)a / b;
int d = a % b; /* Likely uses the result of the division. */

76
2017-08-15 20:23



Myślę, że wielu uczniów wie od szkoły podstawowej, że robiąc podział, dostajecie resztę za darmo. Prawdziwe pytanie brzmi: czy nasze kompilatory są wystarczająco inteligentne, aby z tego skorzystać?
@jdv: Nie byłbym zaskoczony. To bardzo prosta optymalizacja. - Jon Purdy
Próbowałem szybkiego testu. Z g ++ 4.3.2 przy użyciu -O2, wyjście asemblera wyraźnie pokazuje to używając jednego idivl instrukcja i wykorzystanie wyników w eax i edx. Byłbym zszokowany, gdyby tak się nie stało. - Fred Larson
@EuriPinhollow Zgadzam się, to nie jest pytanie o x86. Podałem to tylko jako przykład, z bardzo wątpliwym założeniem, że inne architektury prawdopodobnie robią coś podobnego. - cnicutar
Musisz jednak powiedzieć kompilatorowi, aby zoptymalizował co najmniej pod kątem g ++. Prosty eksperyment z g ++ 6.3.0 na x86_64 ujawnił, że bez żadnej optymalizacji masz dwa idivl instrukcje, ale z -O1 lub więcej, otrzymasz jeden. Jak mówi podręcznik, "Bez opcji optymalizacji ... Oświadczenia są niezależne". - Tom Zych


std::div zwraca strukturę z wynikiem i resztą.


59
2017-08-15 20:24



Jestem ciekawy, czy jest to rzeczywiście bardziej wydajne niż, powiedzmy, opcja 1 na nowoczesnym kompilatorze. - Greg Howell
Miło, nie wiedziałem. Czy to jest szybsze?
Miły. Czy zdarzy ci się wiedzieć, czy gdzieś jest realizowany przez długi czas? - Cookie
@ Cookie: C ++ 03 nie ma pojęcia long long, ale jest wysoce prawdopodobne, że twój kompilator ma long long przeciążenie std::div jako rozszerzenie. - ildjarn
@Greg: Nie sądzę, że tak jest, biorąc pod uwagę, że najprawdopodobniej musi zapisać wyniki w strukturze pamięci i zwrócić je, co (chyba że kompiluje się jako wbudowane, a dostęp do struktury jest zoptymalizowany) jest karą większą niż wykonywanie dodatkowa instrukcja podziału. - pezcode


Przynajmniej na x86, g ++ 4.6.1 używa tylko IDIVL i pobiera obie z tej pojedynczej instrukcji.

Kod C ++:

void foo(int a, int b, int* c, int* d)
{
  *c = a / b;
  *d = a % b;
}

kod x86:

__Z3fooiiPiS_:
LFB4:
    movq    %rdx, %r8
    movl    %edi, %edx
    movl    %edi, %eax
    sarl    $31, %edx
    idivl   %esi
    movl    %eax, (%r8)
    movl    %edx, (%rcx)
    ret

22
2017-08-15 20:41



Czy zamówienie ma znaczenie? Na przykład jeśli iterujesz po /= - może być konieczne użycie zmiennej tymczasowej, aby najpierw zachować podział. - Annan


Przykładowy kod testujący div () i połączony podział i mod. Skompilowałem je za pomocą gcc -O3, musiałem dodać wywołanie do nothing, aby zatrzymać kompilator od optymalizacji wszystkiego (wyjście będzie wynosić 0 dla rozwiązania division + mod).

Dodaj szczyptę soli:

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>

extern doNothing(int,int); // Empty function in another compilation unit

int main() {
    int i;
    struct timeval timeval;
    struct timeval timeval2;
    div_t result;
    gettimeofday(&timeval,NULL);
    for (i = 0; i < 1000; ++i) {
        result = div(i,3);
        doNothing(result.quot,result.rem);
    }
    gettimeofday(&timeval2,NULL);
    printf("%d",timeval2.tv_usec - timeval.tv_usec);
}

Wyjścia: 150

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>

extern doNothing(int,int); // Empty function in another compilation unit

int main() {
    int i;
    struct timeval timeval;
    struct timeval timeval2;
    int dividend;
    int rem;
    gettimeofday(&timeval,NULL);
    for (i = 0; i < 1000; ++i) {
        dividend = i / 3;
        rem = i % 3;
        doNothing(dividend,rem);
    }
    gettimeofday(&timeval2,NULL);
    printf("%d",timeval2.tv_usec - timeval.tv_usec);
}

Wyjścia: 25


8
2017-08-15 20:57





Oprócz wyżej wspomnianego std :: div rodzina funkcji, jest także std :: remquo rodzina funkcji, zwróć rem-odparł i zdobycie quo-tient za pomocą przekazanego wskaźnika.

[Edytować:] Wygląda jak std :: remquo tak naprawdę nie zwraca ilorazu po wszystkim.


5
2017-09-19 18:56





Wszystkie pozostałe są równe, najlepszym rozwiązaniem jest takie, które jasno wyraża twoje zamiary. Więc:

int totalSeconds = 453;
int minutes = totalSeconds / 60;
int remainingSeconds = totalSeconds % 60;

jest prawdopodobnie najlepszym z trzech przedstawionych przez ciebie opcji. Jak zauważono w innych odpowiedziach, jednak div metoda obliczy dla ciebie obie wartości naraz.


3
2017-08-15 20:27



Najwyraźniej pytanie dotyczy prędkości ... - Pacerier


Nie można zaufać g ++ 4.6.3 tutaj z 64-bitowymi liczbami całkowitymi na 32-bitowej platformie intel. a / b jest obliczane przez wywołanie divdi3, a% b jest obliczane przez wywołanie moddi3. Mogę nawet wymyślić przykład, który oblicza a / b i a-b * (a / b) z tymi wywołaniami. Używam więc c = a / b i a-b * c.

Metoda div daje wywołanie funkcji, która oblicza strukturę div, ale wywołanie funkcji wydaje się nieskuteczne na platformach, które mają sprzętową obsługę typu integralnego (tj. 64-bitowe liczby całkowite na 64-bitowych platformach intel / amd).


3
2018-05-04 01:38





Możesz użyć modułu, aby uzyskać pozostałą część. Choć odpowiedź @ cnicutara wydaje się czystsza / bardziej bezpośrednia.


-4
2017-08-15 20:26



Tak, oryginalny plakat użył operatora modulus, pytanie, jak sprawić, by był wydajny. - Mark Lakata