Jakiej lepszej opcji użyć do podzielenia liczby całkowitej przez 2?

406

Która z poniższych technik jest najlepszą opcją do podzielenia liczby całkowitej przez 2 i dlaczego?

Technika 1:

x = x >> 1;

Technika 2:

x = x / 2;

Oto xliczba całkowita.

— Abhineet
źródło

75

Jeśli naprawdę chcesz ponownie przypisać wynik x, żadna z nich nie jest odpowiednia w ten sposób: powinna być albo, x >>= 1albo x /= 2, w zależności od tego, co zamierzasz wyrazić za pomocą operacji. Nie dlatego, że jest szybszy (każdy nowoczesny kompilator i tak skompiluje wszystkie równoważne warianty do identycznego, szybkiego zestawu), ale dlatego, że jest mniej mylący.

— lewo około

33

Nie zgadzam się z lewej strony wokół. - Ale myślę, że warto zauważyć, że istnieje operacja zwana przesunięciem arytmetycznym w wielu językach programowania, która utrzymuje bit znaku na miejscu i dlatego działa dla podpisanych wartości zgodnie z oczekiwaniami. Składnia może być podobna x = x >>> 1. Należy również pamiętać, że w zależności od platformy i kompilatora może być całkiem uzasadnione ręczne optymalizowanie podziałów i mnożenia za pomocą przesunięć. - Myśląc na przykład o mikrokontrolerach, bez bezpośredniej obsługi ALU dla mnożenia.

— JimmyB

36

Wolę, x /= 2ponieważ x >>= 1zbyt przypomina monadic bind;)

— fredoverflow

19

@leftaroundabout - po prostu uznać, że o wiele bardziej czytelne napisać x = x / 2zamiast x /= 2. Subiektywne preferencje może :)

— JimmyB

8

@ HannoBinder: z pewnością subiektywne, w szczególności dużo nawyków. IMO, w języku, w którym wszystkie operatory arytmetyczne mają ⬜=kombinacje, należy ich używać, gdy tylko jest to możliwe. Usuwa hałas i kładzie nacisk na fakt, że xjest modyfikowany , podczas gdy główny =operator raczej sugeruje, że przyjmuje zupełnie nową wartość, niezależnie od starej. - Zawsze unikając operatorów połączonych (tak, to czytelny więc ktoś, kto zna tylko operatorów matematycznych) może mieć swój punkt jak dobrze, ale wtedy trzeba by zrezygnować z niezwykle przydatna ++, --, +=, too.

— lewo około

847

Użyj operacji, która najlepiej opisuje to, co próbujesz zrobić.

Jeśli traktujesz liczbę jako ciąg bitów, użyj przesunięcia bitów.
Jeśli traktujesz to jako wartość liczbową, użyj podziału.

Pamiętaj, że nie są dokładnie równoważne. Mogą dawać różne wyniki dla liczb całkowitych ujemnych. Na przykład:

-5 / 2  = -2
-5 >> 1 = -3

(ideone)

— Mark Byers
źródło

20

Pierwotne pytanie było również niejasne co do terminu „najlepszy”. „Najlepsze” pod względem szybkości, czytelności, pytania egzaminacyjnego, aby oszukać studentów itp. Wobec braku wyjaśnienia, co oznacza „najlepszy”, wydaje się to najbardziej poprawna odpowiedź.

— Ray

47

W C ++ 03 oba są implementacjami zdefiniowanymi dla liczb ujemnych i mogą dawać takie same wyniki. W C ++ 11 podział jest dobrze zdefiniowany dla liczb ujemnych, ale przesunięcie jest nadal zdefiniowane w implementacji.

— James Kanze

2

Podczas gdy definicją / jest implementacja (robi się, jeśli zaokrągla w górę lub w dół dla liczb ujemnych) zdefiniowana we wczesnych standardach C. Musi zawsze być zgodny z% (operator modulo / reszta).

— ctrl-alt-delor

7

