Jak mogę zapewnić, że podział liczb całkowitych jest zawsze zaokrąglany w górę?

Chcę upewnić się, że podział liczb całkowitych jest zawsze zaokrąglany w górę, jeśli to konieczne. Czy jest lepszy sposób? Dużo się dzieje na castingu. :-)

(int)Math.Ceiling((double)myInt1 / myInt2)
 228
Author: Lightness Races in Orbit, 2009-05-28

7 answers

Aktualizacja: to pytanie było tematem mojego bloga w styczniu 2013. Dzięki za świetne pytanie!


Uzyskanie poprawnej arytmetyki całkowitej jest trudne. Jak zostało to do tej pory udowodnione, w momencie, gdy próbujesz zrobić "sprytny" trik, szanse są dobre, że popełniłeś błąd. A gdy zostanie znaleziona wada, zmiana kodu w celu naprawienia wady bez zastanawiania się, czy poprawka łamie coś innego , nie jest dobrą techniką rozwiązywania problemów. Do tej pory mieliśmy chyba pięć różnych niepoprawnych rozwiązań arytmetycznych dla tego zupełnie nie-szczególnie-trudnego problemu.

Właściwym sposobem podejścia do problemów arytmetyki całkowitej - czyli sposobu, który zwiększa prawdopodobieństwo uzyskania prawidłowej odpowiedzi za pierwszym razem - jest ostrożne podejście do problemu, rozwiązanie go krok po kroku i wykorzystanie w tym dobrych zasad inżynierii.

Zacznij od przeczytania specyfikacji tego, co próbujesz zastąpić. The Specyfikacja podziału liczb całkowitych jasno stwierdza:

  1. Podział zaokrągla wynik do zera

  2. Wynik jest zerowy lub dodatni, gdy dwa operandy mają ten sam znak i zero lub ujemny, gdy dwa operandy mają przeciwne znaki

  3. Jeśli lewy operand jest najmniejszą reprezentowalną wartością int, a prawy operand to -1, następuje przepełnienie. [...] jest to implementacja-definiowana, czy [ArithmeticException] jest wyrzucana, czy przepełnienie jest niezgłoszone, a wynikowa wartość jest wartością lewego operandu.

  4. Jeśli wartość prawego operandu wynosi zero, to System.Dividebyzeroexception jest wyrzucany.

Chcemy funkcji dzielenia liczb całkowitych, która oblicza iloraz, ale zaokrągla wynik zawsze w górę , a nie zawsze w kierunku zera .

Więc napisz specyfikację dla tej funkcji. Nasza funkcja int DivRoundUp(int dividend, int divisor) musi mieć określone zachowanie dla każdego możliwe wejście. To nieokreślone zachowanie jest głęboko niepokojące, więc wyeliminujmy je. Powiemy, że nasza operacja ma taką specyfikację:

  1. Operation throws if divisor is zero

  2. Operacja rzuca, jeśli dywidenda jest int.minval i dzielnik to -1

  3. Jeśli nie ma reszty -- dzielenie jest 'parzyste' -- wtedy wartością zwracaną jest iloraz całkowy

  4. W przeciwnym razie zwraca najmniejszą liczbę całkowitą, która jest większą niż iloraz, czyli zawsze się zaokrągla.

Teraz mamy specyfikację, więc wiemy, że możemy wymyślić testowalny projekt. Załóżmy, że dodamy dodatkowe kryterium projektowe, że problem zostanie rozwiązany wyłącznie za pomocą arytmetyki całkowitej, a nie obliczania ilorazu jako podwójnego, ponieważ rozwiązanie" podwójne " zostało wyraźnie odrzucone w instrukcji problemu.

Więc co musimy obliczyć? Oczywiście, aby spełnić nasze wymagania pozostając wyłącznie w liczbie całkowitej arytmetyka, musimy znać trzy fakty. Po pierwsze, jaki był iloraz całkowity? Po drugie, czy podział był wolny od reszty? A po trzecie, jeśli nie, to czy iloraz całkowity był obliczany przez Zaokrąglanie w górę lub w dół?

Teraz, gdy mamy specyfikację i projekt, możemy zacząć pisać kod.

