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

242

Chcę zapewnić, że podział liczb całkowitych jest zawsze zaokrąglany w górę, jeśli to konieczne. Czy istnieje lepszy sposób niż ten? Trwa dużo castingu. :-)

(int)Math.Ceiling((double)myInt1 / myInt2)
Karsten
źródło
48
Czy możesz jaśniej zdefiniować to, co uważasz za „lepsze”? Szybciej? Krótszy? Bardziej precyzyjne? Bardziej wytrzymałe? Bardziej oczywiście poprawne?
Eric Lippert
6
Zawsze masz dużo castingu z matematyką w C # - dlatego nie jest to świetny język dla tego rodzaju rzeczy. Czy chcesz, aby wartości były zaokrąglane w górę lub od zera - należy -3,1 przejść do -3 (w górę) czy -4 (od zera)
Keith
9
Eric: Co rozumiesz przez „dokładniejsze? Bardziej niezawodne? Oczywiście bardziej poprawne?” Właściwie to, co miałem na myśli, było po prostu „lepsze”, pozwoliłbym czytelnikowi lepiej nadać sens. Więc jeśli ktoś miał krótszy fragment kodu, świetnie, jeśli inny miał szybszy, również świetny :-) A co u Ciebie masz jakieś sugestie?
Karsten
1
Czy jestem jedyną osobą, która po przeczytaniu tytułu „Och, to jakaś łapanka C #?”
Matt Ball
6
To naprawdę niesamowite, jak subtelnie trudne okazało się to pytanie i jak pouczająca była dyskusja.
Justin Morgan

Odpowiedzi:

669

AKTUALIZACJA: To pytanie było przedmiotem mojego bloga w styczniu 2013 r . Dzięki za świetne pytanie!


Uzyskiwanie poprawnej arytmetyki liczb całkowitych jest trudne. Jak do tej pory wykazano obszernie, w chwili, gdy spróbujesz wykonać „sprytną” sztuczkę, szanse są duże, że popełniłeś błąd. A kiedy zostanie znaleziona wada, zmiana kodu w celu naprawienia usterki bez rozważania, czy poprawka psuje coś innego nie jest dobrą techniką rozwiązywania problemów. Do tej pory myślę, że pięć różnych niepoprawnych arytmetycznych rozwiązań liczb całkowitych na ten całkowicie niezbyt trudny problem.

Właściwy sposób podejścia do liczbowych problemów arytmetycznych - to znaczy sposób, który zwiększa prawdopodobieństwo otrzymania poprawnej odpowiedzi za pierwszym razem - polega na ostrożnym podejściu do problemu, rozwiązywaniu go krok po kroku i stosowaniu dobrych zasad inżynierii więc.

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

  1. Podział zaokrągla wynik w kierunku zera

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

  3. Jeśli lewy operand jest najmniejszą możliwą do przedstawienia int, a prawy operand ma wartość –1, następuje przepełnienie. [...] definiuje się implementację, czy zostanie zgłoszony [wyjątek Arithmetic], czy przepełnienie nie zostanie zgłoszone, a wynikowa wartość będzie wartością lewego operandu.

  4. Jeśli wartość prawego operandu wynosi zero, zgłaszany jest wyjątek System.DivideByZeroException.

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

Napisz więc specyfikację dla tej funkcji. Nasza funkcja int DivRoundUp(int dividend, int divisor)musi mieć zdefiniowane zachowanie dla każdego możliwego wejścia. To nieokreślone zachowanie jest głęboko niepokojące, więc wyeliminujmy je. Powiemy, że nasza operacja ma następującą specyfikację:

  1. operacja wyrzuca, jeśli dzielnik jest równy zero

  2. operacja wyrzuca, jeśli dywidenda jest int.minval, a dzielnik wynosi -1

  3. jeśli nie ma reszty - dzielenie jest „parzyste” - wówczas wartość zwracana jest ilorazem całkowitym

  4. W przeciwnym razie zwraca najmniejszą liczbę całkowitą większą niż iloraz, to znaczy zawsze zaokrągla w górę.

Teraz mamy specyfikację, więc wiemy, że możemy zaproponować testowalny projekt . Załóżmy, że dodamy dodatkowe kryterium projektowe, aby rozwiązać problem wyłącznie za pomocą arytmetyki liczb całkowitych, zamiast obliczania ilorazu jako liczby podwójnej, ponieważ rozwiązanie „podwójne” zostało wyraźnie odrzucone w opisie problemu.

Co więc musimy obliczyć? Oczywiście, aby spełnić naszą specyfikację, pozostając jedynie w zakresie arytmetyki liczb całkowitych, musimy znać trzy fakty. Po pierwsze, jaki był iloraz liczby całkowitej? Po drugie, czy dywizja była wolna od reszty? I po trzecie, jeśli nie, czy iloraz liczby całkowitej obliczono zaokrąglając 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 jest sprytne? Niepiękne? Nie. Krótki? Nie. Prawidłowo zgodnie ze specyfikacją? Wierzę w to, ale nie przetestowałem go w pełni. Wygląda jednak całkiem nieźle.

