Bitdrift

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 16 december 2021; kontroller kräver 10 redigeringar .

En bitvis operation i programmering  är en operation på kedjor av bitar , som regel ingår logiska bitvisa operationer och bitskiften i denna klass . De används i programmeringsspråk och digital teknik , studerade i diskret matematik .

Bitoperationer är grunden för digital signalbehandling : med hjälp av dem erhålls en ny signal från en eller flera signaler vid ingången, som i sin tur kan matas till ingången för en eller flera sådana operationer. Det är bitoperationer i kombination med lagringselement (till exempel triggers ) som realiserar all rikedom av möjligheterna med modern digital teknik.

Bitvisa operationer

Ett antal källor på lågnivåspråk kallar bitvisa logiska operationer helt enkelt logiska [1] [2] , men i terminologin för programmering på högnivåspråk innehåller namnen på bitvisa operationer adjektiv bitvis , bitvis (till exempel: "bitvis logisk OCH ", det är också "bitvis multiplikation"), bitvis .

I vissa programmeringsspråk är namnen på operatorerna som motsvarar logiska och bitvisa logiska operationer liknande. Dessutom kan programmeringsspråket tillåta implicit konvertering av en numerisk typ till en boolesk typ och vice versa. I sådana programmeringsspråk måste man vara försiktig med användningen av logiska och bitvisa operationer, vars blandning kan leda till fel. Till exempel, i C++ är resultatet av uttrycket "2 && 1" ( logiskt AND ) det booleska värdet true , och resultatet av uttrycket "2 & 1" ( bitvis AND ) är heltalsvärdet 0 .

Bitvis negation

Bitvis negation (eller bitvis NOT , komplement ) är en unär operation vars åtgärd är likvärdig med att tillämpa logisk negation på varje bit i den binära representationen av operanden. Med andra ord, vid den position där det fanns 0 i den binära representationen av operanden, blir resultatet 1, och omvänt, där det var 1, kommer det att finnas 0. Till exempel:

INTE 01
tio

Bitvis OCH

Bitvis "AND"  är en binär operation , vars åtgärd är ekvivalent med att applicera ett logiskt "AND" på varje par av bitar som är i samma positioner i de binära representationerna av operanderna. Med andra ord, om båda motsvarande bitar av operanderna är 1, är den resulterande biten 1; om minst en bit av paret är 0, är ​​den resulterande biten 0.

Exempel:

Och 0011
0101
0001

Bitvis ELLER

Bitvis ELLER  är en binär operation som är ekvivalent med att tillämpa ett logiskt ELLER på varje par av bitar som har samma position i de binära representationerna av operanderna. Med andra ord, om båda motsvarande bitar av operanderna är 0, är ​​den binära biten av resultatet 0; om minst en bit av paret är 1, är den binära biten av resultatet 1.

Exempel:

ELLER 0011
0101
0111

Bitvis XOR

Bitvis exklusiv ELLER (modulo 2 addition) är en binär operation, vars åtgärd är ekvivalent med att applicera ett logiskt exklusivt ELLER på varje par av bitar som är i samma positioner i de binära representationerna av operanderna. Med andra ord, om båda motsvarande bitar av operanderna är lika med varandra, är den binära biten av resultatet 0; annars är den binära siffran i resultatet 1.

Exempel:

Exkl. ELLER 0011
0101
0110

Det första ryska namnet på operationen beror på det faktum att resultatet av denna operation skiljer sig från resultatet av "ELLER" endast i ett fall av fyra ingångsfall - båda 1 (fallet med samtidig sanning av argumenten är "exkluderat "). Även i rysk grammatik förmedlas innebörden av detta logiska bindemedel av facket "eller".

Det andra namnet är det som egentligen är addition i ringen av rester modulo två, från vilket några intressanta egenskaper följer. Till exempel, till skillnad från ovanstående "OCH" och "ELLER", är denna operation reversibel: .

I datorgrafik används "addition modulo two" när sprites visas på bilden - dess upprepade tillämpning tar bort spriten från bilden. På grund av involutivitet har samma operation hittat tillämpning i kryptografi som den enklaste implementeringen av ett absolut säkert chiffer ( Vernam-chiffer ). "Modulo two addition" kan också användas för att utbyta två variabler med hjälp av XOR-utbytesalgoritmen .

Denna operation kan också kallas "maskinversion", det vill säga de bitar som matchar 1:an i masken inverteras från det ursprungliga binära talet.

I vanliga programmeringsspråk implementeras endast fyra bitvisa logiska operationer av inbyggda verktyg: AND, OR, NOT och XOR . För att specificera en godtycklig bitvis logisk operation räcker det med de listade, och dessutom, som följer av teorin om booleska funktioner, kan man begränsa sig till en ännu mindre uppsättning grundläggande operationer. Det finns också programmeringsspråk där det finns en inbyggd förmåga att utföra vilken binär logisk operation som helst bit för bit. Till exempel har PL/I en inbyggd BOOL-funktion vars tredje argument är för att specificera en godtycklig logisk operation som ska tillämpas bitvis på de två första argumenten [3] .

Bitskiften

Bitvisa operationer inkluderar även bitskift. Vid växling kopieras bitvärden till intilliggande i växlingsriktningen. Det finns flera typer av skift - logiska , aritmetiska och cykliska , beroende på bearbetningen av de extrema bitarna.

Det sker också en förskjutning till vänster (i riktningen från den minst signifikanta biten till den mest signifikanta) och till höger (i riktningen från den mest signifikanta biten till den minst signifikanta).

Logiskt skift

Under en logisk växling förloras värdet på den sista biten i växlingens riktning (kopieras till bärbiten), och den första biten blir noll.