public static int DivRoundUp(int dividend, int divisor)
{
  if (divisor == 0 ) throw ...
  if (divisor == -1 && dividend == Int32.MinValue) throw ...
  int roundedTowardsZeroQuotient = dividend / divisor;
  bool dividedEvenly = (dividend % divisor) == 0;
  if (dividedEvenly) 
    return roundedTowardsZeroQuotient;

  // At this point we know that divisor was not zero 
  // (because we would have thrown) and we know that 
  // dividend was not zero (because there would have been no remainder)
  // Therefore both are non-zero.  Either they are of the same sign, 
  // or opposite signs. If they're of opposite sign then we rounded 
  // UP towards zero so we're done. If they're of the same sign then 
  // we rounded DOWN towards zero, so we need to add one.

  bool wasRoundedDown = ((divisor > 0) == (dividend > 0));
  if (wasRoundedDown) 
    return roundedTowardsZeroQuotient + 1;
  else
    return roundedTowardsZeroQuotient;
}
Czy to sprytne? Nie. Piękna? Nie. Krótko? Nie. Poprawne zgodnie ze specyfikacją? wydaje mi się, że tak, ale nie do końca go przetestowałem.Wygląda całkiem nieźle.

Jesteśmy profesjonaliści tutaj; korzystać z dobrych praktyk inżynierskich. Zbadaj swoje narzędzia, określ pożądane zachowanie, najpierw rozważ przypadki błędów i napisz kod, aby podkreślić jego oczywistą poprawność. a kiedy znajdziesz błąd, zastanów się, czy twój algorytm jest głęboko wadliwy, zanim zaczniesz losowo wymieniać Kierunki porównań i łamać rzeczy, które już działają.

 652
Author: Eric Lippert,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-01-28 19:29:50

Ostateczna odpowiedź oparta na int

Dla liczby całkowitej podpisanej:

int div = a / b;
if (((a ^ b) >= 0) && (a % b != 0))
    div++;

Dla liczb całkowitych niepodpisanych:

int div = a / b;
if (a % b != 0)
    div++;

Uzasadnienie dla tej odpowiedzi

Liczba całkowita '/ ' jest zdefiniowana jako Zaokrąglanie w kierunku zera (7.7.2 specyfikacji), ale chcemy zaokrąglać. Oznacza to, że odpowiedzi negatywne są już prawidłowo zaokrąglane, ale odpowiedzi pozytywne muszą zostać skorygowane.

Niezerowe pozytywne odpowiedzi są łatwe do wykrycia, ale odpowiedź zero jest trochę trudniejsza, ponieważ może być zaokrągleniem w górę wartości ujemnej lub zaokrągleniem w dół wartości dodatniej.

Najbezpieczniej jest wykryć, kiedy odpowiedź powinna być pozytywna, sprawdzając, czy znaki obu liczb całkowitych są identyczne. Operator XOR Integer '^ ' na obu wartościach spowoduje, że znak 0 będzie w takim przypadku bitem, co oznacza wynik nieujemny, więc sprawdzenie (a ^ b) >= 0 określa, że wynik powinien być dodatni przed zaokrągleniem. Zauważ również, że dla niepodpisanych liczb całkowitych każda odpowiedź jest oczywiście pozytywny, więc ten czek można pominąć.

Pozostaje tylko sprawdzenie, czy doszło do zaokrąglenia, dla którego a % b != 0 wykona zadanie.

Wyciągnięte wnioski

Arytmetyka (liczba całkowita lub inna) nie jest tak prosta, jak się wydaje. Uważne myślenie wymagane przez cały czas.

Ponadto, chociaż moja ostateczna odpowiedź nie jest być może tak "prosta" lub "oczywista", a może nawet "szybka" jak odpowiedzi zmiennoprzecinkowe, ma jedną bardzo silną jakość odkupienia dla mnie; teraz rozumowałem przez odpowiedź, więc jestem rzeczywiście pewien, że jest poprawna (dopóki ktoś mądrzejszy nie powie mi inaczej- {40]}furtywne spojrzenie w kierunku Erica {41]}-).

Aby uzyskać to samo poczucie pewności co do odpowiedzi zmiennoprzecinkowej, musiałbym zrobić więcej (i być może bardziej skomplikowane) myśląc o tym, czy istnieją jakiekolwiek warunki, w których precyzja zmiennoprzecinkowa może stać na drodze, i czy Math.Ceiling być może robi coś niepożądanego na "tylko właściwym" wejścia.

The path traveled

Zastąp (Uwaga zamieniłem drugie myInt1 na myInt2, zakładając, że o to ci chodziło):

