Dzielenie dwóch liczb całkowitych i zaokrąglanie wyniku bez użycia zmiennoprzecinkowej

Question

Potrzebuję podzielić dwie liczby i zaokrąglić je w górę. Czy istnieje lepszy sposób na zrobienie tego?

int myValue = (int) ceil((float)myIntNumber/myOtherInt); 

Znajduję przesadę, aby rzucić dwa razy. (Extern int obsada jest po prostu wyłączyć ostrzeżenie)

Uwaga muszę rzucać wewnętrznie unosić inaczej

int a = ceil(256/11); //> Should be 24, but it is 23 
       ^example 

Answer 1

Z pomocą DYP, wpadł na poniższym branchless wzoru:

int idiv_ceil (int numerator, int denominator) 
{ 
    return numerator/denominator 
      + (((numerator < 0)^(denominator > 0)) && (numerator%denominator)); 
} 

Unika konwersje zmiennoprzecinkowe i przechodzi podstawowy zestaw testów jednostkowych, jak pokazano poniżej:

• http://ideone.com/3OrviU

---

Oto kolejna wersja która unika operatora modulo.

int idiv_ceil (int numerator, int denominator) 
{ 
    int truncated = numerator/denominator; 
    return truncated + (((numerator < 0)^(denominator > 0)) && 
              (numerator - truncated*denominator)); 
} 

• http://ideone.com/Z41G5q

Pierwszy będzie szybsze procesory gdzie IDIV przywraca zarówno iloraz i pozostałość (i kompilator wystarczająco silny, aby korzystać z tego).

Answer 2

Zakładając, że zarówno myIntNumber i myOtherInt są pozytywne, można zrobić:

int myValue = (myIntNumber + myOtherInt - 1)/myOtherInt; 

Answer 3

Zamiast używać funkcji ceil przed rzutowaniem na int, możesz dodać stałą, która jest bardzo bliska (ale nie całkiem) równa 1 - w ten sposób prawie wszystko (z wyjątkiem wartości, która jest dokładnie lub bardzo zbliżona do rzeczywistej liczba całkowita) będzie zwiększone o jeden, zanim zostanie obcięte.

Przykład:

#define EPSILON (0.9999) 

int myValue = (int)(((float)myIntNumber)/myOtherInt + EPSILON); 

EDIT: po obejrzeniu odpowiedź do innego wątku, chciałbym wyjaśnić, że to będzie zaokrąglić w górę, a nie od zera - liczby ujemne staną się mniej negatywny, a liczbami dodatnimi będzie stać się bardziej pozytywnym.

Answer 4

Podział całkowity z zaokrągleniem.

tylko 1 podział wykonywany za połączenie, nie % lub * lub konwersji do/z zmiennoprzecinkowych, pracuje dla dodatniego i ujemnego int. Patrz uwaga (1).

n (numerator) = OPs myIntNumber; 
d (denominator) = OPs myOtherInt; 

Poniższe podejście jest proste. int runda dywizji w kierunku 0. Dla ujemnych kwot, jest to zaokrąglenie w górę, więc nic specjalnego nie jest potrzebne. Aby uzyskać dodatnie ilorazy, dodaj d-1, aby wykonać zaokrąglenie, a następnie wykonaj podział bez znaku.

Uwaga (1) Typowy podział według 0 wysadza w powietrze i MININT/-1 zawiedzie zgodnie z oczekiwaniami na maszynach drugiego stopnia.

int IntDivRoundUp(int n, int d) { 
    // If n and d are the same sign ... 
    if ((n < 0) == (d < 0)) { 
    // If n (and d) are negative ... 
    if (n < 0) { 
     n = -n; 
     d = -d; 
    } 
    // Unsigned division rounds down. Adding d-1 to n effects a round up. 
    return (((unsigned) n) + ((unsigned) d) - 1)/((unsigned) d); 
    } 
    else { 
    return n/d; 
    } 
} 

---

[Edycja: Kod testu usunięta, zobacz wcześniej rev jako potrzebne źródło]

Answer 5

Wystarczy użyć

int ceil_of_division = ((dividend-1)/divisor)+1; 

Na przykład:

for (int i=0;i<20;i++) 
    std::cout << i << "/8 = " << ((i-1)/8)+1 << std::endl; 

Answer 6

Być może jest to po prostu łatwiej zrobić:

int result = dividend/divisor; 
if(dividend % divisor != 0) 
    result++; 

Answer 7

mały kilof to zrobić:

int divideUp(int a, int b) { 
    result = (a-1)/b + 1; 
} 
// Proof: 
a = b*N + k (always) 
if k == 0, then 
    (a-1)  == b*N - 1 
    (a-1)/b  == N - 1 
    (a-1)/b + 1 == N ---> Good ! 

if k > 0, then 
    (a-1)  == b*N + l 
    (a-1)/b  == N 
    (a-1)/b + 1 == N+1 ---> Good !