Operacja bitowa

Przesunięcia bitowe są czasami uważane za operacje bitowe, ponieważ traktują wartość jako serię bitów, a nie jako wielkość liczbową. W tych operacjach cyfry są przesuwane, lub przesunięte, w lewo lub w prawo. Rejestry w procesorze komputerowym mają stałą szerokość, więc niektóre bity będą „przesunięte” z rejestru na jednym końcu, podczas gdy ta sama liczba bitów jest „przesunięta” z drugiego końca; różnice między operatorami przesunięć bitowych polegają na tym, jak określają one wartości przesuniętych bitów.

Adresowanie bitoweEdit

Jeżeli szerokość rejestru (często 32 lub nawet 64) jest większa niż liczba bitów (zwykle 8) najmniejszej adresowalnej jednostki (elementu atomowego), zwanej często bajtem, to operacje przesunięcia wywołują schemat adresowania na bitach.Pomijając efekty brzegowe na obu końcach rejestru, operacje przesunięcia arytmetycznego i logicznego zachowują się tak samo, a przesunięcie o 8 pozycji bitowych przenosi schemat bitowy o 1 pozycję bajtową w następujący sposób:

Przesunięcie arytmetyczneEdit

Przesunięcie arytmetyczne w lewo

Prawe przesunięcie arytmetyczne

W przesunięciu arytmetycznym, bity, które są przesunięte z obu końców, są odrzucane. W lewym przesunięciu arytmetycznym, zera są przesuwane w prawo; w prawym przesunięciu arytmetycznym, bit znaku (MSB w uzupełnieniu do dwóch) jest przesuwany w lewo, zachowując znak operandu.

Przykład wykorzystuje 8-bitowy rejestr, interpretowany jako dopełnienie dwójkowe:

 00010111 (decimal +23) LEFT-SHIFT= 00101110 (decimal +46)

 10010111 (decimal −105) RIGHT-SHIFT= 11001011 (decimal −53)

W pierwszym przypadku najbardziej na lewo wysunięta cyfra została przesunięta poza koniec rejestru, a nowe 0 zostało przesunięte na najbardziej na prawo wysuniętą pozycję. W drugim przypadku, prawa cyfra 1 została przesunięta na zewnątrz (być może do flagi przenoszenia), a nowa 1 została skopiowana na lewą pozycję, zachowując znak liczby. Wielokrotne przesunięcia są czasami skracane do pojedynczego przesunięcia o pewną liczbę cyfr. Na przykład:

 00010111 (decimal +23) LEFT-SHIFT-BY-TWO= 01011100 (decimal +92)

Lewe arytmetyczne przesunięcie o n jest równoważne mnożeniu przez 2n (pod warunkiem, że wartość nie przepełnia się), podczas gdy prawe arytmetyczne przesunięcie o n wartości dopełnienia do dwóch jest równoważne dzieleniu przez 2n i zaokrąglaniu w kierunku ujemnej nieskończoności. Jeśli liczba binarna jest traktowana jako dopełnienie jedynki, to ta sama operacja przesunięcia w prawo skutkuje dzieleniem przez 2n i zaokrąglaniem w kierunku zera.

Przesunięcie logiczneEdit

.

Lewe przesunięcie logiczne

Prawe przesunięcie logiczne

W przesunięciu logicznym, zera są przesuwane w celu zastąpienia odrzuconych bitów. Dlatego logiczne i arytmetyczne przesunięcia w lewo są dokładnie takie same.

Jednakże, ponieważ logiczne przesunięcie w prawo wstawia bity o wartości 0 do najbardziej znaczącego bitu, zamiast kopiowania bitu znaku, jest idealne dla liczb binarnych bez znaku, podczas gdy arytmetyczne przesunięcie w prawo jest idealne dla podpisanych liczb binarnych z uzupełnieniem dwóch.

Przesunięcie kołoweEdit

Inną formą przesunięcia jest przesunięcie kołowe, obrót bitowy lub obrót bitowy.

RotateEdit

.

Przesunięcie w lewo lub obrót

Prawe przesunięcie okrężne lub rotate

