Ik heb in mijn vrije tijd geprobeerd C te leren, en andere talen (C#, Java, enz.) hebben hetzelfde concept (en vaak dezelfde operators) …

Wat ik me afvraag is, op kernniveau, wat bit-shifting doet (<<, >>, >>>) doen, welke problemen kan het helpen oplossen en welke valkuilen liggen op de loer? Met andere woorden, een absolute beginnersgids voor bitverschuiving in al zijn goedheid.

Antwoord 1, autoriteit 100%

De bitshift-operators doen precies wat hun naam aangeeft. Ze verschuiven stukjes. Hier is een korte (of niet zo korte) introductie van de verschillende ploegoperators.

De operators

• >>is de rekenkundige (of ondertekende) rechter shift-operator.
• >>>is de logische (of niet-ondertekende) operator voor de shift naar rechts.
• <<is de operator voor de linkerploeg en voldoet aan de behoeften van zowel logische als rekenkundige ploegen.

Al deze operatoren kunnen worden toegepast op gehele waarden (int, long, mogelijk shorten byteof char). In sommige talen wordt de grootte van de operand automatisch gewijzigd in een intdoor de shift-operatoren toe te passen op elk datatype dat kleiner is dan int.

Merk op dat <<<geen operator is, omdat het overbodig zou zijn.

Houd er ook rekening mee dat C en C++ geen onderscheid maken tussen de juiste ploegendiensten. Ze bieden alleen de operator >>en het naar rechts verschuivende gedrag is door de implementatie gedefinieerd voor ondertekende typen. De rest van het antwoord gebruikt de C# / Java-operators.

(In alle gangbare C- en C++-implementaties, inclusief GCC en Clang/LLVM, is >>op ondertekende typen rekenkundig. Sommige code gaat hiervan uit, maar het is niet iets dat de standaard garandeert. Het is echter niet ongedefinieerd; de standaard vereist implementaties om het op de een of andere manier te definiëren. Linkerverschuivingen van getallen met negatief teken isongedefinieerd gedrag (getekende integer overflow). Dus tenzij je een rekenkundige verschuiving naar rechts nodig hebt, is het meestal een goed idee om je bitverschuiving uit te voeren met niet-ondertekende typen.)

Linker shift (<<)

Gehele getallen worden in het geheugen opgeslagen als een reeks bits. Bijvoorbeeld, het nummer 6 opgeslagen als een 32-bits intzou zijn:

00000000 00000000 00000000 00000110

Als u dit bitpatroon één positie naar links verschuift (6 << 1) krijgt u het getal 12:

00000000 00000000 00000000 00001100

Zoals je kunt zien, zijn de cijfers één positie naar links verschoven en is het laatste cijfer aan de rechterkant gevuld met een nul. Je zou ook kunnen opmerken dat naar links schuiven gelijk staat aan vermenigvuldigen met machten van 2. Dus 6 << 1is gelijk aan 6 * 2en 6 << 3is gelijk aan 6 * 8. Een goede optimaliserende compiler zal vermenigvuldigingen waar mogelijk vervangen door ploegendiensten.

Niet-circulair schakelen

Houd er rekening mee dat dit geencirculaire diensten zijn. Deze waarde één positie naar links verschuiven (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” wordt verschoven, gaat verloren. Het wikkelt niet rond.

Logische verschuiving naar rechts (>>>)

Een logische verschuiving naar rechts is het omgekeerde van de verschuiving naar links. In plaats van bits naar links te verplaatsen, verplaatsen ze zich gewoon naar rechts. Bijvoorbeeld, het nummer 12 verschuiven:

00000000 00000000 00000000 00001100

één positie naar rechts (12 >>> 1) krijgen onze oorspronkelijke 6 terug:

00000000 00000000 00000000 00000110

We zien dus dat naar rechts verschuiven gelijk is aan delen door machten van 2.

Verloren bits zijn verdwenen

Een ploeg kan echter geen “verloren” bits terugvorderen. Als we dit patroon bijvoorbeeld verschuiven:

00111000 00000000 00000000 00000110

naar links 4 posities (939,524,102 << 4), krijgen we 2.147.483.744:

10000000 00000000 00000000 01100000

en dan terugschakelen ((939,524,102 << 4) >>> 4) krijgen we 134.217.734:

00001000 00000000 00000000 00000110

We kunnen onze oorspronkelijke waarde niet terugkrijgen als we eenmaal bits zijn kwijtgeraakt.

Rekenkundige verschuiving naar rechts (>>)

De rekenkundige verschuiving naar rechts is precies hetzelfde als de logische verschuiving naar rechts, behalve dat in plaats van opvulling met nul, het opvult met het meest significante bit. Dit komt omdat het meest significante bit het tekenbit is, of het bit dat positieve en negatieve getallen onderscheidt. Door op te vullen met het meest significante bit, blijft de rekenkundige verschuiving naar rechts tekenbehoudend.

Als we dit bitpatroon bijvoorbeeld interpreteren als een negatief getal:

10000000 00000000 00000000 01100000

we hebben het nummer -2.147.483.552. Als we dit 4 posities naar rechts verschuiven met de rekenkundige verschuiving (-2.147.483.552 >> 4) zou ons het volgende opleveren:

11111000 00000000 00000000 00000110

of het nummer -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 uitvoeren.

Antwoord 2, autoriteit 12%

Stel dat we één byte hebben:

0110110

Als we een enkele bitshift naar links toepassen, krijgen we:

1101100

De meest linkse nul is uit de byte verschoven en een nieuwe nul is toegevoegd aan het rechteruiteinde van de byte.

De bits rollen niet om; ze worden weggegooid. Dat betekent dat als je naar links 1101100 schakelt en dan naar rechts, je niet hetzelfde resultaat terugkrijgt.

Naar links schuiven is gelijk aan vermenigvuldigen met 2^N.

Naar rechts verschuiven is (als je ones’ complementgebruikt) equivalent van delen door 2^Nen afronden naar nul.

Bitshifting kan worden gebruikt voor waanzinnig snelle vermenigvuldiging en deling, op voorwaarde dat u met een kracht van 2 werkt. Bijna alle grafische routines op laag niveau gebruiken bitshifting.

Vroeger gebruikten we bijvoorbeeld modus 13h (320×200 256 kleuren) voor games. In Mode 13h werd het videogeheugen sequentieel per pixel ingedeeld. Dat betekende om de locatie voor een pixel te berekenen, je zou de volgende wiskunde gebruiken:

memoryOffset = (row * 320) + column

In die tijd was snelheid van cruciaal belang, dus we zouden bitshifts gebruiken om deze bewerking uit te voeren.

320 is echter 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 ploegen naar links:

(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 zoiets zijn als dit (let op, het is een eeuwigheid geleden dat ik assemblage heb gedaan opmerking: een paar fouten gecorrigeerd en een 32-bits 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 tijden 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 cycli op dezelfde oude CPU.

Ja, we zouden zo hard werken om 16 CPU-cycli te verminderen.

In 32- of 64-bits modus worden beide versies een stuk korter en sneller. Moderne out-of-order uitvoerings-CPU’s zoals Intel Skylake (zie http://agner.org/optimize/) hebben een zeer snelle hardwarevermenigvuldiging (lage latentie en hoge doorvoer), dus de winst is veel kleiner. AMD Bulldozer-familie is een beetje langzamer, vooral voor 64-bits vermenigvuldiging. Op Intel CPU’s en AMD Ryzen hebben twee ploegen een iets lagere latentie maar meer instructies dan een vermenigvuldiging (wat kan leiden tot een 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 u: kijk hoe GCC, Clang en Microsoft Visual C++ gebruiken allemaal shift+lea bij het optimaliseren van return 320*row + col;.

Het meest interessante om hier op te merken is dat x86 heeft een shift-and-add instructie (LEA)die kleine shifts naar links kan doen en tegelijkertijd kan toevoegen, met de uitvoering als een addinstructie. ARM is nog krachtiger: één operand van elke instructie kan gratis naar links of rechts worden verschoven. Dus schalen met een compile-time-constante waarvan bekend is dat het een power-of-2 is, kan zelfs efficiënter zijn dan een vermenigvuldiging.

Ok, in de moderne tijd… zou het nu nuttiger 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 structmet twee 8-bits leden gebruikt, maar in de praktijk doen ze dat niet altijd.

Antwoord 3, autoriteit 6%

Bitgewijze bewerkingen, inclusief bitverschuiving, zijn van fundamenteel belang voor hardware op laag niveau of ingebedde programmering. Als u een specificatie voor een apparaat of zelfs enkele binaire bestandsindelingen leest, ziet u bytes, woorden en dwords, opgedeeld in niet-byte uitgelijnde bitvelden, die verschillende interessante waarden bevatten. Toegang tot deze bitvelden voor lezen/schrijven is het meest gebruikelijke gebruik.

Een eenvoudig echt voorbeeld in grafische programmering is dat een 16-bits pixel als volgt wordt weergegeven:

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

Om de groene waarde te krijgen, doet u het volgende:

#define GREEN_MASK  0x7E0
 #define GREEN_OFFSET  5
 // Read green
 uint16_t green = (pixel & GREEN_MASK) >> GREEN_OFFSET;

Uitleg

Om de waarde van ALLEEN groen te verkrijgen, die begint bij offset 5 en eindigt bij 10 (dwz 6 bits lang), moet u een (bit) masker gebruiken, dat wanneer toegepast op de gehele 16-bits pixel , levert alleen de bits op waarin we geïnteresseerd zijn.

#define GREEN_MASK  0x7E0

Het juiste masker is 0x7E0, wat in binair getal 0000011111100000 is (wat 2016 in decimaal is).

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

Om een masker toe te passen, gebruik je de AND-operator (&).

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

Na het toepassen van het masker, krijg je een 16-bits getal dat eigenlijk gewoon een 11-bits getal is, aangezien de MSB zich in de 11e bit bevindt. Groen is eigenlijk maar 6 bits lang, dus we moeten het verkleinen met een verschuiving naar rechts (11 – 6 = 5), vandaar het gebruik van 5 als offset (#define GREEN_OFFSET 5).

Ook gebruikelijk is het gebruik van bitverschuivingen voor snelle vermenigvuldiging en deling door machten van 2:

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

Antwoord 4, autoriteit 3%

Bit maskeren & Schakelen

Bitverschuiving wordt vaak gebruikt bij grafische programmering op laag niveau. Bijvoorbeeld een bepaalde pixelkleurwaarde gecodeerd in een 32-bits woord.

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

Voor een beter begrip, dezelfde binaire waarde gelabeld met welke secties welk kleurgedeelte vertegenwoordigen.

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

Laten we zeggen bijvoorbeeld dat we de groene waarde van de kleur van deze pixel willen krijgen. We kunnen deze waarde gemakkelijk krijgen door Maskering en Shifting .

Ons masker:

                 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

De logische &operator zorgt ervoor dat alleen de waarden waar het masker 1 wordt bewaard. Het laatste dat we nu moeten doen, is om de juiste integer-waarde te krijgen door al die bits naar rechts te verschuiven door 16 plaatsen (logische rechterschakeling) .

green_value = masked_color >>> 16

et voilà, we hebben het geheel getal dat de hoeveelheid groen in de kleur van de pixel vertegenwoordigt:

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

Dit wordt vaak gebruikt voor het coderen of decoderen van beeldformaten zoals jpg, png, enz.

5, Autoriteit 2%

Eén GOTCHA is dat het volgende is afhankelijk van de implementatie (volgens de ANSI-standaard):

char x = -1;
x >> 1;

x kan nu 127 (01111111) of nog -1 (11111111) zijn.

In de praktijk is het meestal de laatste.

6

Ik schrijf alleen tips en trucs. Het kan nuttig zijn in tests en examens.

1. n = n*2: n = n<<1
2. n = n/2: n = n>>1
3. Controleren of n Voeding van 2 (1,2,4,8, …): Controleer !(n & (n-1))
4. Krijg x ^{th bit van n: n |= (1 << x)}
5. Controleren of x zelfs of oneven is: x&1 == 0(zelfs)
6. Schakel de N ^{TH BIT van X: x ^ (1<<n)}

Antwoord 7

Enkele handige bitbewerkingen/manipulaties in Python.

Ik heb Het antwoord van Ravi Prakashin Python.

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

Antwoord 8

De bitsgewijze shift-operators verplaatsen de bitwaarden van een binair object. De linker operand specificeert de waarde die moet worden verschoven. De rechter operand specificeert het aantal posities dat de bits in de waarde moeten worden verschoven. Het resultaat is geen waarde. Beide operanden hebben dezelfde prioriteit en zijn associatief van links naar rechts.

Operator     Usage
 <<           Indicates the bits are to be shifted to the left.
 >>           Indicates the bits are to be shifted to the right.

Elke operand moet een integraal- of opsommingstype hebben. De compiler voert integrale promoties uit op de operanden en vervolgens wordt de juiste operand geconverteerd naar het type int. Het resultaat heeft hetzelfde type als de linker operand (na de rekenkundige conversies).

De rechter operand mag geen negatieve waarde hebben of een waarde die groter is dan of gelijk is aan de breedte in bits van de uitdrukking die wordt verschoven. Het resultaat van bitsgewijze verschuivingen op dergelijke waarden is onvoorspelbaar.

Als de rechter operand de waarde 0 heeft, is het resultaat de waarde van de linker operand (na de gebruikelijke rekenkundige conversies).

De << operator vult vrijgekomen bits met nullen. Als left_op bijvoorbeeld de waarde 4019 heeft, is het bitpatroon (in 16-bits formaat) van left_op:

0000111110110011

De uitdrukking left_op << 3 opbrengsten:

0111110110011000

De uitdrukking left_op >> 3 opbrengsten:

0000000111110110

Antwoord 9

Houd er rekening mee dat er alleen een 32-bits versie van PHP beschikbaar is op het Windows-platform.

Als u bijvoorbeeld << of >> meer dan met 31 bits, zijn de resultaten onverwacht. Gewoonlijk wordt het originele getal in plaats van nullen geretourneerd, en het kan een erg lastige bug zijn.

Als je een 64-bits versie van PHP (Unix) gebruikt, moet je natuurlijk voorkomen dat je meer dan 63 bits verschuift. MySQL gebruikt echter bijvoorbeeld de 64-bits BIGINT, dus er zouden geen compatibiliteitsproblemen moeten zijn.

UPDATE: vanaf PHP 7 Windows kunnen PHP-builds eindelijk volledige 64-bits gehele getallen gebruiken:
De grootte van een geheel getal is platformafhankelijk, hoewel een maximale waarde van ongeveer twee miljard de gebruikelijke waarde is (dat is 32 bits ondertekend). 64-bits platforms hebben meestal een maximale waarde van ongeveer 9E18, behalve op Windows voorafgaand aan PHP 7, waar het altijd 32 bit was.