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

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)

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ą.

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

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)

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

Możesz napisać pomocnika.

static int DivideRoundUp(int p1, int p2) {
  return (int)Math.Ceiling((double)p1 / p2);
}

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

a / b + ((Math.Sign(a) * Math.Sign(b) > 0) && (a % b != 0)) ? 1 : 0)

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

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.