W tej operacji, czasami nazywana rotate no carry, bity są „obracane” tak, jakby lewy i prawy koniec rejestru były połączone. Wartość, która jest przesunięta w prawo podczas lewego przesunięcia, jest dowolną wartością, która została przesunięta z lewej strony, i odwrotnie dla operacji przesunięcia w prawo. Jest to przydatne, gdy konieczne jest zachowanie wszystkich istniejących bitów i jest często używane w kryptografii cyfrowej.

Rotate through carryEdit

.

Lewy obrót przez przeniesienie

Prawy rotate through carry

Rotate through carry jest wariantem operacji rotate, gdzie bit, który jest przesunięty do środka (na obu końcach) jest starą wartością flagi carry, a bit, który jest przesunięty na zewnątrz (na drugim końcu) staje się nową wartością flagi carry.

Pojedynczy obrót przez przeniesienie może symulować logiczne lub arytmetyczne przesunięcie o jedną pozycję poprzez wcześniejsze ustawienie flagi przeniesienia. Na przykład, jeśli flaga carry zawiera 0, to x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE jest logicznym przesunięciem w prawo, a jeśli flaga carry zawiera kopię bitu znaku, to x RIGHT-ROTATE-THROUGH-CARRY-BY-ONE jest arytmetycznym przesunięciem w prawo. Z tego powodu niektóre mikrokontrolery, takie jak low end PIC, mają po prostu rotate i rotate through carry, i nie zawracają sobie głowy instrukcjami arytmetycznymi lub logicznymi shift.

Rotate through carry jest szczególnie przydatny przy wykonywaniu przesunięć na liczbach większych niż natywny rozmiar słowa procesora, ponieważ jeśli duża liczba jest przechowywana w dwóch rejestrach, bit, który jest przesunięty z jednego końca pierwszego rejestru, musi wejść na drugi koniec drugiego. Z rotate-through-carry, ten bit jest „zapisany” we fladze carry podczas pierwszego przesunięcia, gotowy do przesunięcia podczas drugiego przesunięcia bez żadnych dodatkowych przygotowań.

W językach wysokiego poziomuEdit

W językach z rodziny CEdit

W językach z rodziny C logicznymi operatorami przesunięcia są „<<” dla przesunięcia w lewo i „>>” dla przesunięcia w prawo. Liczba miejsc do przesunięcia jest podawana jako drugi argument operatora. Na przykład,

x = y << 2;

przypisuje x wynik przesunięcia y w lewo o dwa bity, co jest równoważne mnożeniu przez cztery.

Przesunięcia mogą powodować niezdefiniowane zachowanie w implementacji lub niezdefiniowane zachowanie, więc należy zachować ostrożność podczas ich używania. Wynik przesunięcia o liczbę bitów większą lub równą rozmiarowi słowa jest niezdefiniowanym zachowaniem w C i C++. Przesunięcie w prawo wartości ujemnej jest zdefiniowane przez implementację i nie jest zalecane przez dobrą praktykę kodowania; wynik przesunięcia w lewo wartości podpisanej jest niezdefiniowany, jeśli wynik nie może być reprezentowany w typie wynikowym.

W C#, przesunięcie w prawo jest przesunięciem arytmetycznym, gdy pierwszy operand jest typu int lub long. Jeśli pierwszy operand jest typu uint lub ulong, przesunięcie w prawo jest przesunięciem logicznym.

Przesunięcia kołoweEdit

W rodzinie języków C brakuje operatora rotate, ale można go zsyntetyzować z operatorów przesunięcia. Należy zadbać o to, aby oświadczenie było dobrze uformowane, aby uniknąć niezdefiniowanego zachowania i ataków czasowych w oprogramowaniu z wymaganiami bezpieczeństwa. Na przykład, naiwna implementacja, która obraca w lewo 32-bitową wartość bez znaku x o n pozycje jest po prostu:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (32 - n));

Jednakże, przesunięcie o 0 bitów powoduje niezdefiniowane zachowanie w prawym wyrażeniu (x >> (32 - n)) ponieważ 32 - 0 jest 32, i 32 jest poza zakresem włącznie. Druga próba może skutkować:

