Która opcja jest lepsza do dzielenia liczby całkowitej przez 2?

Czy ten pierwszy wygląda jak dzielenie? Nie. Jeśli chcesz podzielić, użyj x / 2. Kompilator może go zoptymalizować, aby użyć bit-shift, jeśli to możliwe (nazywa się to redukcją siły), co czyni go bezużyteczną mikro-optymalizacją, jeśli robisz to samodzielnie.

Do kupy: jest tak wiele powodów, aby faworyzować używanie x = x / 2; Oto kilka:

• Wyraża to wyraźniej twoje intencje (zakładając, że nie masz do czynienia z bitowymi przekręcanymi bitami rejestru lub czymś takim)

• Kompilator i tak zredukuje to do operacji shift

• Nawet jeśli kompilator go nie zmniejszył i wybrał wolniejszą operację niż zmiana, prawdopodobieństwo, że w końcu wpłynie to na wydajność programu w wymierny sposób, jest samo w sobie znikający mały (a jeśli ma to wymierny wpływ, to masz rzeczywisty powód, aby użyć zmiany)

• Jeśli dzielenie ma być częścią większego wyrażenia, bardziej prawdopodobne jest, że uzyskasz prawo pierwszeństwa, jeśli użyjesz operatora dzielenia:

  x = x / 2 + 5;
  x = x >> 1 + 5;  // not the same as above
  

• Arytmetyka podpisana może skomplikować sprawy nawet bardziej niż wspomniany powyżej problem pierwszeństwa

• Dla przypomnienia-kompilator i tak zrobi to za Ciebie. W rzeczywistości nawróci się dzielenie przez stałą na szereg przesunięć, dodawania i mnożenia dla różnego rodzaju liczb, a nie tylko potęg dwóch. Zobacz to pytanie dla linków do jeszcze więcej informacji na ten temat.

Krótko mówiąc, nic nie kupujesz, kodując przesunięcie, kiedy naprawdę chcesz mnożyć lub dzielić, może poza zwiększoną możliwością wprowadzenia błędu. Minęło całe życie, ponieważ Kompilatory nie były wystarczająco inteligentne, aby zoptymalizować tego rodzaju rzeczy do zmiany, gdy jest to właściwe.

Która z nich jest najlepszą opcją i dlaczego dzielenie liczby całkowitej przez 2?

Zależy co masz na myśli przez Najlepsze .

Jeśli chcesz podzielić liczbę przez 2, wybierz drugą.

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

Powinieneś napisać swój kod, aby wyrazić jego intencję. Jeśli wydajność jest Twoim problemem, nie martw się, optymalizator wykonuje dobrą pracę w tego rodzaju mikro-optymalizacjach.

Wystarczy użyć divide (/), zakładając, że jest jaśniejszy. Kompilator odpowiednio zoptymalizuje.

Zgadzam się z innymi odpowiedziami, które powinieneś faworyzować x / 2, ponieważ jego intencja jest jaśniejsza, a kompilator powinien ją zoptymalizować dla Ciebie.

Innym powodem preferowania x / 2 nad x >> 1 jest to, że zachowanie >> jest zależne od implementacji, Jeśli x jest podpisane int i jest ujemne.

Z sekcji 6.5.7, punkt 5 normy ISO C99:

Wynikiem E1 >> E2 jest E1 przesunięte w prawo E2 pozycje bitowe. If E1 has Typ niepodpisany lub Jeśli E1 mA typ signed i wartość nonnegatywną, wartość wyniku jest integralną częścią ilorazu E1 / 2^E2. Jeśli E1 mA typ podpisany i wartość ujemną, wartość wynikowa jest zdefiniowana w implementacji.

x / 2 jest jaśniejszy i x >> 1 nie jest dużo szybszy(według mikro-benchmarku, około 30% szybszy dla Java JVM). Jak zauważyli inni, dla liczb ujemnych zaokrąglenie jest nieco inne, więc musisz wziąć to pod uwagę, gdy chcesz przetwarzać liczby ujemne. Niektóre Kompilatory mogą automatycznie konwertować x / 2 na x >> 1, jeśli wiedzą, że liczba nie może być ujemna (nawet myślałem, że nie mogę tego zweryfikować).

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

