Ik'heb in mijn vrije tijd C proberen te leren, en andere talen (C#, Java, enz.) hebben hetzelfde concept (en vaak dezelfde operatoren) ...
Wat ik me afvraag is, op een kernniveau, wat bit-shifting (<<
, >>
, >>>
) doet, welke problemen het kan helpen oplossen, en welke gotchas op de loer liggen in de bocht? Met andere woorden, een absolute beginnersgids voor bit shifting in al zijn goedheid.
De bit shifting operatoren doen precies wat hun naam impliceert. Ze verschuiven bits. Hier's een korte (of niet zo korte) inleiding tot de verschillende verschuivingsoperatoren.
>>
is de rekenkundige (of signed) rechter shift operator.>>>
is de logische (of niet-teken-) rechter verschuivingsoperator.<<
is de linker shift operator, en voldoet aan de noden van zowel logische als rekenkundige shifts.Al deze operatoren kunnen worden toegepast op gehele getallen (int
, long
, eventueel short
en byte
of char
). In sommige talen wordt bij toepassing van de verschuivingsoperatoren op een datatype kleiner dan int
de operand automatisch verkleind naar een int
.
Merk op dat <<<
geen operator is, omdat het overbodig zou zijn.
Merk ook op dat C en C++ geen onderscheid maken tussen de right shift operatoren. Zij bieden alleen de >>
operator, en het rechts-verschuiving gedrag is implementatie gedefinieerd voor gesigneerde types. De rest van het antwoord gebruikt de C# / Java operatoren.
(In alle mainstream C en C++ implementaties inclusief gcc en clang/LLVM, >>
op signed types is rekenkundig. Sommige code neemt dit aan, maar het is'niet iets wat de standaard garandeert. Het is echter niet ongedefinieerd; de standaard vereist dat implementaties het op de een of andere manier definiëren. Echter, links verschuiven van negatieve getallen is ongedefinieerd gedrag (signed integer overflow). Dus tenzij u een rekenkundige verschuiving naar rechts nodig hebt, is het meestal een goed idee om uw bit-shifting te doen met niet-ondertekende types).
Gehele getallen worden, in het geheugen, opgeslagen als een reeks bits. Bijvoorbeeld, het getal 6 opgeslagen als een 32-bit int
zou zijn:
00000000 00000000 00000000 00000110
Als je dit bitpatroon één positie naar links schuift (6 << 1
), krijg je het getal 12:
00000000 00000000 00000000 00001100
Zoals je ziet, zijn de cijfers één positie naar links verschoven, en is het laatste cijfer rechts opgevuld met een nul. Je zou ook kunnen opmerken dat naar links schuiven gelijk staat aan vermenigvuldigen met machten van 2. Dus 6 << 1
is gelijk aan 6 * 2
, en 6 << 3
is gelijk aan 6 * 8
. Een goede optimaliserende compiler zal waar mogelijk vermenigvuldigingen vervangen door verschuivingen.
Let op dat dit geen circulaire verschuivingen zijn. Deze waarde wordt één positie naar links verschoven (3.758.096.384 << 1
):
11100000 00000000 00000000 00000000
resulteert in 3.221.225.472:
11000000 00000000 00000000 00000000
Het cijfer dat van het einde verschoven wordt, gaat verloren. Het wordt niet rondgedraaid.
Een logische verschuiving naar rechts is het omgekeerde van de verschuiving naar links. In plaats van bits naar links te verschuiven, verschuiven ze gewoon naar rechts. Bijvoorbeeld, het verschuiven van het getal 12:
00000000 00000000 00000000 00001100
naar rechts met één positie (12 >>> 1
) krijg je onze oorspronkelijke 6 terug:
00000000 00000000 00000000 00000110
We zien dus dat naar rechts schuiven gelijk staat aan delen door machten van 2.
Een verschuiving kan echter geen "verloren" bits terugwinnen. Bijvoorbeeld, als we dit patroon verschuiven:
00111000 00000000 00000000 00000110
4 posities naar links schuiven (939.524.102 << 4
), krijgen we 2.147.483.744:
10000000 00000000 00000000 01100000
en dan terugschuivend ((939.524.102 << 4) >>> 4
) krijgen we 134.217.734:
00001000 00000000 00000000 00000110
We kunnen onze oorspronkelijke waarde niet meer terugkrijgen als we bits verloren hebben.
De rekenkundige verschuiving naar rechts is precies hetzelfde als de logische verschuiving naar rechts, behalve dat in plaats van het opvullen met nul, het opvullen met het meest significante bit gebeurt. Dit komt omdat het meest significante bit het teken bit is, of het bit dat onderscheid maakt tussen positieve en negatieve getallen. Door op te vullen met het meest significante bit, is de rekenkundige verschuiving naar rechts tekenbehoudend.
Bijvoorbeeld, als we dit bitpatroon interpreteren als een negatief getal:
10000000 00000000 00000000 01100000
hebben we het getal -2.147.483.552. Als we dit 4 posities naar rechts verschuiven met de rekenkundige verschuiving (-2,147,483,552 >> 4) dan krijgen we:
11111000 00000000 00000000 00000110
of het getal -134.217.722.
We zien dus dat we het teken van onze negatieve getallen hebben behouden door de rekenkundige verschuiving naar rechts te gebruiken, in plaats van de logische verschuiving naar rechts. En nogmaals, we zien dat we delen door machten van 2.
Laten we zeggen dat we een enkele byte hebben:
0110110
Als we een enkele linkse bitshift toepassen krijgen we:
1101100
De meest linkse nul werd uit de byte geschoven, en een nieuwe nul werd toegevoegd aan het rechter einde van de byte.
De bits rollen niet door; ze worden weggegooid. Dat betekent dat als je 1101100 naar links verschuift en het dan naar rechts verschuift, je niet'hetzelfde resultaat terugkrijgt.
Naar links schuiven met N is gelijk aan vermenigvuldigen met 2N.
Naar rechts schuiven door N is (als je enen'complement gebruikt) het equivalent van delen door 2N en afronden op nul.
Bitshifting kan worden gebruikt voor krankzinnig snelle vermenigvuldigingen en delingen, mits je werkt met een macht van 2. Bijna alle grafische routines op laag niveau gebruiken bitshifting.
Vroeger, bijvoorbeeld, gebruikten we mode 13h (320x200 256 kleuren) voor spelletjes. In Mode 13h werd het videogeheugen sequentieel per pixel ingedeeld. Dat betekende dat om de locatie van een pixel te berekenen, je de volgende wiskunde zou gebruiken:
memoryOffset = (row * 320) + column
In die tijd was snelheid van groot belang, dus gebruikten we bitshifts om deze operatie uit te voeren.
Echter, 320 is geen macht van twee, dus om dit te omzeilen moeten we uitzoeken wat een macht van twee is die bij elkaar opgeteld 320 maakt:
(row * 320) = (row * 256) + (row * 64)
Nu kunnen we dat omzetten in linkse verschuivingen:
(row * 320) = (row << 8) + (row << 6)
Voor een eindresultaat van:
memoryOffset = ((row << 8) + (row << 6)) + column
Nu krijgen we dezelfde offset als voorheen, behalve dat we in plaats van een dure vermenigvuldigingsoperatie, de twee bitshifts gebruiken...in x86 zou het er ongeveer zo uitzien (let op, het'is al een eeuwigheid geleden dat ik'assembly heb gedaan (editor's note: een paar fouten verbeterd en een 32-bit voorbeeld toegevoegd)):
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
Totaal: 28 cycli op welke oude CPU deze timings ook had.
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 cyclussen op dezelfde oude CPU.
Ja, we zouden zo hard werken om 16 CPU cyclussen af te schaven.
In 32 of 64-bit modus worden beide versies een stuk korter en sneller. Moderne out-of-order executie CPU's zoals Intel Skylake (zie http://agner.org/optimize/) hebben zeer snelle hardware multiply (lage latency en hoge doorvoer), dus de winst is veel kleiner. AMD Bulldozer-familie is een beetje trager, vooral voor 64-bit multiply. Op Intel CPU's, en AMD Ryzen, zijn twee verschuivingen iets lagere latency maar meer instructies dan een vermenigvuldiging (wat kan leiden tot lagere doorvoer):
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.
Compilers doen dit voor je: Zie hoe gcc, clang, en MSVC allemaal shift+lea gebruiken bij het optimaliseren van return 320*row + col;
.
Het meest interessante om hier op te merken is dat x86 een shift-and-add instructie (LEA
) heeft die kleine linker shifts kan doen en tegelijkertijd kan toevoegen, met de performance als en add
instructie. ARM is nog krachtiger: één operand van een instructie kan gratis naar links of rechts worden verschoven. Dus schuiven met een compileertijd-constante waarvan bekend is dat het een macht-van-2 is, kan zelfs efficiënter zijn dan een vermenigvuldiging.
OK, terug in de moderne tijd... iets nuttigers nu zou zijn om bitshifting te gebruiken om twee 8-bits waarden op te slaan in een 16-bits geheel getal. Bijvoorbeeld, in C#:
// Byte1: 11110000
// Byte2: 00001111
Int16 value = ((byte)(Byte1 >> 8) | Byte2));
// value = 000011111110000;
In C++ zouden compilers dit voor je moeten doen als je een struct
gebruikt met twee 8-bit members, maar in de praktijk doen ze dat niet altijd's.
Een probleem is dat het volgende afhankelijk is van de implementatie (volgens de ANSI standaard):
char x = -1;
x >> 1;
x kan nu 127 zijn (01111111) of nog steeds -1 (11111111).
In de praktijk is het meestal het laatste.