Jesteśmy tutaj profesjonalistami; stosować dobre praktyki inżynierskie. 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 zmieniać kierunki porównań i niszczyć rzeczy, które już działają.

Eric Lippert
źródło
44
Doskonała przykładowa odpowiedź
Gavin Miller
61
To, co mnie obchodzi, to nie zachowanie; każde z tych zachowań wydaje się uzasadnione. Chodzi mi o to, że nie jest określony , co oznacza, że ​​nie można go łatwo przetestować. W takim przypadku definiujemy własnego operatora, abyśmy mogli określić dowolne zachowanie. nie obchodzi mnie, czy to zachowanie jest „rzucać”, czy „nie rzucać”, ale zależy mi na tym, aby to powiedzieć.
Eric Lippert
68
Cholera, pedanteria zawodzą :(
Jon Skeet
32
Człowieku - czy mógłbyś napisać na ten temat książkę?
xtofl
76
@finnw: Nieważne, czy go przetestowałem, czy nie. Rozwiązanie tego problemu arytmetycznego liczb całkowitych nie jest moim problemem biznesowym; gdyby tak było, to bym to przetestował. Jeśli ktoś chce zabrać nieznajomym kod z Internetu, aby rozwiązać swój problem biznesowy, spoczywa na nim obowiązek jego dokładnego przetestowania.
Eric Lippert
49

Wszystkie dotychczasowe odpowiedzi wydają się raczej skomplikowane.

W języku C # i Javie, dla dodatniej dywidendy i dzielnika, wystarczy wykonać:

( dividend + divisor - 1 ) / divisor 

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

Ian Nelson
źródło
Niesamowite. Powinieneś dodać nawiasy, aby usunąć dwuznaczności. Dowód tego był nieco długi, ale możesz poczuć to w jelitach, że to prawda, po prostu patrząc na to.
Jörgen Sigvardsson,
1
Hmmm ... co z dywidendą = 4, dzielnikiem = (- 2) ??? 4 / (-2) = (-2) = (-2) po zaokrągleniu w górę. ale podany algorytm (4 + (-2) - 1) / (-2) = 1 / (-2) = (-0,5) = 0 po zaokrągleniu w górę.
Scott,
1
@ Scott - przepraszam, nie wspomniałem, że to rozwiązanie dotyczy tylko dodatniej dywidendy i dzielnika. Zaktualizowałem moją odpowiedź, aby wspomnieć o wyjaśnieniach.
Ian Nelson
1
podoba mi się to, oczywiście, że może być nieco sztuczny przepełnienie licznika jako produkt uboczny tego podejścia ...
TCC
2
@PIntag: Pomysł jest dobry, ale złe zastosowanie modulo. Weź 13 i 3. Oczekiwany wynik 5, ale ((13-1)%3)+1)daje 1 jako wynik. Właściwy podział 1+(dividend - 1)/divisordaje taki sam wynik, jak odpowiedź na dywidendę dodatnią i dzielnik. Ponadto nie występują problemy z przepełnieniem, jakkolwiek mogą być sztuczne.
Lutz Lehmann
48

Ostateczna odpowiedź int

Dla liczb całkowitych ze znakiem:

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

W przypadku liczb całkowitych bez znaku:

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

Uzasadnienie tej odpowiedzi

Podział liczb całkowitych ' /' jest zdefiniowany do zaokrąglania w kierunku zera (7.7.2 specyfikacji), ale chcemy zaokrąglić w górę. Oznacza to, że odpowiedzi negatywne są już poprawnie zaokrąglone, ale odpowiedzi pozytywne należy dostosować.

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

Najbezpieczniejszym zakładem jest wykrycie, kiedy odpowiedź powinna być pozytywna, poprzez sprawdzenie, czy znaki obu liczb całkowitych są identyczne. Operator liczb całkowitych xor ' ^' na tych dwóch wartościach spowoduje w tym przypadku bit znaku 0, co oznacza wynik nieujemny, więc sprawdzenie (a ^ b) >= 0ustali, że wynik powinien być dodatni przed zaokrągleniem. Zauważ również, że w przypadku liczb całkowitych bez znaku każda odpowiedź jest oczywiście pozytywna, więc to sprawdzenie można pominąć.

Pozostaje tylko sprawdzenie, czy zaszło zaokrąglenie, które a % b != 0wykona zadanie.

Zdobyta wiedza

Arytmetyka (liczba całkowita lub inna) nie jest tak prosta, jak się wydaje. Ciągłe myślenie jest wymagane.