(jest to pytanie C / c++, inne języki programowania mają więcej operatorów. W przypadku Javy istnieje również unsigned right shift, x >>> 1, który jest znowu inny. Pozwala na prawidłowe obliczenie średniej (średniej) wartości dwóch wartości, tak że (a + b) >>> 1 zwróci wartość średnią nawet dla bardzo dużych wartości a i b. Jest to wymagane na przykład do wyszukiwania binarnego, jeśli indeksy tablicy mogą być bardzo duże. Był błąd w wielu wersjach wyszukiwania binarnego , ponieważ używali (a + b) / 2 do obliczania średniej. To nie działa poprawnie. Poprawnym rozwiązaniem jest użycie (a + b) >>> 1.)

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 i myślę również, że optymalizacja tej operacji w tej formie, nie oznacza dużej różnicy dla procesora.

Spójrz na wyjście kompilatora, aby pomóc ci podjąć decyzję. Przeprowadziłem ten test na x86-64 z
gcc (GCC) 4.2.1 20070719 [FreeBSD]

Zobacz takżekompilator wyjścia online w godbolt .

Widzisz, że kompilator używa instrukcji sarl (arytmetyczna przesunięcie w prawo) w obu przypadkach, więc rozpoznaje podobieństwo między dwoma wyrażeniami. Jeśli używasz dzielenia, kompilator musi również dostosować liczby ujemne. Aby to zrobić przesuwa znak bit w dół do najniższy bit rzędu i dodaje to do wyniku. Rozwiązuje to problem "off-by-one" podczas przesuwania liczb ujemnych, w porównaniu do tego, co zrobiłby podział.
Ponieważ przypadek divide wykonuje 2 przesunięcia, podczas gdy jawny przypadek przesunięcia wykonuje tylko jedną, możemy teraz wyjaśnić niektóre różnice wydajności mierzone innymi odpowiedziami tutaj.

Kod C z wyjściem montażowym:

Dla divide, twoje wejście będzie

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

I to kompiluje się do

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

Podobnie dla shift

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

Z wyjściem:

    sarl    %edi
    movl    %edi, %eax
    ret

Tylko dodana notka -

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

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

Mówię na potrzeby konkursów programistycznych. Na ogół mają bardzo duże wejścia, gdzie podział przez 2 odbywa się wiele razy i wiadomo, że wejście jest dodatnie lub ujemne.

X > > 1 będzie lepszy niż x / 2. Sprawdziłem. ideone.com poprzez prowadzenie programu, w którym odbyło się ponad 10^10 operacji podziału przez 2. x / 2 trwało prawie 5,5 s, podczas gdy x>>1 trwało prawie 2,6 s dla tego samego programu.

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

1. Bitshift powinien być szybszy, ponieważ żadne specjalne obliczenia nie są tak naprawdę potrzebne do przesunięcia bitów, jednak jak wskazano, są potencjalne problemy z liczbami ujemnymi. Jeśli masz pewność, że liczby dodatnie, a szukają prędkości to polecam bitshift.

2. Operator podziału jest bardzo łatwy do odczytania przez ludzi. Więc jeśli szukasz czytelności kodu, możesz przydałoby się to. Uwaga że dziedzina optymalizacji kompilatora przeszła długą drogę, więc ułatwianie kodu czytać i rozumieć to dobra praktyka.

3. w zależności od podstawowego sprzętu, operacje mogą mieć różne prędkości. Prawo Amdal polega na tym, aby szybka sprawa. Więc możesz mieć sprzęt, który może wykonywać różne operacje szybciej niż inne. Na przykład mnożenie przez 0,5 może być szybsze niż dzielenie przez 2. (Możesz potrzebować aby wziąć udział w mnożeniu, jeśli chcesz wymusić dzielenie liczb całkowitych).

Jeśli zależy ci na czystej wydajności, polecam stworzenie testów, które mogłyby wykonywać operacje miliony razy. Spróbuj wykonać kilka razy (wielkość próbki), aby określić, który z nich jest statystycznie najlepszy z twojego systemu operacyjnego/sprzętu/kompilatora / kodu.

