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

262

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?

i i
źródło
70
instrukcja dzielenia często zwraca jednocześnie iloraz i resztę, więc nie ma potrzeby mnożenia, q = x/y + (x % y != 0);wystarczy
phuclv 25.01.2014
2
@ LưuVĩnhPhúc ten komentarz powinien być zaakceptowaną odpowiedzią, imo.
Andreas Grapentin
1
@ LưuVĩnhPhúc Poważnie, musisz dodać to jako odpowiedź. Właśnie użyłem tego do mojej odpowiedzi podczas testu kodowania. Działało to jak urok, choć nie jestem pewien, jak działa modowa część odpowiedzi, ale zadziałało.
Zachary Kraus
2
@AndreasGrapentin poniżej odpowiedź Miguela Figueiredo została przesłana na prawie rok przed pozostawieniem komentarza przez Lưu Vĩnh Phúc. Chociaż rozumiem, jak atrakcyjne i eleganckie jest rozwiązanie Miguela, nie jestem skłonny do zmiany przyjętej odpowiedzi w tak późnym terminie. Oba podejścia pozostają zdrowe. Jeśli czujesz się wystarczająco mocno, sugeruję, abyś wyraził swoje poparcie, głosując odpowiedź Miguela poniżej.
i
1
Dziwne, nie widziałem żadnego rozsądnego pomiaru ani analizy proponowanych rozwiązań. Mówisz o prędkości w pobliżu kości, ale nie ma dyskusji na temat architektur, rurociągów, instrukcji rozgałęziania i cykli zegara.
Rado,

Odpowiedzi:

394

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
iskrzący
źródło
6
@bitc: W przypadku liczb ujemnych uważam, że C99 określa wartość od zera do zera, podobnie x/yjak pułap podziału. C90 nie określił, jak zaokrąglać, i nie sądzę, aby obecny standard C ++ również.
David Thornley,
6
Zobacz post Erica Lipperta: stackoverflow.com/questions/921180/c-round-up/926806#926806
Mashmagar
3
Uwaga: to może się przepełnić. q = ((długi długi) x + y - 1) / y nie będzie. Mój kod jest jednak wolniejszy, więc jeśli wiesz, że twoje liczby się nie przepełnią, powinieneś użyć wersji Sparky.
Jørgen Fogh
1
@bitc: Uważam, że David miał na myśli to, że nie użyłbyś powyższego obliczenia, jeśli wynik byłby negatywny - po prostu q = x / y;
użyłbyś
12
Drugi ma problem, w którym x wynosi 0. ceil (0 / r) = 0, ale zwraca 1.
Omry Yadan
78

Dla liczb dodatnich:

    q = x/y + (x % y != 0);
Miguel Figueiredo
źródło
5
najczęstsza instrukcja dzielenia architektury zawiera również pozostałą część wyniku, więc to naprawdę potrzebuje tylko jednego podziału i byłoby bardzo szybkie
phuclv
58

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.

Jørgen Fogh
źródło
3
Był łatwiejszy sposób, aby naprawić przepełnienie, po prostu zmniejsz r / r:q = (x > 0)? 1 + (x - 1)/y: (x / y);
Ben Voigt
-1: jest to nieefektywny sposób, ponieważ handluje tanim * za kosztowny%; gorsze niż podejście PO.
Yves Daoust
2
Nie. Jak wyjaśniłem w odpowiedzi, operator% jest bezpłatny, gdy już wykonujesz podział.
Jørgen Fogh
1
Czy q = x / y + (x % y > 0);to jest łatwiejsze niż ? :wyrażenie?
Han
To zależy od tego, co rozumiesz przez „łatwiej”. Może być lub nie być szybszy, w zależności od tego, jak kompilator to przetłumaczy. Domyślam się wolniej, ale musiałbym to zmierzyć, aby się upewnić.
Jørgen Fogh
18

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;
}
Nathan Ernst
źródło
12
Jako interesujący przypadek podwójnego wybuchu można również return res.quot + !!res.rem;:)
Sam Harwell
Czy ldiv nie zawsze promuje argumenty w długie długie? A czy to nic nie kosztuje, casting lub casting?
einpoklum
12

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

Ben Voigt
źródło
Twój inny zawsze zwróci 0, nie musisz niczego obliczać.
Ruud Althuizen
@Ruud: nieprawda. Rozważmy x = -45 iy = 4
Ben Voigt
7

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

RiaD
źródło
ciekawe, ponieważ zdarzają się częste przypadki, gdy y jest stały
Wolf
1
mod wymaga podziału, więc nie jest to tylko 1 podział tutaj, ale być może komplement może zoptymalizować dwa podobne podziały w jeden.
M.kazem Akhgary
4

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 .

Mark Conway
źródło
3

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);
Anroca
źródło
Byłoby ciekawie zobaczyć, jak q = x/y + !!(x % y);radzi sobie q = x/y + (x % y == 0);i jakie są q = (x + y - 1) / y;rozwiązania pod względem wydajności we współczesnej CUDA.
Greg Kramida
-2

Kompiluj z O3, kompilator dobrze wykonuje optymalizację.

q = x / y;
if (x % y)  ++q;
dhb
źródło