Ponadto, chociaż moja ostateczna odpowiedź może nie jest tak „prosta”, „oczywista”, a może nawet „szybka”, jak odpowiedzi zmiennoprzecinkowe, ma ona dla mnie jedną bardzo silną cechę odkupienia; Teraz uzasadniłem odpowiedź, więc jestem pewien, że jest poprawna (dopóki ktoś mądrzejszy nie powie mi inaczej - ukradkowe spojrzenie w kierunku Erica -).

Aby uzyskać to samo poczucie pewności co do odpowiedzi zmiennoprzecinkowej, musiałbym robić więcej (i być może bardziej skomplikowane), zastanawiając się, czy są jakieś warunki, w których precyzja zmiennoprzecinkowa mogłaby przeszkadzać i czy Math.Ceilingmoże nie coś niepożądanego przy „odpowiednich” wejściach.

Ścieżka przemierzała

Wymienić (nota Wymieniłem drugi myInt1z myInt2zakładając, że było to, co masz na myśli):

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

z:

(myInt1 - 1 + myInt2) / myInt2

Jedynym zastrzeżeniem jest to, że jeśli myInt1 - 1 + myInt2przepełni się typ liczb całkowitych, którego używasz, możesz nie uzyskać tego, czego oczekujesz.

Powód jest zły : -1000000 i 3999 powinny dać -250, to daje -249

EDYCJA:
Biorąc pod uwagę ten sam błąd co inne rozwiązanie liczb całkowitych dla myInt1wartości ujemnych , 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 divużyciu tylko operacji na liczbach całkowitych.

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

EDYCJA (jeszcze raz, z wyczuciem):
Operator podziału zaokrągla w kierunku zera; w przypadku wyników ujemnych jest to dokładnie właściwe, więc tylko wyniki nieujemne wymagają korekty. Biorąc pod uwagę, że DivRempo prostu robi /, a %mimo to, pomińmy rozmowę (i zacząć od łatwego porównania Aby uniknąć obliczeń modulo, gdy nie jest to konieczne):

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

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

(W mojej obronie ostatniej próby nigdy nie powinienem był próbować uzyskać uzasadnionej odpowiedzi, gdy mój umysł mówił mi, że spóźniłem się o 2 godziny)

jerryjvl
źródło
19

Idealna szansa na zastosowanie metody rozszerzenia:

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

Dzięki temu twój kod jest również czytelny:

int result = myInt.DivideByAndRoundUp(4);
joshcomley
źródło
1
Eee, co? Twój kod nazywałby się myInt.DivideByAndRoundUp () i zawsze zwracał 1, z wyjątkiem wejścia 0, które powodowałoby wyjątek ...
konfigurator
5
Awaria epicka. (-2) .DivideByAndRoundUp (2) zwraca 0.
Timwi
3
Jestem naprawdę spóźniony na imprezę, ale czy ten kod się kompiluje? Moja klasa Math nie zawiera metody Ceiling, która przyjmuje dwa argumenty.
R. Martinho Fernandes,
17

Możesz napisać pomocnika.

static int DivideRoundUp(int p1, int p2) {
  return (int)Math.Ceiling((double)p1 / p2);
}
JaredPar
źródło
1
Nadal jednak ta sama ilość castingów trwa
ChrisF
29
@Outlaw, zakładaj, co chcesz. Ale dla mnie, jeśli nie zadają tego pytania, ogólnie zakładam, że nie brali tego pod uwagę.
JaredPar
1
Pisanie pomocnika jest bezużyteczne, jeśli jest właśnie tak. Zamiast tego napisz pomocnika z kompleksowym pakietem testów.
dolmen
3
@dolmen Czy znasz pojęcie ponownego wykorzystania kodu ? oO
Rushyo,
4

Możesz użyć czegoś takiego jak poniżej.

