W wolnym czasie próbowałem nauczyć się języka C, a inne języki (C #, Java itp.) Mają tę samą koncepcję (i często te same operatory) ...
Zastanawiam się co jest na poziomie rdzenia, co czyni nieco przesunięcia ( <<
, >>
, >>>
) zrobić, jakie problemy może pomóc rozwiązać i jakie pułapek czai się za zakrętem? Innymi słowy, absolutny przewodnik dla początkujących, aby nieco zmienić się w całej swojej dobroci.
operators
bit-manipulation
bit-shift
binary-operators
John Rudy
źródło
źródło
Odpowiedzi:
Operatorzy przesuwania bitów robią dokładnie to, co implikuje ich nazwa. Przesuwają bity. Oto krótkie (lub niezbyt krótkie) wprowadzenie do różnych operatorów zmiany biegów.
Operatorzy
>>
jest arytmetycznym (lub podpisanym) operatorem prawej zmiany.>>>
jest logicznym (lub niepodpisanym) operatorem prawej zmiany.<<
jest operatorem zmiany biegów w lewo i spełnia potrzeby zarówno zmian logicznych, jak i arytmetycznych.Wszystkie te podmioty mogą być zastosowane do wartości całkowitych (
int
,long
ewentualnieshort
ibyte
ichar
). W niektórych językach zastosowanie operatorów shift do dowolnego typu danych mniejszego niżint
automatycznie zmienia rozmiar operandu naint
.Pamiętaj, że
<<<
nie jest operatorem, ponieważ byłby nadmiarowy.Zauważ też, że C i C ++ nie rozróżniają właściwych operatorów shift . Dostarczają tylko
>>
operatora, a właściwość przesunięcia w prawo jest implementacją zdefiniowaną dla podpisanych typów. Reszta odpowiedzi korzysta z operatorów C # / Java.(We wszystkich głównych implementacjach C i C ++, w tym GCC i Clang / LLVM,
>>
na podpisanych typach występuje arytmetyka. Niektóre kody to zakładają, ale nie jest to coś, co gwarantują standardowe. Nie jest to jednak nieokreślone ; standard wymaga implementacji, aby je zdefiniować w ten czy inny sposób. Jednak lewe przesunięcie ujemnych liczb ze znakiem jest zachowaniem niezdefiniowanym (przepełnienie liczb całkowitych ze znakiem). Więc jeśli nie potrzebujesz arytmetycznej zmiany prawej, zwykle dobrym pomysłem jest przesuwanie bitów z niepodpisanymi typami.)Shift w lewo (<<)
Liczby całkowite są przechowywane w pamięci jako seria bitów. Na przykład liczba 6 przechowywana jako wersja 32-bitowa
int
to:Przesunięcie tego wzorca bitowego do lewej pozycji (
6 << 1
) spowodowałoby liczbę 12:Jak widać, cyfry przesunęły się w lewo o jedną pozycję, a ostatnia cyfra po prawej stronie jest wypełniona zerem. Możesz również zauważyć, że przesunięcie w lewo jest równoznaczne z pomnożeniem przez potęgi 2. Zatem
6 << 1
jest równoważne6 * 2
i6 << 3
równoważne6 * 8
. Dobry kompilator optymalizujący zastąpi mnożenia przesunięciami, jeśli to możliwe.Przesunięcie nieokrągłe
Należy pamiętać, że nie są to przesunięcia kołowe. Przesunięcie tej wartości w lewo o jedną pozycję (
3,758,096,384 << 1
):wyniki w 3.221.225.472:
Cyfra, która zostanie przesunięta „z końca”, zostanie utracona. Nie zawija się.
Logiczne przesunięcie w prawo (>>>)
Logiczne przesunięcie w prawo jest odwrotnością do przesunięcia w lewo. Zamiast przesuwać bity w lewo, po prostu przesuwają się w prawo. Na przykład przesunięcie liczby 12:
w prawo o jedną pozycję (
12 >>> 1
) odzyska naszą oryginalną 6:Widzimy więc, że przesunięcie w prawo jest równoważne podziałowi przez potęgi 2.
Zagubione kawałki zniknęły
Jednak zmiana nie może odzyskać „utraconych” bitów. Na przykład, jeśli zmienimy ten wzór:
na lewo 4 pozycje (
939,524,102 << 4
) otrzymujemy 2 147 483 744:a następnie cofając się (
(939,524,102 << 4) >>> 4
) otrzymujemy 134 217 734:Nie możemy odzyskać naszej pierwotnej wartości po utracie bitów.
Arytmetyczne przesunięcie w prawo (>>)
Arytmetyczne przesunięcie w prawo jest dokładnie tak samo jak logiczne przesunięcie w prawo, z tym wyjątkiem, że zamiast dopełniania zerem, uzupełnia się najbardziej znaczącym bitem. Wynika to z faktu, że najbardziej znaczącym bitem jest bit znaku lub bit, który odróżnia liczby dodatnie i ujemne. Wypełniając najbardziej znaczącym bitem, arytmetyczne przesunięcie w prawo zachowuje znaki.
Na przykład, jeśli interpretujemy ten wzór bitowy jako liczbę ujemną:
mamy liczbę -2 147 483 552. Przesunięcie tego w prawo o 4 pozycje za pomocą przesunięcia arytmetycznego (-2,147,483,552 >> 4) dałoby nam:
lub numer -134,217,722.
Widzimy więc, że zachowaliśmy znak naszych liczb ujemnych, używając arytmetycznego przesunięcia w prawo, a nie logicznego przesunięcia w prawo. I po raz kolejny widzimy, że dokonujemy podziału według potęg 2.
źródło
A good optimizing compiler will substitute shifts for multiplications when possible.
Co? Przesunięcia bitów są o rząd wielkości szybsze, jeśli chodzi o niskopoziomowe operacje procesora, dobry kompilator optymalizujący zrobiłby dokładnie odwrotnie, to znaczy zamieniając zwykłe mnożenia przez potęgę dwóch na przesunięcia bitowe.Powiedzmy, że mamy jeden bajt:
Zastosowanie pojedynczego przesunięcia bitów w lewo daje nam:
Lewe zero zostało przesunięte poza bajt, a nowe zero zostało dodane do prawego końca bajtu.
Bity nie przechodzą; są odrzucane. Oznacza to, że jeśli opuścisz Shift 1101100, a następnie prawy Shift, nie otrzymasz z powrotem tego samego wyniku.
Przesunięcie w lewo o N odpowiada przemnożeniu przez 2 N. .
Przesunięcie w prawo o N to (jeśli używasz ich uzupełnienia ) jest równoważne podzieleniu przez 2 N. i zaokrągleniu do zera.
Bitshifting może być użyty do niesamowicie szybkiego mnożenia i dzielenia, pod warunkiem, że pracujesz z potęgą 2. Prawie wszystkie procedury graficzne niskiego poziomu używają bitshiftingu.
Na przykład w dawnych czasach używaliśmy trybu 13h (320 x 200 256 kolorów) do gier. W trybie 13h pamięć wideo była układana sekwencyjnie na piksel. Oznaczało to obliczenie lokalizacji piksela, użyłbyś następującej matematyki:
W tamtych czasach prędkość była kluczowa, więc do wykonania tej operacji użyjemy przesunięć bitów.
Jednak 320 nie jest potęgą dwóch, więc aby to obejść, musimy dowiedzieć się, jaka potęga dwóch, dodanych razem, daje 320:
Teraz możemy przekonwertować to na przesunięcia w lewo:
Aby uzyskać końcowy wynik:
Teraz otrzymujemy takie samo przesunięcie jak poprzednio, z tą różnicą, że zamiast kosztownej operacji mnożenia używamy dwóch przesunięć bitowych ... w x86 byłoby to mniej więcej tak (uwaga, to trwało wiecznie, odkąd zrobiłem montaż (uwaga redaktora: poprawiona kilka błędów i dodany 32-bitowy przykład)):
Łącznie: 28 cykli na dowolnym starożytnym procesorze miał te czasy.
Vrs
12 cykli na tym samym starożytnym procesorze.
Tak, ciężko pracowalibyśmy, aby zmniejszyć 16 cykli procesora.
W trybie 32- lub 64-bitowym obie wersje stają się znacznie krótsze i szybsze. Nowoczesne procesory poza kolejnością, takie jak Intel Skylake (patrz http://agner.org/optimize/ ), mają bardzo szybki mnożnik sprzętowy (małe opóźnienia i wysoka przepustowość), więc zysk jest znacznie mniejszy. Rodzina buldożerów AMD jest nieco wolniejsza, szczególnie w przypadku mnożenia 64-bitowego. W procesorach Intel i AMD Ryzen dwie zmiany mają nieco mniejsze opóźnienie, ale więcej instrukcji niż wielokrotność (co może prowadzić do niższej przepustowości):
vs.
Kompilatory zrobią to za Ciebie: Zobacz, jak GCC, Clang i Microsoft Visual C ++ używają shift + lea podczas optymalizacji
return 320*row + col;
.Najciekawszą rzeczą do odnotowania tutaj jest to, że x86 ma instrukcję shift-and-add (
LEA
), która może wykonywać małe lewe przesunięcia i dodawać w tym samym czasie, z wydajnością jakoadd
instrukcją. ARM jest jeszcze potężniejszy: jeden operand dowolnej instrukcji można przesunąć w lewo lub w prawo za darmo. Skalowanie według stałej czasowej kompilacji, o której wiadomo, że jest potęgą 2, może być nawet bardziej wydajne niż mnożenie.OK, wracając do czasów współczesnych ... bardziej użyteczne byłoby użycie przesunięcia bitów do przechowywania dwóch 8-bitowych wartości w 16-bitowej liczbie całkowitej. Na przykład w języku C #:
W C ++ kompilatory powinny zrobić to za Ciebie, jeśli korzystasz
struct
z dwóch 8-bitowych elementów, ale w praktyce nie zawsze.źródło
c=4*d
, dostaniesz zmianę. Jeśli piszeszk = (n<0)
, można to zrobić również przy zmianie:k = (n>>31)&1
aby uniknąć gałęzi. Podsumowując, ta poprawa sprytności kompilatorów oznacza, że nie jest już konieczne korzystanie z tych sztuczek w kodzie C, a także pogarszają czytelność i przenośność. Nadal bardzo dobrze je znać, jeśli piszesz np. Kod wektorowy SSE; lub w każdej sytuacji, w której potrzebujesz go szybko i istnieje pewna sztuczka, której nie używa kompilator (np. kod GPU).if(x >= 1 && x <= 9)
to, żeif( (unsigned)(x-1) <=(unsigned)(9-1))
zmiana dwóch testów warunkowych na jeden może być dużą zaletą prędkości; szczególnie gdy pozwala na predykcyjne wykonanie zamiast gałęzi. Używałem tego przez lata (tam, gdzie było to uzasadnione), dopóki nie zauważyłem około 10 lat temu, że kompilatory rozpoczęły tę transformację w optymalizatorze, a potem przestałem. Nadal dobrze wiedzieć, ponieważ istnieją podobne sytuacje, w których kompilator nie może dokonać transformacji za Ciebie. Lub jeśli pracujesz na kompilatorze.Operacje bitowe, w tym przesunięcie bitów, mają fundamentalne znaczenie dla sprzętu niskiego poziomu lub programowania wbudowanego. Jeśli przeczytasz specyfikację urządzenia lub nawet niektóre binarne formaty plików, zobaczysz bajty, słowa i dwory, podzielone na niepasujące do siebie bajtowe pola bitowe, które zawierają różne interesujące wartości. Dostęp do tych pól bitowych do odczytu / zapisu jest najczęstszym zastosowaniem.
Prostym prawdziwym przykładem w programowaniu graficznym jest to, że 16-bitowy piksel jest reprezentowany w następujący sposób:
Aby uzyskać zieloną wartość, wykonaj następujące czynności:
Wyjaśnienie
Aby uzyskać wartość TYLKO zieleni, która zaczyna się od przesunięcia 5 i kończy na 10 (tj. O długości 6 bitów), musisz użyć maski (bitowej), która zastosowana w stosunku do całego 16-bitowego piksela da tylko te części, którymi jesteśmy zainteresowani.
Odpowiednią maską jest 0x7E0, która w systemie binarnym to 0000011111100000 (czyli 2016 w systemie dziesiętnym).
Aby zastosować maskę, użyj operatora AND (&).
Po zastosowaniu maski otrzymasz 16-bitową liczbę, która jest tak naprawdę tylko 11-bitową liczbą, ponieważ jej MSB znajduje się w 11-tym bicie. Kolor zielony ma w rzeczywistości tylko 6 bitów, więc musimy go przeskalować za pomocą przesunięcia w prawo (11 - 6 = 5), stąd użycie 5 jako przesunięcia (
#define GREEN_OFFSET 5
).Często stosuje się również przesunięcia bitów do szybkiego mnożenia i dzielenia przez potęgi 2:
źródło
Maskowanie i przesuwanie bitów
Przesunięcie bitów jest często stosowane w programowaniu grafiki niskiego poziomu. Na przykład podana wartość koloru piksela jest zakodowana w 32-bitowym słowie.
Dla lepszego zrozumienia ta sama wartość binarna oznaczona sekcjami reprezentującymi część koloru.
Powiedzmy na przykład, że chcemy uzyskać zieloną wartość koloru tego piksela. Możemy łatwo uzyskać tę wartość poprzez maskowanie i przesuwanie .
Nasza maska:
&
Operator logiczny zapewnia zachowanie tylko tych wartości, w których maska wynosi 1. Ostatnią rzeczą, którą musimy teraz zrobić, jest uzyskanie poprawnej wartości całkowitej poprzez przesunięcie wszystkich bitów w prawo o 16 miejsc (logiczne przesunięcie w prawo) .Et voilà, mamy liczbę całkowitą reprezentującą ilość zieleni w kolorze piksela:
To jest często używany do kodowania lub dekodowania formatów graficznych jak
jpg
,png
itpźródło
Jedna z nich polega na tym, że następujące elementy zależą od implementacji (zgodnie ze standardem ANSI):
x może teraz wynosić 127 (01111111) lub nadal -1 (11111111).
W praktyce jest to zwykle ta ostatnia.
źródło
Piszę tylko porady i wskazówki. Może być przydatny w testach i egzaminach.
n = n*2
:n = n<<1
n = n/2
:n = n>>1
!(n & (n-1))
n
:n |= (1 << x)
x&1 == 0
(parzysty)x ^ (1<<n)
źródło
Zauważ, że w implementacji Java liczba bitów do przesunięcia jest modyfikowana przez rozmiar źródła.
Na przykład:
równa się 2. Można oczekiwać, że przesunięcie bitów w prawo 65 razy wyzeruje wszystko, ale w rzeczywistości jest to odpowiednik:
Dotyczy to <<, >> i >>>. Nie wypróbowałem tego w innych językach.
źródło
gcc 5.4.0
daje ostrzeżenie, ale daje2
za 5 >> 65; także.Kilka przydatnych operacji / operacji bitowych w Pythonie.
Zaimplementowałem odpowiedź Ravi Prakash w Pythonie.
źródło
Pamiętaj, że tylko 32-bitowa wersja PHP jest dostępna na platformie Windows.
Jeśli na przykład przesuniesz << lub >> o więcej niż o 31 bitów, wyniki będą nieoczekiwane. Zwykle zwracany jest oryginalny numer zamiast zer i może to być naprawdę trudny błąd.
Oczywiście, jeśli używasz 64-bitowej wersji PHP (Unix), powinieneś unikać przesunięcia o więcej niż 63 bity. Jednak na przykład MySQL używa 64-bitowego BIGINT, więc nie powinno być żadnych problemów ze zgodnością.
AKTUALIZACJA: Z PHP 7 Windows kompilacje PHP mogą wreszcie korzystać z pełnych 64-bitowych liczb całkowitych: Rozmiar liczby całkowitej zależy od platformy, chociaż maksymalna wartość wynosząca około dwóch miliardów to zwykle wartość (to 32 bitów ze znakiem). Platformy 64-bitowe zwykle mają maksymalną wartość około 9E18, z wyjątkiem Windowsa przed PHP 7, gdzie zawsze był 32-bitowy.
źródło