Aritmetiskt skift

Ett aritmetiskt skift liknar ett logiskt skift, men talet anses vara ett tecken med tecken, representerat i en extra kod. Så med en högerförskjutning behåller den mest signifikanta biten sitt värde. Det vänstra aritmetiska skiftet är identiskt med det logiska.

Aritmetiska vänster- och högerskift används för snabb multiplikation och division med 2.

Cyklisk växling

I en rotation kopieras värdet av den sista biten i växlingens riktning till den första biten (och kopieras till bärbiten).

Det finns också en cyklisk växling genom bärbiten  - där den första biten i växlingsriktningen tar emot värdet från bärbiten, och värdet på den sista biten skiftas till bärbiten.

I programmeringsspråk

Inbyggda operatörer och funktioner som implementerar bitvis logiska operationer i vissa programmeringsspråk:

Språk INTE Och ELLER Exkl. ELLER Växla åt vänster skift höger Övrig
C , C++ , Java [4] , C# , Ruby , Python , JavaScript ~ & | ^ << >>
Pascal [5] inte och eller xor shl shr
Kotlin [6] inv
PL/1 [7] JAG INTE JAG OCH IOR IEOR BOOL
¬ & | ¬
Prolog [8] \ /\ \/

2-adic tolkning

Ett heltal skrivet (i tvås komplement) i ett oändligt (i riktning mot positiva potenser av två) binärt register är ett naturligt objekt för teorin om p-adiska tal för . Uppsättningen av 2-adiska heltal (det vill säga godtyckliga oändliga bitsekvenser) kan ses som en boolesk algebra, precis som uppsättningen värden i ett bitregister med ändlig längd. Alla ovanstående bitvisa operationer visar sig vara kontinuerliga mappningar . Även om praktisk programmering inte har register av oändlig längd, hindrar detta inte användningen av detta teoretiska faktum i kryptografi för att skapa höghastighetskrypteringsalgoritmer.

Praktiska applikationer

Fysisk implementering av bitoperationer

Implementeringen av bitoperationer kan i princip vara vilken som helst: mekanisk (inklusive hydraulisk och pneumatisk), kemisk, termisk, [9] elektrisk, magnetisk och elektromagnetisk (intervall - IR, synlig optisk, UV, och vidare i fallande ordning av våglängder ), såväl som i form av kombinationer, till exempel elektromekaniska .

Under första hälften av 1900-talet, före uppfinningen av transistorer , användes elektromekaniska reläer och vakuumrör .

Under brand och explosiva förhållanden används fortfarande pneumatiska logiska enheter (pneumonik).

De vanligaste elektroniska implementeringarna av bitoperationer som använder transistorer , till exempel resistor-transistor-logik (RTL), diod-transistor-logik (DTL), emitterkopplad logik (ECL), transistor-transistor-logik (TTL), N-MOS- logik , CMOS -logik, etc.

I kvantberäkning, av de listade booleska operationerna, endast NOT och exkl. ELLER (med vissa reservationer). Det finns inga kvantanaloger av AND, OR, etc.

Hårdvarulogikdiagram

Resultatet av en ELLER-NOT- eller ELLER-operation på alla bitar i ett binärt register kontrollerar om registrets värde är noll; detsamma, taget från utgång exkl. ELLER av två register, kontrollerar likheten mellan deras värden sinsemellan.

Bitoperationer används i teckengeneratorer och grafikadaptrar .

Använd i programmering

Genom implementering i processorns aritmetiska logikenhet ( ALU ) är många registerbitoperationer tillgängliga i hårdvara på lågnivåspråk . De flesta processorer implementerar ett register INTE som en instruktion; registrera två-argument OCH, ELLER, XOR; noll jämställdhetskontroll (se ovan); tre typer av bitskift, samt cykliska bitskift.

OCH-registeroperationen används för att:

Register-ELLER-operationen används för att:

Register XOR-operationen används för att invertera bitarna i ett register med en mask.

Vänster- och högerskift används för att multiplicera med 2 respektive heltalsdivision med 2 och extrahera individuella bitar.

Så, till exempel, i Internet-nätverkstekniker, används OCH-operationen mellan värdet på en IP-adress och värdet på en subnätmask för att avgöra om en given adress tillhör ett subnät.

Anteckningar

  1. ↑ Sammansättningsspråk för 8086-mikroprocessorn . Hämtad 19 januari 2010. Arkiverad från originalet 26 januari 2013.
  2. ↑ Multiplikation och division // Handbok för programmeringssystemet Turbo Assembler / Ed. S. B. Orlova.
  3. ↑ PL/I språkreferens Arkiverad 25 september 2018 på Wayback Machine  - sid. 393
  4. ↑ Java-språkspecifikationen. Heltalsoperationer . Datum för åtkomst: 17 januari 2010. Arkiverad från originalet den 28 februari 2012.
  5. ↑ Free Pascal: Referensguide. Logiska operatorer . Hämtad 20 maj 2018. Arkiverad från originalet 21 maj 2018.
  6. ↑ Grundläggande typer - Kotlins programmeringsspråk . Kotlin. Hämtad 2 januari 2017. Arkiverad från originalet 2 januari 2017.
  7. ↑ PL/I språkreferens . Hämtad 17 januari 2010. Arkiverad från originalet 25 september 2018.
  8. ↑ GNU-Prolog Manual. Aritmetik . Datum för åtkomst: 18 januari 2010. Arkiverad från originalet 23 januari 2010.
  9. ↑ En logisk gate för en termisk dator har skapats  // Lenta.ru . - Problem. 05.11.2007 .