„Zdefiniowana implementacja” oznacza, że implementator kompilatora musiał wybrać spośród kilku opcji implementacji, zwykle z istotnymi ograniczeniami. Tutaj jednym ograniczeniem jest to, że operatory %i /muszą być spójne zarówno dla argumentów dodatnich, jak i ujemnych, aby było (a/b)*b+(a%b)==ato prawdą niezależnie od znaków ai b. Zazwyczaj autor dokonuje wyborów zapewniających najlepszą możliwą wydajność procesora.

— RBerteig

6

Więc każdy, kto mówi „kompilator i tak przekształci go na zmianę”, jest w błędzie, prawda? O ile kompilator nie może zagwarantować, że masz do czynienia z nieujemną liczbą całkowitą (albo stałą, albo liczbą całkowitą bez znaku), nie może zmienić jej na zmianę

— Kip

225

Czy ten pierwszy wygląda na dzielenie? Nie. Jeśli chcesz podzielić, użyj x / 2. Kompilator może go zoptymalizować pod kątem przesunięcia bitów, jeśli to możliwe (nazywa się to redukcją siły), co czyni go bezużyteczną mikrooptymalizacją, jeśli robisz to sam.

— Cat Plus Plus
źródło

15

Wiele kompilatorów nie przekształci dzielenia siłą dwóch w przesunięcie bitów. Byłaby to niepoprawna optymalizacja dla liczb całkowitych ze znakiem. Powinieneś spróbować spojrzeć na dane wyjściowe zestawu z kompilatora i przekonać się sam.

— exDM69

1

IIRC Użyłem tego, aby przyspieszyć równoległą redukcję na CUDA (unikaj dzielenia na liczby całkowite). Jednak było to ponad rok temu, zastanawiam się, jak inteligentne są obecnie kompilatory CUDA.

— Nils

9

@ exDM69: Wiele kompilatorów zrobi to nawet dla podpisanych liczb całkowitych i po prostu dostosuje je zgodnie z podpisaniem. Ładne narzędzie do zabawy tymi rzeczami to: tinyurl.com/6uww253

— PlasmaHH

19

@ exDM69: I to jest istotne, jak? Powiedziałem „jeśli to możliwe”, nie „zawsze”. Jeśli optymalizacja jest niepoprawna, to wykonanie jej ręcznie nie poprawia jej (ponadto, jak wspomniano, GCC jest wystarczająco sprytny, aby znaleźć właściwą zamianę na podpisane liczby całkowite).

— Cat Plus Plus

4

Patrząc na stronę WikiPedia, jest to pozornie kontrowersyjne, ale nie nazwałbym tego zmniejszeniem siły. Zmniejszenie siły ma miejsce wtedy, gdy w pętli zmniejsza się, na przykład, od mnożenia do dodawania, dodając do poprzednich wartości w pętli. Jest to raczej optymalizacja wizjera, którą kompilatory mogą wykonać całkiem niezawodnie.

— SomeCallMeTim

189

Kupowanie: istnieje wiele powodów, dla których warto skorzystać z x = x / 2; Oto kilka:

wyraźniej wyraża twoją intencję (zakładając, że nie masz do czynienia z bitami rejestru bitowymi lub czymś podobnym)
kompilator i tak zredukuje to do zmiany
nawet jeśli kompilator nie zmniejszył go i wybrał wolniejszą operację niż zmiana, prawdopodobieństwo, że wpłynie to na wydajność twojego programu w wymierny sposób, samo w sobie jest znikomo małe (a jeśli ma to wymierny wpływ, to masz rzeczywistą powód, aby użyć zmiany)
jeśli podział będzie częścią większego wyrażenia, bardziej prawdopodobne jest uzyskanie pierwszeństwa, jeśli użyjesz operatora dzielenia:
```
x = x / 2 + 5;
x = x >> 1 + 5;  // not the same as above
```
podpisana arytmetyka może komplikować sprawy jeszcze bardziej niż wspomniany wyżej problem pierwszeństwa
Powtórzmy - kompilator i tak zrobi to za ciebie. W rzeczywistości przekształci dzielenie przez stałą na serię przesunięć, sum i mnożeń dla wszystkich rodzajów liczb, nie tylko potęg dwóch. Zobacz to pytanie, aby uzyskać dostęp do dodatkowych informacji na ten temat.

