Operátory bitového posunu robia presne to, čo naznačuje ich názov. Posúvajú bity. Tu je stručný (alebo nie až tak stručný) úvod do rôznych operátorov posunu.

Operátory

• >> je aritmetický (alebo znamienkový) operátor pravého posunu.
• >>> je logický (alebo bez znamienka) operátor pravého posunu.
• << je operátor ľavého posunu a spĺňa potreby logického aj aritmetického posunu.

Všetky tieto operátory možno použiť na celočíselné hodnoty (int, long, prípadne short a byte alebo char). V niektorých jazykoch sa pri použití operátorov posunu na akýkoľvek dátový typ menší ako int automaticky zmení veľkosť operandu na int.

Všimnite si, že <<< nie je operátor, pretože by bol zbytočný.

Taktiež si všimnite, že C a C++ nerozlišujú medzi operátormi pravého posunu. Poskytujú len operátor >> a správanie pri posúvaní doprava je implementačne definované pre znamienkové typy. Zvyšok odpovede používa operátory jazyka C#/Java.

(Vo všetkých hlavných implementáciách C a C++ vrátane gcc a clang/LLVM je >> na znamienkových typoch aritmetický. Niektoré kódy to predpokladajú, ale nie je to niečo, čo štandard garantuje. Nie je to však nedefinované; štandard vyžaduje, aby to implementácie definovali tak či onak. Avšak ľavý posun záporných čísiel so znamienkom je nedefinované správanie (pretečenie celého čísla so znamienkom). Takže ak nepotrebujete aritmetický posun doprava, je zvyčajne dobré robiť bitový posun s nepodpísanými typmi).

Levý posun (<<)

Celé čísla sú v pamäti uložené ako rad bitov. Napríklad číslo 6 uložené ako 32-bitový int by bolo:

00000000 00000000 00000000 00000110

Posunutím tohto bitového vzoru doľava o jednu pozíciu (6 << 1) by vzniklo číslo 12:

00000000 00000000 00000000 00001100

Ako vidíte, číslice sa posunuli doľava o jednu pozíciu a posledná číslica vpravo je vyplnená nulou. Môžete si tiež všimnúť, že posun doľava je ekvivalentný násobeniu mocninami 2. Takže 6 << 1 je ekvivalentné 6 * 2 a 6 << 3 je ekvivalentné 6 * 8. Dobrý optimalizujúci kompilátor nahradí násobenie posunmi, ak je to možné.

Nekruhové posúvanie

Upozorňujeme, že toto nie sú kruhové posuny. Posunutie tejto hodnoty doľava o jednu pozíciu (3 758 096 384 << 1):

11100000 00000000 00000000 00000000

Výsledkom je 3 221 225 472:

11000000 00000000 00000000 00000000

Číslica, ktorá sa posunie "z konca", sa stratí. Neobklopí sa.

Logický posun doprava (>>>)

Logický posun doprava je opakom posunu doľava. Namiesto posunu bitov doľava sa jednoducho posunú doprava. Napríklad posun čísla 12:

00000000 00000000 00000000 00001100

doprava o jednu pozíciu (12 >>> 1) dostaneme späť pôvodných 6:

00000000 00000000 00000000 00000110

Vidíme teda, že posun doprava je ekvivalentný deleniu mocninami 2.

Stratené bity sú preč

Posunutím však nemožno získať späť "stratené" bity. Ak napríklad posunieme tento vzor:

00111000 00000000 00000000 00000110

doľava o 4 pozície (939 524 102 <<4), dostaneme 2 147 483 744:

10000000 00000000 00000000 01100000

a potom posunutím späť ((939,524,102 << 4) >>> 4) dostaneme 134,217,734:

00001000 00000000 00000000 00000110

Keď sme stratili bity, nemôžeme získať späť pôvodnú hodnotu.

Aritmetický posun doprava (>>)

Aritmetický pravý posun je presne taký istý ako logický pravý posun, len namiesto vyplnenia nulou sa vyplní najvýznamnejším bitom. Je to preto, že najvýznamnejší bit je sign bit, alebo bit, ktorý rozlišuje kladné a záporné čísla. Tým, že je aritmetický posun doprava vyplnený najvýznamnejším bitom, zachováva znamienko.

Ak napríklad interpretujeme tento bitový vzor ako záporné číslo:

10000000 00000000 00000000 01100000

dostaneme číslo -2 147 483 552. Posunutím tohto čísla o 4 pozície doprava pomocou aritmetického posunu (-2,147,483,552 >> 4) by sme dostali:

