Powiedzmy, że mamy pojedynczy bajt:

0110110

Zastosowanie jednego lewego bitshift daje nam:

1101100

Lewe zero zostało przesunięte poza bajt, a nowe zero zostało dodane do prawego końca bajtu.

Bity nie przewracają się; są odrzucane. Oznacza to, że jeśli przesuniesz w lewo 1101100, a następnie przesuniesz w prawo, nie otrzymasz tego samego wyniku z powrotem.

Przesunięcie w lewo przez N jest równoważne mnożeniu przez 2 ^N .

Przesunięcie w prawo przez N jest (jeśli używasz dopełniacza jedynek ) jest odpowiednikiem dzielenia przez 2 ^N i zaokrąglania do zera.

Bitshifting może być używany do szalenie szybkiego mnożenia i dzielenia, pod warunkiem, że pracujesz z mocą 2. Prawie wszystkie niskopoziomowe procedury graficzne używają bitshiftingu.

Na przykład w dawnych czasach używaliśmy trybu 13h (320x200 256 kolorów) do gier. W trybie 13h pamięć wideo była rozkładana kolejno na piksel. To oznaczało obliczenie miejsce dla piksela, można użyć następującej matematyki:

memoryOffset = (row * 320) + column

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

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

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

Dla wyniku końcowego:

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

Teraz otrzymujemy to samo przesunięcie co poprzednio, z wyjątkiem zamiast kosztownej operacji mnożenia, używamy dwóch bitshifts...in x86 byłoby to coś takiego (Uwaga, minęło wieki odkąd zrobiłem assembly( Uwaga redaktora: poprawiłem kilka błędów i dodałem przykład 32-bitowy)): {]}

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

Razem: 28 cykli na dowolnym starożytnym procesorze.

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.

W trybie 32 lub 64-bitowym, obie wersje są znacznie krótsze i szybsze. Nowoczesne procesory out-of-order execution, takie jak Intel Skylake (zobacz http://agner.org/optimize / ) mają bardzo szybkie mnożenie sprzętu (niskie opóźnienia i wysoka przepustowość), więc zysk jest znacznie mniejszy. AMD Bulldozer-rodzina jest nieco wolniejsza, szczególnie dla 64-bitowych multiply. Na procesorach Intel i AMD Ryzen dwie zmiany to nieco mniejsze opóźnienie, ale więcej instrukcji niż mnożenie (co może prowadzić do niższego przepustowość): {]}

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 MSVC używają shift + lea podczas optymalizacji return 320*row + col;.

Najciekawsze jest to, że x86 ma instrukcję shift-and-add (LEA) może to robić małe zmiany w lewo i dodawać jednocześnie, z instrukcją performance as and add. Ramię jest jeszcze potężniejsze: jeden operand dowolnej instrukcji może być przesunięty w lewo lub w prawo za darmo. Więc skalowanie przez stałą czasu kompilacji, która jest znana jako moc 2, może być jeszcze bardziej wydajne niż mnożenie.

// Byte1: 11110000
// Byte2: 00001111

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

// value = 000011111110000;

W C++ Kompilatory powinny zrobić to za Ciebie, jeśli używasz struct z dwoma składnikami 8-bitowymi, ale w praktyce nie zawsze.

Operacje bitowe, w tym przesunięcie bitowe, są fundamentalne dla niskopoziomowego sprzętu lub programowania wbudowanego. Jeśli czytasz specyfikację urządzenia lub nawet niektórych formatów plików binarnych, zobaczysz bajty, słowa i dwords, podzielone na nie-bajtowe pola bitowe, które zawierają różne interesujące wartości. Dostęp do tych pól bitowych do odczytu/zapisu jest najczęściej używany.

Prostym prawdziwym przykładem w programowaniu Grafiki jest to, że 16-bitowy piksel jest reprezentowany jako follows:

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

Aby uzyskać wartość green należy zrobić to:

 #define GREEN_MASK  0x7E0
 #define GREEN_OFFSET  5

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

Wyjaśnienie

Aby uzyskać wartość green ONLY, która zaczyna się od przesunięcia 5 i kończy się na 10 (tj. długości 6 bitów), należy użyć maski (bitowej), która po nałożeniu na cały 16-bitowy piksel, uzyska tylko te bity, które nas interesują.

#define GREEN_MASK  0x7E0

Odpowiednią maską jest 0x7e0, która w układzie binarnym wynosi 000001111100000 (co w układzie dziesiętnym oznacza 2016).

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

Aby zastosować Maska, używasz operatora AND ( & ).

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

Po nałożeniu maski, skończysz z 16-bitową liczbą, która jest tak naprawdę tylko 11-bitową liczbą, ponieważ jej MSB jest w 11-tym bitie. Zielony ma długość tylko 6 bitów, więc musimy przeskalować go w dół, używając prawego przesunięcia (11-6 = 5), stąd użycie 5 jako przesunięcia (#define GREEN_OFFSET 5).

Popularne jest również używanie przesunięć bitowych do szybkiego mnożenia i dzielenia przez potęgi 2:

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

Bit Masking & Shifting

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

Dla lepszego zrozumienia, ta sama wartość binarna oznaczona tym, które sekcje reprezentują jaką część koloru.

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

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

Nasz 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, że zachowywane są tylko wartości, w których Maska wynosi 1. Ostatnią rzeczą, jaką musimy teraz zrobić, jest uzyskanie poprawnej wartości całkowitej przez przesunięcie wszystkich tych 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 pikseli:

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

Jest to często używane do kodowania lub dekodowania formatów obrazu, takich jak jpg,png,....

Jedną z nich jest to, że w zależności od implementacji (zgodnie ze standardem ANSI):

char x = -1;
x >> 1;

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

W praktyce zwykle jest to drugie.

Zauważ, że w implementacji Javy 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 się spodziewać, że przesunięcie bitów w prawo 65 razy zerowałoby wszystko, ale w rzeczywistości jest to odpowiednik:

(long) 4 >> (65 % 64)

To prawda dla > i>>>. Nie próbowałem go w innych językach.

Piszę tylko porady i triki, mogą się przydać w testach/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,...): check !(n & (n-1))
4. Getting x^th bit z n: n |= (1 << x)
5. sprawdzanie czy x jest parzyste czy nieparzyste: x&1 == 0 (parzyste)
6. Przełącz n^th bit x: x ^ (1<<n)

Należy pamiętać, że tylko 32-bitowa wersja PHP jest dostępna na platformie Windows.

Wtedy, jeśli na przykład przesuniesz > więcej niż o 31 bitów, wyniki są nieprzewidywalne. Zazwyczaj zwracana jest oryginalna liczba zamiast zer i może to być bardzo trudny błąd.

Oczywiście jeśli używasz 64-bitowej wersji PHP (unix), powinieneś unikać przesuwania o więcej niż 63 bity. Jednak na przykład MySQL używa 64-bitowego BIGINTA, więc nie powinno być żadnej kompatybilności problemy.

Aktualizacja: od PHP7 Windows, PHP buildy są w końcu w stanie używać pełnych 64-bitowych liczb całkowitych: wielkość liczby całkowitej jest zależna od platformy, chociaż maksymalna wartość około dwóch miliardów jest zwykłą wartością (to jest 32 bity podpisane). Platformy 64-bitowe zwykle mają maksymalną wartość około 9E18, z wyjątkiem Windows przed PHP 7, gdzie zawsze był 32 bit.