Krótko mówiąc, nic nie kupujesz, kodując zmianę, gdy naprawdę chcesz pomnożyć lub podzielić, z wyjątkiem być może zwiększonej możliwości wprowadzenia błędu. Minęło całe życie, odkąd kompilatory nie były wystarczająco inteligentne, aby w razie potrzeby zoptymalizować tego rodzaju zmiany.

— Michael Burr
źródło

5

Warto również dodać, że chociaż istnieją zasady pierwszeństwa, stosowanie nawiasów nie jest niczym złym. Podczas przebudowy jakiegoś kodu produkcyjnego faktycznie widziałem coś w formie a/b/c*d(gdzie a..doznaczono zmienne numeryczne) zamiast o wiele bardziej czytelnego (a*d)/(b*c).

1

Wydajność i optymalizacje zależą od kompilatora i celu. Na przykład pracuję dla mikrokontrolera, w którym wszystko wyższe niż -O0 jest wyłączone, chyba że kupisz komercyjny kompilator, więc kompilator na pewno nie zmieni podziału na przesunięcia bitów. Co więcej, przesunięcia bitów zajmują jeden cykl, a podział zajmuje 18 cykli na tym celu, a ponieważ szybkość zegara mikrokontrolerów jest dość niska, może to być rzeczywiście zauważalny spadek wydajności (ale zależy to od twojego kodu - powinieneś zdecydowanie użyć / dopóki profilowanie ci nie powie to problem!)

4

@JackManey, jeśli istnieje jakakolwiek możliwość spowodowania a*dlub b*cprzepełnienia, mniej czytelna forma nie jest równoważna i ma oczywistą zaletę. PS Zgadzam się, że nawiasy są twoim najlepszym przyjacielem.

— Mark Ransom

@MarkRansom - Racja (chociaż wpadłem na a/b/c*dkod R - w kontekście, w którym przepełnienie oznaczałoby, że coś było poważnie nie tak z danymi - a nie, powiedzmy, w krytycznym dla wydajności bloku kodu C).

