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.

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, longewentualnie shorti bytei char). W niektórych językach zastosowanie operatorów shift do dowolnego typu danych mniejszego niż intautomatycznie zmienia rozmiar operandu na int.

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 intto:

00000000 00000000 00000000 00000110

Przesunięcie tego wzorca bitowego do lewej pozycji ( 6 << 1) spowodowałoby liczbę 12:

00000000 00000000 00000000 00001100

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 << 1jest równoważne 6 * 2i 6 << 3równoważne 6 * 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):

11100000 00000000 00000000 00000000

wyniki w 3.221.225.472:

11000000 00000000 00000000 00000000

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:

00000000 00000000 00000000 00001100

w prawo o jedną pozycję ( 12 >>> 1) odzyska naszą oryginalną 6:

00000000 00000000 00000000 00000110

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:

00111000 00000000 00000000 00000110

na lewo 4 pozycje ( 939,524,102 << 4) otrzymujemy 2 147 483 744:

10000000 00000000 00000000 01100000

a następnie cofając się ( (939,524,102 << 4) >>> 4) otrzymujemy 134 217 734:

00001000 00000000 00000000 00000110

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

10000000 00000000 00000000 01100000

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:

11111000 00000000 00000000 00000110

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.

Powiedzmy, że mamy jeden bajt:

0110110

Zastosowanie pojedynczego przesunięcia bitów w lewo daje nam:

1101100

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:

memoryOffset = (row * 320) + column

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:

(row * 320) = (row * 256) + (row * 64)

Teraz możemy przekonwertować to na przesunięcia w lewo:

(row * 320) = (row << 8) + (row << 6)

Aby uzyskać końcowy wynik:

memoryOffset = ((row << 8) + (row << 6)) + column

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

mov ax, 320; 2 cycles
mul word [row]; 22 CPU Cycles
mov di,ax; 2 cycles
add di, [column]; 2 cycles
; di = [row]*320 + [column]

; 16-bit addressing mode limitations:
; [di] is a valid addressing mode, but [ax] isn't, otherwise we could skip the last mov

Łącznie: 28 cykli na dowolnym starożytnym procesorze miał te czasy.

Vrs

mov ax, [row]; 2 cycles
mov di, ax; 2
shl ax, 6;  2
shl di, 8;  2
add di, ax; 2    (320 = 256+64)
add di, [column]; 2
; di = [row]*(256+64) + [column]

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

imul edi, [row], 320    ; 3 cycle latency from [row] being ready
add  edi, [column]      ; 1 cycle latency (from [column] and edi being ready).
; edi = [row]*(256+64) + [column],  in 4 cycles from [row] being ready.

vs.

mov edi, [row]
shl edi, 6               ; row*64.   1 cycle latency
lea edi, [edi + edi*4]   ; row*(64 + 64*4).  1 cycle latency
add edi, [column]        ; 1 cycle latency from edi and [column] both being ready
; edi = [row]*(256+64) + [column],  in 3 cycles from [row] being ready.

Kompilatory zrobią to za Ciebie: Zobacz, jak GCC, Clang i Microsoft Visual C ++ używają shift + lea podczas optymalizacjireturn 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ą jako addinstrukcją. 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 #:

// Byte1: 11110000
// Byte2: 00001111

Int16 value = ((byte)(Byte1 >> 8) | Byte2));

// value = 000011111110000;

W C ++ kompilatory powinny zrobić to za Ciebie, jeśli korzystasz structz dwóch 8-bitowych elementów, ale w praktyce nie zawsze.

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:

  bit | 15| 14| 13| 12| 11| 10| 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1  | 0 |
      |       Blue        |         Green         |       Red          |

Aby uzyskać zieloną wartość, wykonaj następujące czynności:

 #define GREEN_MASK  0x7E0
 #define GREEN_OFFSET  5

 // Read green
 uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

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.

#define GREEN_MASK  0x7E0

Odpowiednią maską jest 0x7E0, która w systemie binarnym to 0000011111100000 (czyli 2016 w systemie dziesiętnym).

uint16_t green = (pixel & GREEN_MASK) ...;

Aby zastosować maskę, użyj operatora AND (&).

uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

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:

 i <<= x;  // i *= 2^x;
 i >>= y;  // i /= 2^y;

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.

 Pixel-Color Value in Hex:    B9B9B900
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

Dla lepszego zrozumienia ta sama wartość binarna oznaczona sekcjami reprezentującymi część koloru.

                                 Red     Green     Blue       Alpha
 Pixel-Color Value in Binary: 10111001  10111001  10111001  00000000

Powiedzmy na przykład, że chcemy uzyskać zieloną wartość koloru tego piksela. Możemy łatwo uzyskać tę wartość poprzez maskowanie i przesuwanie .

Nasza maska:

                  Red      Green      Blue      Alpha
 color :        10111001  10111001  10111001  00000000
 green_mask  :  00000000  11111111  00000000  00000000

 masked_color = color & green_mask

 masked_color:  00000000  10111001  00000000  00000000

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

 green_value = masked_color >>> 16

Et voilà, mamy liczbę całkowitą reprezentującą ilość zieleni w kolorze piksela:

 Pixels-Green Value in Hex:     000000B9
 Pixels-Green Value in Binary:  00000000 00000000 00000000 10111001
 Pixels-Green Value in Decimal: 185

To jest często używany do kodowania lub dekodowania formatów graficznych jak jpg, pngitp

Jedna z nich polega na tym, że następujące elementy zależą od implementacji (zgodnie ze standardem ANSI):

char x = -1;
x >> 1;

x może teraz wynosić 127 (01111111) lub nadal -1 (11111111).

W praktyce jest to zwykle ta ostatnia.

Piszę tylko porady i wskazówki. Może być przydatny w testach i egzaminach.

1. n = n*2: n = n<<1
2. n = n/2: n = n>>1
3. Sprawdzanie, czy n jest potęgą 2 (1,2,4,8, ...): sprawdź !(n & (n-1))
4. Pierwsze X ^th bitowej n:n |= (1 << x)
5. Sprawdzanie, czy x jest parzyste czy nieparzyste: x&1 == 0 (parzysty)
6. Przełącz n- ^ty bit x:x ^ (1<<n)

Zauważ, że w implementacji Java liczba bitów do przesunięcia jest modyfikowana przez rozmiar źródła.

Na przykład:

(long) 4 >> 65

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:

(long) 4 >> (65 % 64)

Dotyczy to <<, >> i >>>. Nie wypróbowałem tego w innych językach.

Kilka przydatnych operacji / operacji bitowych w Pythonie.

Zaimplementowałem odpowiedź Ravi Prakash w Pythonie.

# Basic bit operations
# Integer to binary
print(bin(10))

# Binary to integer
print(int('1010', 2))

# Multiplying x with 2 .... x**2 == x << 1
print(200 << 1)

# Dividing x with 2 .... x/2 == x >> 1
print(200 >> 1)

# Modulo x with 2 .... x % 2 == x & 1
if 20 & 1 == 0:
    print("20 is a even number")

# Check if n is power of 2: check !(n & (n-1))
print(not(33 & (33-1)))

# Getting xth bit of n: (n >> x) & 1
print((10 >> 2) & 1) # Bin of 10 == 1010 and second bit is 0

# Toggle nth bit of x : x^(1 << n)
# take bin(10) == 1010 and toggling second bit in bin(10) we get 1110 === bin(14)
print(10^(1 << 2))

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.