Jeśli chodzi o procesor, operacje bit-shift są szybsze niż operacje podziału. Jednak kompilator to wie i odpowiednio zoptymalizuje do tego stopnia, że może, więc możesz kodować w sposób, który ma największy sens i spać spokojnie wiedząc, że Twój kod jest działa sprawnie. Ale pamiętaj, że unsigned int może (w niektórych przypadkach) być zoptymalizowana lepiej niż int z wcześniej wskazanych powodów. Jeśli nie potrzebujesz signed arithmatic, nie dołączaj bitu znaku.

X = X / 2; jest odpowiednim kodem do użycia.. ale operacja zależy od własnego programu, jak dane wyjściowe, które chcesz wyprodukować.

Wyjaśnij swoje intencje...na przykład, jeśli chcesz podzielić, użyj x / 2 i pozwól kompilatorowi zoptymalizować go do przesunięcia operatora (lub czegokolwiek innego).

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

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

• jeśli pracujesz nad 8-bitowym mikrokontrolerem lub czymś innym bez wsparcia sprzętowego dla mnożenia, przesunięcie bitów jest oczekiwane i powszechne, a podczas gdy kompilator prawie na pewno zmieni x /= 2 w x >>= 1, obecność symbolu podziału podniesie więcej brwi w tym środowisku niż użycie przesunięcia do wywołania podziału.
• Jeśli pracujesz w środowisku o krytycznym znaczeniu dla wydajności lub sekcja kodu, lub Twój kod może być skompilowany z wyłączoną optymalizacją kompilatora, x >>= 1 z komentarzem wyjaśniającym jego rozumowanie jest prawdopodobnie najlepszy tylko dla jasności celu.
• Jeśli nie spełniasz jednego z powyższych warunków, popraw czytelność kodu po prostu używając x /= 2. Lepiej zapisać następnego programistę, który spojrzy na Twój kod przez 10 sekund na podwójną zmianę, niż niepotrzebnie udowodnić, że wiedziałeś, że zmiana była bardziej efektywna bez kompilatora optymalizacja.

Wszystkie te zakładają niepodpisane liczby całkowite. Prosta zmiana prawdopodobnie nie jest tym, czego chcesz za podpisane. DanielH zwraca również uwagę na używanie x *= 0.5 w niektórych językach, takich jak ActionScript.

Mod 2, test dla = 1. nie znam składni w c. ale to może być najszybsze.

Ogólnie prawe przesunięcie dzieli:

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

Jest to czasami używane do przyspieszenia programów kosztem przejrzystości. Nie powinieneś tego robić . Kompilator jest wystarczająco inteligentny, aby wykonać przyspieszenie automatycznie. Oznacza to, że wprowadzenie zmiany nic nie zyskuje kosztem jasności .

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

Oczywiście, jeśli piszesz swój kod dla następnego gościa, który go czyta, przejdź do jasności "x / 2".

Jeśli jednak twoim celem jest szybkość, wypróbuj ją w obie strony i czas na wyniki. kilka miesięcy temu pracowałem nad procedurą splatania bitmap, która polegała na przechodzeniu przez tablicę liczb całkowitych i dzieleniu każdego elementu przez 2. Zrobiłem wiele rzeczy, aby go zoptymalizować, w tym starą sztuczkę polegającą na zastąpieniu "x> > 1" przez "x/2".

Kiedy faktycznie zmierzyłem obie strony odkryłem ku mojemu zdziwieniu, że x/2 był szybszy niż x>>1

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

Pod względem wydajności. Operacje przesunięcia procesora są znacznie szybsze niż operacje dzielenia. Więc dzielenie przez dwa lub mnożenie przez 2 itd. wszyscy korzystają z operacji zmiany.

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

X / Y jest poprawne...i "> > " operator zmiany biegów..jeśli chcemy, aby dwa dzielił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..

Podczas gdy x > > 1 jest szybszy niż X / 2, właściwe 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;
    }
}