Kod x=x/2;jest tylko „wyraźniejszy” niż x>>=1wtedy x, gdy nigdy nie będzie nieparzystą liczbą ujemną lub nikt nie przejmuje się błędami pojedynczymi. W przeciwnym razie x=x/2;i x>>=1;mają różne znaczenia. Jeśli potrzebna jest wartość obliczona przez x>>=1, uważałbym to za jaśniejsze niż x = (x & ~1)/2lub x = (x < 0) ? (x-1)/2 : x/2, lub jakikolwiek inny sposób, który mogę pomyśleć o zastosowaniu podziału na dwa. Podobnie, jeśli potrzebna jest obliczona wartość x/=2, to jest wyraźniejsze niż ((x + ((unsigned)x>>31)>>1).

— supercat

62

Która z nich jest najlepszą opcją i dlaczego warto podzielić liczbę całkowitą przez 2?

Zależy co masz na myśli najlepiej .

Jeśli chcesz, aby twoi koledzy cię nienawidzili lub utrudniali czytanie kodu, zdecydowanie wybrałbym pierwszą opcję.

Jeśli chcesz podzielić liczbę przez 2, przejdź do drugiej.

Te dwa nie są równoważne, nie zachowują się tak samo, jeśli liczba jest ujemna lub wewnątrz większych wyrażeń - przesunięcie bitowe ma niższy priorytet niż +lub -, podział ma wyższy priorytet.

Powinieneś napisać kod, aby wyrazić jego zamiary. Jeśli zależy Ci na wydajności, nie martw się, optymalizator wykonuje dobrą robotę przy tego rodzaju mikrooptymalizacjach.

— Luchian Grigore
źródło

58

Wystarczy użyć divide ( /), zakładając, że jest to bardziej przejrzyste. Kompilator odpowiednio zoptymalizuje.

— justin
źródło

34

Kompilator powinien odpowiednio zoptymalizować.

— Noctis Skytower

12

Jeśli kompilator nie zoptymalizuje się odpowiednio, powinieneś użyć lepszego kompilatora.

— David Stone

3

@DavidStone: Na jakich procesorach kompilator może zoptymalizować dzielenie liczby całkowitej ze znakiem prawdopodobnie ujemnym przez dowolną stałą inną niż 1, aby był tak wydajny jak przesunięcie?

— supercat

1

@ supercat: To dobra uwaga. Możesz oczywiście zapisać wartość w liczbach całkowitych bez znaku (co, jak sądzę, ma znacznie gorszą reputację niż w połączeniu z ostrzeżeniami o niedopasowanym podpisaniu / niepodpisaniu), a większość kompilatorów ma również sposób, aby powiedzieć im, że coś jest prawdą podczas optymalizacji . Wolałbym zawijanie że w zgodności makro i mieć coś podobnego ASSUME(x >= 0); x /= 2;nad x >>= 1;, ale to jest nadal ważnym punktem wychowywać.

— David Stone

39

Zgadzam się z innymi odpowiedziami, które należy faworyzować x / 2 ponieważ jego zamiary są jaśniejsze, a kompilator powinien go zoptymalizować.

Jednak kolejny powód, dla preferujących x / 2na x >> 1to, że zachowanie >>jest zależna od implementacji jeśli xjest podpisana inti jest ujemna.

Z sekcji 6.5.7 punkt 5 normy ISO C99:

Wynikiem E1 >> E2są E1przesunięte w prawo E2pozycje bitów. Jeśli E1ma typ bez znaku lub E1ma typ ze znakiem i nieujemną wartość, wartość wyniku jest integralną częścią ilorazu E1/ 2 ^E2. Jeśli E1ma typ ze znakiem i wartość ujemną, wartość wynikowa jest zdefiniowana w implementacji.

— jamesdlin
źródło

3

Warto zauważyć, że zachowanie, które wiele implementacji definiuje dla x>>scalepowerliczb ujemnych, będzie dokładnie tym, czego potrzeba, dzieląc wartość przez potęgę dwóch do celów takich jak renderowanie ekranu, podczas gdy użycie x/scalefactorbędzie nieprawidłowe, chyba że zastosuje się poprawki do wartości ujemnych.

— supercat,

32

x / 2jest bardziej przejrzysty i x >> 1nie jest dużo szybszy (według mikro-testu porównawczego, około 30% szybszy dla JVM Java). Jak zauważyli inni, w przypadku liczb ujemnych zaokrąglenie jest nieco inne, więc należy wziąć to pod uwagę, gdy chcesz przetwarzać liczby ujemne. Niektóre kompilatory mogą się automatycznie konwertować x / 2nax >> 1 , jeśli wiedzą, że liczba ta nie może być ujemna (nawet, że nie mogłem to sprawdzić).

Nawet x / 2nie może używać instrukcji procesora (powolnego) podziału, ponieważ niektóre skróty są możliwe , ale wciąż jest wolniejsze niż x >> 1.

(Jest to C / C ++ pytanie, inne języki programowania mają więcej operatorów. Dla Java istnieje również bez znaku prawy shift x >>> 1, który jest znowu inny. To pozwala prawidłowo obliczyć średnią (średnia) wartość dwóch wartości, tak że (a + b) >>> 1woli zwraca wartość średnią nawet dla bardzo dużych wartości ai b. Jest to wymagane na przykład do wyszukiwania binarnego, jeśli indeksy tablic mogą być bardzo duże. Wystąpił błąd w wielu wersjach wyszukiwania binarnego , ponieważ używano ich (a + b) / 2do obliczania średniej. nie działa poprawnie. (a + b) >>> 1Zamiast tego należy użyć poprawnego rozwiązania .)

— Thomas Mueller
źródło

1

Kompilatory nie mogą przekonwertować x/2na x>>1przypadki, w których xmogą być ujemne. Jeśli pragniemy wartości, która x>>1byłaby obliczona, prawie na pewno będzie szybsza niż jakiekolwiek wyrażenie, x/2które oblicza tę samą wartość.

— supercat

Masz rację. A kompilatory może konwertować tylko x/2do x>>1jeśli zna wartość nie jest negatywna. Spróbuję zaktualizować swoją odpowiedź.

— Thomas Mueller,

kompilatory wciąż unikają divinstrukcji, konwertując x/2na (x + (x<0?1:0)) >> 1(gdzie >> jest arytmetyką przesunięcia w prawo, która zmienia bity znakowe). Wymaga to 4 instrukcji: skopiuj wartość, shr (aby uzyskać tylko bit znaku w reg), dodaj, sar. goo.gl/4F8Ms4

— Peter Cordes

Pytanie jest oznaczone jako C i C ++.

— Josh Sanford

22

Knuth powiedział:

Przedwczesna optymalizacja jest źródłem wszelkiego zła.

Więc proponuję użyć x /= 2;

W ten sposób kod jest łatwy do zrozumienia, a także myślę, że optymalizacja tej operacji w tej formie nie oznacza dużej różnicy dla procesora.

— Ivan Californias
źródło

4

Co uważasz za preferowaną metodę zmniejszania liczby o potęgę dwóch, jeśli chcemy, aby liczby całkowite utrzymywały aksjomat (który dotyczy liczb naturalnych i liczb rzeczywistych), że (n + d) / d = (n / d) + 1? Naruszenie tego aksjomatu podczas skalowania grafiki spowoduje widoczne „szwy” w wyniku. Jeśli ktoś chce czegoś, co jest równe i prawie symetryczne względem zera, (n+8)>>4działa dobrze. Czy możesz zaoferować jakieś podejście, które jest tak jasne lub tak efektywne bez korzystania z podpisanej prawej zmiany?

— supercat,

19

Spójrz na dane wyjściowe kompilatora, które pomogą Ci podjąć decyzję. Uruchomiłem ten test na x86-64 z
gcc (GCC) 4.2.1 20070719 [FreeBSD]

Zobacz także wyniki kompilatora online w godbolt .

To, co widzisz, to kompilator sarlw obu przypadkach korzysta z instrukcji (arytmetyczne przesunięcie w prawo), więc rozpoznaje podobieństwo między tymi dwoma wyrażeniami. Jeśli użyjesz podziału, kompilator musi również dostosować liczby ujemne. W tym celu przesuwa bit znaku do bitu najniższego rzędu i dodaje go do wyniku. Rozwiązuje to problem „jeden po drugim” przy przesuwaniu liczb ujemnych w porównaniu do tego, co zrobiłby podział.
Ponieważ przypadek podziału wykonuje dwie zmiany, podczas gdy wyraźny przypadek zmiany robi tylko jedną, możemy teraz wyjaśnić niektóre różnice wydajności mierzone w innych odpowiedziach tutaj.

Kod C z wyjściem zespołu:

W przypadku podziału twój wkład byłby

int div2signed(int a) {
  return a / 2;
}

i to się kompiluje

    movl    %edi, %eax
    shrl    $31, %eax
    addl    %edi, %eax
    sarl    %eax
    ret

podobnie do zmiany

int shr2signed(int a) {
  return a >> 1;
}

z wyjściem:

    sarl    %edi
    movl    %edi, %eax
    ret

— Michael Donohue
źródło

W zależności od tego, co się robi, może naprawić błąd „jeden po drugim” lub może powodować błąd „jeden po drugim” (w porównaniu z tym, co jest rzeczywiście potrzebne), co będzie wymagało użycia dodatkowego kodu do jego naprawy. Jeśli to, czego się chce, to efekt płynny, przesunięcie w prawo jest szybsze i łatwiejsze niż jakakolwiek alternatywa, o której wiem.

— supercat

Jeśli potrzebujesz podłogi, jest mało prawdopodobne, że określisz to, co chcesz, jako „dzielenie przez 2”

— Michael Donohue

Podział liczb naturalnych i liczb rzeczywistych podtrzymuje aksjomat, który (n + d) / d = (n / d) +1. Podział liczb rzeczywistych również podtrzymuje (-n) / d = - (n / d), aksjomat, który nie ma znaczenia dla liczb naturalnych. Nie można mieć operatora dzielenia, który jest zamknięty na liczbach całkowitych i podtrzymuje oba aksjomaty. Moim zdaniem powiedzenie, że pierwszy aksjomat powinien obowiązywać dla wszystkich liczb, a drugi tylko dla liczb rzeczywistych, wydaje się bardziej naturalne niż stwierdzenie, że pierwszy powinien dotyczyć liczb całkowitych lub liczb rzeczywistych, ale nie liczb całkowitych. Ponadto ciekawi mnie, w jakich przypadkach drugi aksjomat jest rzeczywiście przydatny .

— supercat

1

Metoda podziału na liczby całkowite, która spełnia pierwszy aksjomat, podzieli linię liczbową na regiony wielkości d. Takie partycjonowanie jest przydatne do wielu celów. Nawet jeśli wolisz punkt przerwania gdzieś indziej niż między 0 a -1, dodanie przesunięcia spowoduje jego przesunięcie. Podział liczb całkowitych, który spełnia drugi aksjomat, podzieli linię liczbową na regiony, które są przeważnie wielkości d, ale jeden z nich ma rozmiar 2*d-1. Niezupełnie „równe” podziały. Czy możesz podać sugestie, kiedy partycja z nieparzystą kulą jest rzeczywiście przydatna?

— supercat,

Dane wyjściowe kompilatora dla shr2signed są nieprawidłowe. gcc na x86 wybiera zaimplementowanie >> podpisanych liczb całkowitych z przesunięciami arytmetycznymi ( sar). goo.gl/KRgIkb . Ten post z listy mailingowej ( gcc.gnu.org/ml/gcc/2000-04/msg00152.html ) potwierdza, że gcc historycznie używa przesunięć arytmetycznych dla podpisanych znaków int , więc jest bardzo mało prawdopodobne, że FreeBSD gcc 4.2.1 użył przesunięcia bez znaku. Zaktualizowałem twój post, aby to naprawić, i na początku akapitu, mówiąc, że oba użyły Shr, kiedy tak naprawdę SAR używają oboje. SHR to sposób, w jaki wyodrębnia bit znaku dla /sprawy. Zawiera również godbolt link.

— Peter Cordes

15

Tylko dodana notatka -

x * = 0,5 często będzie szybszy w niektórych językach opartych na maszynach wirtualnych - zwłaszcza w ActionScript, ponieważ zmienna nie będzie musiała być sprawdzana pod kątem dzielenia przez 0.

— ansiart
źródło

2

@minitech: To taki zły test. Cały kod w teście jest stały. Zanim kod zostanie nawet JITed, wyeliminuje wszystkie stałe.

@ M28: Byłem całkiem pewien, że elementy wewnętrzne jsPerf (tj. eval) Sprawiły, że stało się to za każdym razem. Niezależnie od tego, tak, jest to dość zły test, ponieważ jest to bardzo głupia optymalizacja.

— Ry-

13

Użyj x = x / 2; LUB x /= 2;Ponieważ możliwe jest, że nowy programista będzie nad nim pracował w przyszłości. Dzięki temu łatwiej będzie mu dowiedzieć się, co się dzieje w wierszu kodu. Każdy może nie być świadomy takich optymalizacji.

— Imdad
źródło

12

Mówię w celu programowania konkursów. Zasadniczo mają one bardzo duże dane wejściowe, w których dzielenie przez 2 odbywa się wiele razy i wiadomo, że dane wejściowe są dodatnie lub ujemne.

x >> 1 będzie lepszy niż x / 2. Sprawdziłem na ideone.com, uruchamiając program, w którym miało miejsce ponad 10 ^ 10 podziałów na 2 operacje. x / 2 zajęło prawie 5,5 s, podczas gdy x >> 1 zajęło prawie 2,6 s dla tego samego programu.

— Shashwat Kumar
źródło

1

Dla wartości bez znaku, kompilator powinny zoptymalizować x/2do x>>1. W przypadku wartości x>>1ze znakiem prawie wszystkie implementacje mają znaczenie, które jest równoważne, x/2ale może być obliczone szybciej, gdy xjest dodatnie, i użytecznie różni się od x/2kiedy xjest ujemne.

— supercat

12

Powiedziałbym, że jest kilka rzeczy do rozważenia.

Przesunięcie bitów powinno być szybsze, ponieważ tak naprawdę nie jest potrzebne żadne specjalne obliczenie do przesunięcia bitów, jednak, jak wskazano, istnieją potencjalne problemy z liczbami ujemnymi. Jeśli masz pewność, że masz liczby dodatnie i szukasz prędkości, poleciłbym bitshift.
Operator podziału jest bardzo łatwy do odczytania przez ludzi. Więc jeśli szukasz czytelności kodu, możesz to wykorzystać. Zwróć uwagę, że pole optymalizacji kompilatora przeszło długą drogę, więc ułatwienie odczytu i zrozumienia kodu jest dobrą praktyką.
W zależności od sprzętu, operacje mogą mieć różne prędkości. Prawo Amdala polega na tym, by pospiesznie posprzątać wspólny przypadek. Możesz mieć sprzęt, który może wykonywać inne operacje szybciej niż inne. Na przykład, mnożenie przez 0,5 może być szybsze niż dzielenie przez 2. (To prawda, że może być konieczne zabranie głosu z mnożenia, jeśli chcesz wymusić dzielenie liczb całkowitych).

Jeśli zależy Ci na czystej wydajności, zaleciłbym utworzenie testów, które mogłyby wykonać operacje miliony razy. Próbkuj wykonanie kilka razy (wielkość twojej próby), aby ustalić, który jest statystycznie najlepszy z twoim OS / Sprzętem / Kompilatorem / Kodem.

— James Oravec
źródło

2

„Bitshift powinien być szybszy”. kompilatory zoptymalizują podział na przesunięcia bitów

— Trevor Hickey

Mam nadzieję, że tak, ale jeśli nie masz dostępu do źródła kompilatora, nie możesz być pewien :)

