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

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.

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)

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.

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.

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.

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

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.

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

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.

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

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.

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.

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.

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

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

2. 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ą.

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

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.

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

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.

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.

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

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

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.

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ą! :)

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

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;
    }
}