uint32_t x = ..., n = ...;uint32_t y = n ? (x << n) | (x >> (32 - n)) : x;

gdzie kwota przesunięcia jest testowana, aby upewnić się, że nie wprowadza niezdefiniowanego zachowania. Jednak gałąź dodaje dodatkową ścieżkę kodu i stanowi okazję do analizy czasu i ataku, co często nie jest akceptowalne w oprogramowaniu o wysokiej integralności. Dodatkowo, kod kompiluje się do wielu instrukcji maszynowych, co często jest mniej wydajne niż natywne instrukcje procesora.

Aby uniknąć niezdefiniowanego zachowania i rozgałęzień w GCC i Clang, zaleca się następujące czynności. Wzorzec ten jest rozpoznawany przez wiele kompilatorów, a kompilator wyemituje pojedynczą instrukcję rotate:

uint32_t x = ..., n = ...;uint32_t y = (x << n) | (x >> (-n & 31));

Istnieją również specyficzne dla kompilatora intrinsics implementujące przesunięcia kołowe, takie jak _rotl8, _rotl16, _rotr8, _rotr16 w Microsoft Visual C++. Clang dostarcza kilka intrinsics rotate dla kompatybilności z Microsoft, które cierpią z powodu powyższych problemów. GCC nie oferuje intrinsics rotate. Intel dostarcza również intrinsics x86.

JavaEdit

W Javie wszystkie typy całkowite są podpisane, więc operatory „<<” i „>>” wykonują przesunięcia arytmetyczne. Java dodaje operator „>>>” do wykonywania logicznych przesunięć w prawo, ale ponieważ logiczne i arytmetyczne operacje przesunięcia w lewo są identyczne dla podpisanych liczb całkowitych, nie ma operatora „<<<” w Javie.

Więcej szczegółów na temat operatorów przesunięcia w Javie:

• Operatory << (przesunięcie w lewo), >> (podpisane przesunięcie w prawo) i >>> (niepodpisane przesunięcie w prawo) są nazywane operatorami przesunięcia.
• Typem wyrażenia przesunięcia jest typ promowany lewego operandu. Na przykład, aByte >>> 2 jest równoważne ((int) aByte) >>> 2.
• Jeśli promowanym typem lewego operandu jest int, tylko pięć bitów najniższego rzędu prawego operandu jest używanych jako odległość przesunięcia. To tak, jakby prawy operand został poddany bitowemu operatorowi logicznemu AND & z wartością maski 0x1f (0b11111). Dlatego faktycznie użyta odległość przesunięcia jest zawsze w zakresie od 0 do 31, włącznie.
• Jeśli promowany typ lewego operandu jest długi, to tylko sześć bitów najniższego rzędu prawego operandu jest używane jako odległość przesunięcia. To tak, jakby prawy operand został poddany bitowemu operatorowi logicznemu AND & z wartością maski 0x3f (0b111111). Dlatego faktycznie użyta odległość przesunięcia zawsze mieści się w zakresie od 0 do 63, włącznie.
• Wartość n >>> s to n przesuniętych w prawo s pozycji bitowych z zerowym rozszerzeniem.
• W operacjach bitowych i przesunięciach, typ byte jest niejawnie konwertowany na int. Jeśli wartość bajtu jest ujemna, najwyższy bit jest jeden, a następnie jedynki są używane do wypełnienia dodatkowych bajtów w int. Tak więc byte b1 = -5; int i = b1 | 0x0200; będzie skutkować i == -5.

JavaScriptEdit

JavaScript używa operacji bitowych do oceny każdej z dwóch lub więcej jednostek miejsce na 1 lub 0.

PascalEdit

W Pascalu, jak również we wszystkich jego dialektach (takich jak Object Pascal i Standard Pascal), logicznymi operatorami przesunięcia w lewo i w prawo są odpowiednio „shl” i „shr„. Nawet dla podpisanych liczb całkowitych, shr zachowuje się jak przesunięcie logiczne i nie kopiuje bitu znaku. Liczba miejsc do przesunięcia jest podawana jako drugi argument. Na przykład, poniższe polecenie przypisuje x wynik przesunięcia y w lewo o dwa bity:

x := y shl 2;