— James Oravec

1

Poleciłbym również bitshift, jeśli jego implementacja obsługuje go w najczęstszy sposób, a sposób, w jaki chce się obsługiwać liczby ujemne, pasuje do tego, co >>działa, a co /nie.

— supercat

12

Jeśli chodzi o procesor, operacje przesunięcia bitów są szybsze niż operacje dzielenia. Jednak kompilator wie o tym i odpowiednio zoptymalizuje w zakresie, w jakim jest to możliwe, abyś mógł kodować w sposób, który jest najbardziej sensowny, i odpoczywać, wiedząc, że Twój kod działa skutecznie. Pamiętaj jednak, że unsigned intmożna (w niektórych przypadkach) zoptymalizować lepiej niż z intwcześniej wymienionych powodów. Jeśli nie potrzebujesz arytmatyki ze znakiem, nie dołączaj bitu znaku.

— tylerl
źródło

11

x = x / 2; jest odpowiednim kodem do użycia ... ale operacja zależy od twojego programu, w jaki sposób wynik chcesz wygenerować.

— Gooner
źródło

11

Wyjaśnij swoje intencje ... na przykład, jeśli chcesz podzielić, użyj x / 2 i pozwól kompilatorowi zoptymalizować go, aby przesunął operatora (lub cokolwiek innego).

