Szybki pułap podziału liczb całkowitych w C / C ++

Podane wartości liczb całkowitych xoraz yC i C ++ zwracają jako iloraz q = x/ypodłogi ekwiwalentu zmiennoprzecinkowego. Zamiast tego interesuje mnie metoda zwrotu sufitu. Na przykład ceil(10/5)=2i ceil(11/5)=3.

Oczywiste podejście obejmuje coś takiego:

q = x / y;
if (q * y < x) ++q;

Wymaga to dodatkowego porównania i pomnożenia; a inne metody, które widziałem (w rzeczywistości stosowały), polegały na rzucaniu jako a floatlub double. Czy istnieje bardziej bezpośrednia metoda, która pozwala uniknąć dodatkowego mnożenia (lub drugiego podziału) i rozgałęzienia, a także pozwala uniknąć rzutowania jako liczby zmiennoprzecinkowej?

Dla liczb dodatnich

unsigned int x, y, q;

Aby zaokrąglić w górę ...

q = (x + y - 1) / y;

lub (unikając przepełnienia x + y)

q = 1 + ((x - 1) / y); // if x != 0

Dla liczb dodatnich:

    q = x/y + (x % y != 0);

Odpowiedź Sparky jest jednym ze standardowych sposobów rozwiązania tego problemu, ale jak napisałem również w moim komentarzu, istnieje ryzyko przepełnienia. Można to rozwiązać za pomocą szerszego typu, ale co jeśli chcesz podzielić long longs?

Odpowiedź Nathana Ernsta zapewnia jedno rozwiązanie, ale wymaga wywołania funkcji, deklaracji zmiennej i warunku, co czyni go nie mniejszym niż kod OP i prawdopodobnie nawet wolniejszym, ponieważ trudniej go zoptymalizować.

Moje rozwiązanie jest następujące:

q = (x % y) ? x / y + 1 : x / y;

Będzie to nieco szybsze niż kod OPs, ponieważ modulo i podział są wykonywane przy użyciu tej samej instrukcji procesora, ponieważ kompilator widzi, że są one równoważne. Przynajmniej gcc 4.4.1 wykonuje tę optymalizację z flagą -O2 na x86.

Teoretycznie kompilator może wstawiać wywołanie funkcji w kodzie Nathana Ernsta i emitować to samo, ale gcc tego nie zrobił, kiedy go testowałem. Może tak być, ponieważ wiązałoby skompilowany kod z jedną wersją standardowej biblioteki.

Na koniec, żadna z tych kwestii nie ma znaczenia na nowoczesnym komputerze, z wyjątkiem sytuacji, gdy jesteś w bardzo ciasnej pętli, a wszystkie twoje dane znajdują się w rejestrach lub pamięci podręcznej L1. W przeciwnym razie wszystkie te rozwiązania będą równie szybkie, z wyjątkiem ewentualnie Nathana Ernsta, które mogą być znacznie wolniejsze, jeśli funkcja musi zostać pobrana z pamięci głównej.

Możesz użyć divfunkcji w cstdlib, aby uzyskać iloraz i resztę w jednym wywołaniu, a następnie osobno obsłużyć sufit, jak w poniższym

#include <cstdlib>
#include <iostream>

int div_ceil(int numerator, int denominator)
{
        std::div_t res = std::div(numerator, denominator);
        return res.rem ? (res.quot + 1) : res.quot;
}

int main(int, const char**)
{
        std::cout << "10 / 5 = " << div_ceil(10, 5) << std::endl;
        std::cout << "11 / 5 = " << div_ceil(11, 5) << std::endl;

        return 0;
}

Co powiesz na to? (wymaga y nieujemnego, więc nie używaj tego w rzadkim przypadku, gdy y jest zmienną bez gwarancji nieujemności)

q = (x > 0)? 1 + (x - 1)/y: (x / y);

Zmniejszyłem y/ydo jednego, eliminując termin, x + y - 1a wraz z nim wszelkie szanse na przepełnienie.

Unikam x - 1zawijania, gdy xjest to typ bez znaku i zawiera zero.

W przypadku znaku x, ujemne i zero nadal łączą się w jeden przypadek.

Prawdopodobnie nie jest to ogromna zaleta nowoczesnego procesora ogólnego zastosowania, ale byłoby to znacznie szybsze w systemie wbudowanym niż jakakolwiek inna poprawna odpowiedź.

Istnieje rozwiązanie zarówno pozytywne, jak i negatywne, xale tylko pozytywne yz tylko 1 dywizją i bez rozgałęzień:

int ceil(int x, int y) {
    return x / y + (x % y > 0);
}

Zauważ, że jeśli xjest dodatni, wówczas podział jest w kierunku zera i powinniśmy dodać 1, jeśli przypomnienie nie jest zerem.

Jeśli xjest ujemne, wówczas podział jest w kierunku zera, to jest to, czego potrzebujemy i nie dodamy niczego, ponieważ x % ynie jest dodatnie

Działa to dla liczb dodatnich lub ujemnych:

q = x / y + ((x % y != 0) ? !((x > 0) ^ (y > 0)) : 0);

Jeśli pozostała część, sprawdź, czy xi ysą tego samego znaku, i 1odpowiednio dodaje .

Wolałbym skomentować, ale nie mam wystarczająco wysokiego przedstawiciela.

O ile mi wiadomo, dla pozytywnych argumentów i dzielnika, który jest potęgą 2, jest to najszybszy sposób (testowany w CUDA):

//example y=8
q = (x >> 3) + !!(x & 7);

Tylko w przypadku ogólnych argumentów pozytywnych zwykle robię to tak:

q = x/y + !!(x % y);

uproszczona forma ogólna,

int div_up(int n, int d) {
    return n / d + (((n < 0) ^ (d > 0)) && (n % d));
} //i.e. +1 iff (not exact int && positive result)

Aby uzyskać bardziej ogólną odpowiedź, funkcje C ++ do dzielenia liczb całkowitych z dobrze zdefiniowaną strategią zaokrąglania

Kompiluj z O3, kompilator dobrze wykonuje optymalizację.

q = x / y;
if (x % y)  ++q;