a / b + ((Math.Sign(a) * Math.Sign(b) > 0) && (a % b != 0)) ? 1 : 0)
Daniel Brückner
źródło
12
Ten kod jest oczywiście błędny na dwa sposoby. Po pierwsze, występuje niewielki błąd w składni; potrzebujesz więcej nawiasów. Ale co ważniejsze, nie oblicza pożądanego wyniku. Na przykład spróbuj przetestować z = -1000000 ib = 3999. Wynik zwykłego podziału na liczby całkowite to -250. Podwójny podział to -250,0625 ... Pożądanym zachowaniem jest zaokrąglanie w górę. Oczywiście poprawne zaokrąglenie w górę od -250,0625 to zaokrąglenie w górę do -250, ale twój kod zaokrągla w górę do -249.
Eric Lippert
36
Przykro mi, że muszę to powtarzać, ale Twój kod jest WCIĄŻ ŹLE Daniel. 1/2 powinno zaokrąglić W GÓRĘ do 1, ale twój kod zaokrągla W DÓŁ do 0. Za każdym razem, gdy znajdę błąd, „naprawiasz” go, wprowadzając inny błąd. Moja rada: przestań to robić. Gdy ktoś znajdzie błąd w twoim kodzie, nie po prostu napraw go razem, nie zastanawiając się dokładnie, co spowodowało błąd. Stosuj dobre praktyki inżynierskie; znajdź błąd w algorytmie i napraw go. Wada we wszystkich trzech niepoprawnych wersjach algorytmu polega na tym, że nie określasz poprawnie, kiedy zaokrąglenie było „w dół”.
Eric Lippert
8
Niewiarygodne, ile błędów może zawierać ten niewielki fragment kodu. Nigdy nie miałem dużo czasu, aby się nad tym zastanowić - wynik przejawia się w komentarzach. (1) a * b> 0 byłoby poprawne, gdyby się nie przelało. Istnieje 9 kombinacji znaku aib - [-1, 0, +1] x [-1, 0, +1]. Możemy zignorować przypadek b == 0, pozostawiając 6 przypadków [-1, 0, +1] x [-1, +1]. a / b zaokrągla w kierunku zera, czyli zaokrągla w górę dla wyników ujemnych i zaokrągla w dół dla wyników pozytywnych. Stąd dostosowanie należy wykonać, jeśli aib mają ten sam znak i oba nie są równe zero.
Daniel Brückner
5
Ta odpowiedź jest prawdopodobnie najgorszą rzeczą, którą napisałem na SO ... i jest teraz połączona z blogiem Erica ... Cóż, moim zamiarem nie było dać czytelnego rozwiązania; Naprawdę blokowałem się na krótki i szybki hack. Aby znów bronić mojego rozwiązania, za pierwszym razem dobrze zrozumiałem, ale nie myślałem o przepełnieniu. Oczywiście moim błędem było opublikowanie kodu bez pisania i testowania go w VisualStudio. „Poprawki” są jeszcze gorsze - nie zdawałem sobie sprawy, że to problem przepełnienia i pomyślałem, że popełniłem logiczny błąd. W konsekwencji pierwsze „poprawki” nic nie zmieniły; Właśnie odwróciłem
Daniel Brückner,
10
logikę i rozrzuciłem błąd. Tutaj popełniłem kolejne błędy; jak już wspomniał Eric, tak naprawdę nie analizowałem błędu i po prostu zrobiłem pierwszą rzecz, która wydawała się właściwa. I nadal nie korzystałem z VisualStudio. Dobra, spieszyłem się i nie spędziłem więcej niż pięć minut na „poprawce”, ale to nie powinno być wymówką. Po tym, jak Eric wielokrotnie wskazywał na błąd, uruchomiłem VisualStudio i znalazłem prawdziwy problem. Poprawka wykorzystująca Sign () czyni tę rzecz jeszcze bardziej nieczytelną i zamienia ją w kod, którego tak naprawdę nie chcesz utrzymywać. Nauczyłem się tej lekcji i nie będę już nie doceniał, jak podstępne
Daniel Brückner,
-2

Niektóre z powyższych odpowiedzi używają liczb zmiennoprzecinkowych, jest to nieefektywne i naprawdę nie jest konieczne. W przypadku znaków bez znaku jest to skuteczna odpowiedź dla int1 / int2:

(int1 == 0) ? 0 : (int1 - 1) / int2 + 1;

W przypadku podpisanych ints nie będzie to poprawne

Tom Mensink
źródło
Nie to, o co prosi OP w pierwszej kolejności, tak naprawdę nie dodaje się do innych odpowiedzi.
Santamanno
-4

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

Gdy użyjesz kodu odpowiedzi z @jerryjvl

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

wystąpił błąd zaokrąglenia. 1/5 zaokrągliby w górę, ponieważ 1% 5! = 0. Ale to źle, ponieważ zaokrąglanie nastąpi tylko wtedy, gdy zamienisz 1 na 3, więc wynik wynosi 0,6. Musimy znaleźć sposób na zaokrąglenie w górę, gdy obliczenia dają nam wartość większą lub równą 0,5. Wynik operatora modulo w górnym przykładzie ma zakres od 0 do myInt2-1. Zaokrąglenie nastąpi tylko wtedy, gdy reszta jest większa niż 50% dzielnika. Skorygowany kod wygląda następująco:

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

Oczywiście mamy również problem z zaokrąglaniem na myInt2 / 2, ale ten wynik da ci lepsze rozwiązanie zaokrąglania niż inne na tej stronie.

raboni
źródło
„Musimy znaleźć sposób na zaokrąglenie w górę, gdy obliczenia dają nam wartość większą lub równą 0,5” - nie trafiłeś w sedno tego pytania - lub zawsze zaokrąglamy w górę, tj. OP chce zaokrąglić w górę 0,001 do 1.
Grhm