Dzisiejsze procesory nie pozwolą, aby te optymalizacje miały jakikolwiek wpływ na wydajność twoich programów.

— Atul Kumar
źródło

10

Odpowiedź będzie zależeć od środowiska, w którym pracujesz.

Jeśli pracujesz na 8-bitowym mikrokontrolerze lub czymkolwiek bez sprzętowej obsługi mnożenia, przesuwanie bitów jest spodziewane i powszechne, a chociaż kompilator prawie na pewno zmieni się x /= 2wx >>= 1 obecność symbolu podziału podniesie brwi więcej, niż w tym środowisku używając Shift, aby dokonać podziału.
Jeśli pracujesz w środowisku krytycznym pod względem wydajności lub w sekcji kodu lub kod może zostać skompilowany przy wyłączonej optymalizacji kompilatora, x >>= 1komentarz wyjaśniający jego uzasadnienie jest prawdopodobnie najlepszy ze względu na przejrzystość celu.
Jeśli nie spełniasz żadnego z powyższych warunków, spraw, aby Twój kod był bardziej czytelny, po prostu używając x /= 2. Lepiej ocalić kolejnego programistę, który akurat spojrzy na twój kod 10-sekundowe podwójne pobranie operacji zmiany, niż niepotrzebnie dowieść, że wiesz, że zmiana była bardziej wydajna bez optymalizacji kompilatora.