(int)Math.Ceiling((double)myInt1 / myInt2)

Z:

(myInt1 - 1 + myInt2) / myInt2

Jedynym zastrzeżeniem jest to, że jeśli myInt1 - 1 + myInt2 przepełnia Typ integer, którego używasz, możesz nie uzyskać tego, czego oczekujesz.

dlatego jest to błędne: -1000000 i 3999 powinno dać -250, to daje -249

EDIT:
Biorąc pod uwagę, że ma ten sam błąd co druga liczba całkowita rozwiązanie dla ujemnych wartości myInt1, może być łatwiej zrobić coś takiego:

int rem;
int div = Math.DivRem(myInt1, myInt2, out rem);
if (rem > 0)
  div++;

To powinno dać poprawny wynik w div używając tylko operacji integer.

powód jest zły : -1 i -5 powinno dać 1, to daje 0

EDIT (jeszcze raz z feelingiem):
Operator podziału zaokrągla się do zera; dla wyników ujemnych jest to dokładnie poprawne, więc tylko wyniki nieujemne wymagają korekty. Również biorąc pod uwagę, że DivRem po prostu robi / i % w każdym razie pomińmy wywołanie (i zacznijmy od łatwego porównania, aby uniknąć obliczeń modulo, gdy nie jest to potrzebne):

int div = myInt1 / myInt2;
if ((div >= 0) && (myInt1 % myInt2 != 0))
    div++;

powód jest zły : -1 i 5 powinno dać 0, to daje 1

(w mojej obronie przed ostatnią próbą nigdy nie powinienem był próbować uzasadnionej odpowiedzi, gdy mój umysł mówił mi, że spóźniłem się 2 godziny na sen)

 43
Author: jerryjvl,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-30 00:15:24

Wszystkie odpowiedzi tutaj do tej pory wydają się dość skomplikowane.

W C # i Javie, aby uzyskać dodatnią dywidendę i dzielnik, wystarczy wykonać:

( dividend + divisor - 1 ) / divisor 

Źródło: Konwersja Liczb, Roland Backhouse, 2001

 42
Author: Ian Nelson,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-12-09 15:43:03

Doskonała szansa na użycie metody rozszerzenia:

public static class Int32Methods
{
    public static int DivideByAndRoundUp(this int number, int divideBy)
    {                        
        return (int)Math.Ceiling((float)number / (float)divideBy);
    }
}

To sprawia, że Twój kod też jest czytelny:

int result = myInt.DivideByAndRoundUp(4);
 19
Author: joshcomley,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-12-01 11:02:31

Możesz napisać pomocnika.

static int DivideRoundUp(int p1, int p2) {
  return (int)Math.Ceiling((double)p1 / p2);
}
 17
Author: JaredPar,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-28 14:40:33

Przydałoby się coś takiego jak poniżej.

a / b + ((Math.Sign(a) * Math.Sign(b) > 0) && (a % b != 0)) ? 1 : 0)
 4
Author: Daniel Brückner,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-05-30 11:17:58

Problem ze wszystkimi rozwiązaniami tutaj jest albo to, że potrzebują obsady, albo mają problem liczbowy. Rzucanie na float lub double jest zawsze opcją, ale możemy zrobić lepiej.

Gdy używasz kodu odpowiedzi z @ jerryjvl

int div = myInt1 / myInt2;
if ((div >= 0) && (myInt1 % myInt2 != 0))
    div++;

Występuje błąd zaokrąglania. 1 / 5 by się zebrało, Bo 1% 5 != 0. Ale jest to złe, ponieważ zaokrąglenie nastąpi tylko wtedy, gdy zastąpisz 1 na 3, więc wynik wynosi 0,6. Musimy znaleźć sposób, aby zaokrąglić, gdy obliczenia dają nas wartość większa lub równa 0,5. Wynik operatora modulo w górnym przykładzie ma zakres od 0 do 2-1. Zaokrąglenie nastąpi tylko wtedy, gdy pozostała część jest większa niż 50% dzielnika. Więc skorygowany kod wygląda tak:

int div = myInt1 / myInt2;
if (myInt1 % myInt2 >= myInt2 / 2)
    div++;

Oczywiście mamy problem z zaokrągleniem w myInt2 / 2, ale ten wynik da Ci lepsze rozwiązanie niż inne na tej stronie.

 -2
Author: raboni,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2012-06-20 15:47:20