11111000 00000000 00000000 00000110

alebo číslo -134,217,722.

Vidíme teda, že sme zachovali znamienko našich záporných čísel použitím aritmetického posunu doprava, a nie logického posunu doprava. A opäť vidíme, že vykonávame delenie mocninami 2.

Povedzme, že máme jeden bajt:

0110110

Použitím jedného ľavého bitového posunu dostaneme:

1101100

Najľavejšia nula bola posunutá z bajtu a nová nula bola pridaná na pravý koniec bajtu.

Bity sa neprevracajú, ale zahadzujú. To znamená, že ak posuniete 1101100 doľava a potom doprava, nedostanete späť rovnaký výsledok.

Posun doľava o N je ekvivalentný násobeniu 2^N.

Posunutie doprava o N je (ak používate jedničkový doplnok) ekvivalentné deleniu 2^N a zaokrúhleniu na nulu.

Posúvanie bitov sa dá použiť na šialene rýchle násobenie a delenie za predpokladu, že pracujete s mocninou 2. Takmer všetky nízkoúrovňové grafické procedúry používajú posúvanie bitov.

Napríklad v dávnych časoch sme v hrách používali režim 13h (320x200 256 farieb). V režime 13h bola videopamäť rozložená sekvenčne na každý pixel. To znamenalo, že na výpočet umiestnenia pixelu by ste použili nasledujúcu matematiku:

memoryOffset = (row * 320) + column

V tej dobe bola rýchlosť rozhodujúca, takže sme na túto operáciu používali bitové posuny.

Avšak 320 nie je mocnina dvoch, takže aby sme to obišli, musíme zistiť, aká mocnina dvoch je súčet 320:

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

Teraz to môžeme previesť na ľavý posun:

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

Pre konečný výsledok:

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

Teraz dostaneme rovnaký offset ako predtým, len namiesto drahej operácie násobenia použijeme dva bitové posuny... v x86 by to vyzeralo takto (pozn. je to už celá večnosť, čo som robil assembler (pozn. redakcie: opravil som pár chýb a pridal 32-bitový príklad)):

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

Celkovo: 28 cyklov na akomkoľvek starodávnom procesore s týmto časovaním.

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 cyklov na tom istom starobylom procesore.

Áno, takto tvrdo by sme pracovali, aby sme ušetrili 16 cyklov CPU.

V 32- alebo 64-bitovom režime sa obe verzie výrazne skracujú a zrýchľujú. Moderné procesory s out-of-order vykonávaním, ako napríklad Intel Skylake (pozri http://agner.org/optimize/), majú veľmi rýchle hardvérové násobenie (nízka latencia a vysoká priepustnosť), takže zisk je oveľa menší. Rodina AMD Bulldozer je o niečo pomalšia, najmä v prípade 64-bitového násobenia. Pri procesoroch Intel a AMD Ryzen sú dve posunutia mierne nižšie latencie, ale viac inštrukcií ako násobenie (čo môže viesť k nižšej priepustnosti):

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.

Kompilátory to urobia za vás: Pozri, ako gcc, clang a MSVC používajú shift+lea pri optimalizácii return 320*row + col;.

Najzaujímavejšie je, že x86 má inštrukciu shift-and-add (LEA), ktorá dokáže robiť malé ľavé posuny a sčítanie súčasne, s výkonom ako inštrukcia add. ARM je ešte výkonnejší: jeden operand ľubovoľnej inštrukcie môže byť zadarmo posunutý doľava alebo doprava. Takže škálovanie pomocou konštanty v čase kompilácie, o ktorej je známe, že je mocninou 2, môže byť ešte efektívnejšie ako násobenie.

OK, späť do moderných čias... niečo užitočnejšie by teraz bolo použiť bitový posun na uloženie dvoch 8-bitových hodnôt do 16-bitového celého čísla. Napríklad v jazyku C#:

// Byte1: 11110000
// Byte2: 00001111

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

// value = 000011111110000;

V jazyku C++ by to mali kompilátory urobiť za vás, ak použijete struct s dvoma 8-bitovými členmi, ale v praxi to nie'vždy urobia.

Jedným z úskalí je, že nasledujúci postup závisí od implementácie (podľa normy ANSI):

char x = -1;
x >> 1;

x môže byť teraz 127 (01111111) alebo stále -1 (11111111).

V praxi je to zvyčajne to druhé.