Wszystkie te zakładają liczby całkowite bez znaku. Prosta zmiana prawdopodobnie nie jest tym, co chcesz podpisać. DanielH również porusza kwestię używania x *= 0.5niektórych języków, takich jak ActionScript.

— gkimsey
źródło

8

mod 2, test na = 1. nie znamy składni w c. ale to może być najszybsze.

— circusdei
źródło

7

ogólnie właściwa zmiana dzieli:

q = i >> n; is the same as: q = i / 2**n;

czasami jest to wykorzystywane do przyspieszenia programów kosztem przejrzystości. Nie sądzę, że powinieneś to zrobić. Kompilator jest wystarczająco inteligentny, aby automatycznie wykonać przyspieszenie. Oznacza to, że wprowadzenie zmiany nic nie kosztuje kosztem przejrzystości .

Spójrz na tę stronę z praktycznego programowania w C ++.

— Mouna Cheikhna
źródło

Jeśli ktoś chce obliczyć wartość, która np. (x+128)>>8Obliczyłaby dla wartości xnie bliskich maksimum, jak w zwięzły sposób zrobić to bez przesunięcia? Pamiętaj, że (x+128)/256to nie zadziała. Czy znasz jakieś miłe wypowiedzi, które będą?

— supercat

7

Oczywiście, jeśli piszesz swój kod dla następnego faceta, który go przeczyta, wybierz przejrzystość „x / 2”.

Jeśli jednak Twoim celem jest prędkość, wypróbuj ją w obie strony i zmierz czas. Kilka miesięcy temu pracowałem nad procedurą splotu bitmapy, która polegała na przejściu przez tablicę liczb całkowitych i podzieleniu każdego elementu przez 2. Zrobiłem różne rzeczy, aby go zoptymalizować, w tym starą sztuczkę polegającą na zamianie „x >> 1” na „x / 2 ”.

Kiedy tak naprawdę zmierzyłem oba sposoby, z zaskoczeniem odkryłem, że x / 2 było szybsze niż x >> 1

To było przy użyciu Microsoft VS2008 C ++ z włączonymi domyślnymi optymalizacjami.

— Chris Bennet
źródło

4

Pod względem wydajności. Operacje przesunięcia procesora są znacznie szybsze niż dzielenie kodów operacyjnych. Zatem dzielenie przez dwa lub mnożenie przez 2 itd. Wszystkie korzystają z operacji zmiany.

Co do wyglądu. Kiedy jako inżynierowie byliśmy tak przywiązani do kosmetyków, że nawet piękne damy nie używają! :)

— Farjad
źródło

3

X / Y jest poprawny ... i operator przesuwania „>>” .. jeśli chcemy, aby dwie liczby były liczbą całkowitą, możemy użyć (/) operatora dywidendy. operator shift służy do przesuwania bitów.

x = x / 2; x / = 2; możemy użyć w ten sposób ..

— czekoladowy chłopak
źródło

0

Podczas gdy x >> 1 jest szybszy niż x / 2, prawidłowe użycie >> w przypadku wartości ujemnych jest nieco bardziej skomplikowane. Wymaga czegoś podobnego do następującego:

// Extension Method
public static class Global {
    public static int ShiftDivBy2(this int x) {
        return (x < 0 ? x + 1 : x) >> 1;
    }
}

— Darin
źródło