Bitdrift
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 16. december 2021; checks kræver 10 redigeringer .En bitvise operation i programmering er en operation på kæder af bit , som regel er logiske bitvise operationer og bitskift inkluderet i denne klasse . De bruges i programmeringssprog og digital teknologi , studeret i diskret matematik .
Bitoperationer er grundlaget for digital signalbehandling : ved hjælp af dem opnås et nyt signal fra et eller flere signaler ved indgangen, som igen kan føres til indgangen af en eller flere sådanne operationer. Det er bitoperationer i kombination med lagringselementer (for eksempel triggere ), der realiserer al rigdommen af mulighederne i moderne digital teknologi.
Bitvise operationer
En række kilder om sprog på lavt niveau kalder bitvise logiske operationer ganske enkelt logiske [1] [2] , men i terminologien for programmering i sprog på højt niveau indeholder navnene på bitvise operationer adjektiver bitvis , bitvis (for eksempel: "bitvis logisk OG ", det er også "bitvis multiplikation"), bitvis .
I nogle programmeringssprog er navnene på de operatører, der svarer til logiske og bitvise logiske operationer, ens. Derudover kan programmeringssproget tillade implicit konvertering af en numerisk type til en boolesk type og omvendt. I sådanne programmeringssprog skal man være forsigtig med brugen af logiske og bitvise operationer, hvis blanding kan føre til fejl. For eksempel i C++ er resultatet af udtrykket "2 && 1" ( logisk OG ) den boolske værdi true , og resultatet af udtrykket "2 & 1" ( bitvist OG ) er heltalsværdien 0 .
Bitvis negation
Bitwise negation (eller bitwise NOT , complement ) er en unær operation, hvis handling svarer til at anvende logisk negation til hver bit af den binære repræsentation af operanden. Med andre ord, på den position, hvor der var 0 i den binære repræsentation af operanden, vil resultatet være 1, og omvendt, hvor der var 1, vil der være 0. For eksempel:
| IKKE | 01 |
| ti | |
Bitvist OG
Bitvist "AND" er en binær operation , hvis handling svarer til at anvende et logisk "AND" på hvert par bit, der er i de samme positioner i de binære repræsentationer af operanderne. Med andre ord, hvis begge tilsvarende bit af operanderne er 1, er den resulterende bit 1; hvis mindst én bit af parret er 0, er den resulterende bit 0.
Eksempel:
| Og | 0011 |
| 0101 | |
| 0001 | |
Bitvist ELLER
Bitwise OR er en binær operation, der svarer til at anvende en logisk OR på hvert par bits, der har den samme position i de binære repræsentationer af operanderne. Med andre ord, hvis begge tilsvarende bit af operanderne er 0, er den binære bit af resultatet 0; hvis mindst én bit af parret er 1, er den binære bit af resultatet 1.
Eksempel:
| ELLER | 0011 |
| 0101 | |
| 0111 | |
Bitwise XOR
Bitwise exclusive OR (modulo 2 addition) er en binær operation, hvis handling svarer til at anvende en logisk eksklusiv OR til hvert par bits, der er i de samme positioner i de binære repræsentationer af operanderne. Med andre ord, hvis begge tilsvarende bit af operanderne er lig med hinanden, er den binære bit af resultatet 0; ellers er det binære ciffer i resultatet 1.
Eksempel:
| Ekskl. ELLER | 0011 |
| 0101 | |
| 0110 | |
Det første russiske navn på operationen skyldes det faktum, at resultatet af denne operation kun adskiller sig fra resultatet af "ELLER" i ét tilfælde ud af 4 inputtilfælde - begge 1 (tilfældet med samtidig sandhed af argumenterne er "udelukket "). Selv i russisk grammatik formidles betydningen af denne logiske forbindelse af fagforeningen "eller".
Det andet navn er det, der egentlig er tilføjelse i ringen af rester modulo to, hvorfra nogle interessante egenskaber følger. For eksempel, i modsætning til ovenstående "AND" og "OR", er denne operation reversibel: .
I computergrafik bruges "addition modulo two" ved visning af sprites på billedet - dens gentagne anvendelse fjerner sprite fra billedet. På grund af involutivitet har den samme operation fundet anvendelse i kryptografi som den enkleste implementering af en absolut sikker cipher ( Vernam cipher ). "Modulo to addition" kan også bruges til at udveksle to variable ved hjælp af XOR-udvekslingsalgoritmen .
Denne operation kan også kaldes "maske-inversion", det vil sige, at de bits, der matcher 1-tallet i masken, inverteres fra det originale binære tal.
I almindelige programmeringssprog implementeres kun fire bitvise logiske operationer af indbyggede værktøjer: AND, OR, NOT og XOR . For at specificere en vilkårlig bitvis logisk operation er de anførte ganske nok, og desuden, som det følger af teorien om boolske funktioner, kan man begrænse sig til et endnu mindre sæt af grundlæggende operationer. Der er også programmeringssprog, hvor der er en indbygget evne til at udføre enhver binær logisk operation bit for bit. For eksempel har PL/I en indbygget BOOL-funktion, hvis tredje argument er til at specificere en vilkårlig logisk operation, der skal anvendes bitvis på de to første argumenter [3] .
Bitskift
Bitvise operationer inkluderer også bitskift. Ved skift kopieres bitværdier til tilstødende i skiftets retning. Der er flere typer forskydninger - logiske , aritmetiske og cykliske , afhængigt af behandlingen af de ekstreme bits.
Der er også et skift til venstre (i retningen fra den mindst signifikante bit til den mest signifikante) og til højre (i retningen fra den mest signifikante bit til den mindst signifikante).
Logisk skift
Under et logisk skift går værdien af den sidste bit i skiftets retning tabt (kopieret til bærebitten), og den første bit bliver nul.
Aritmetisk skift
Et aritmetisk skift ligner et logisk skift, men tallet betragtes som et tal med fortegn, repræsenteret i en ekstra kode. Så med et højreskift bevarer den mest signifikante bit sin værdi. Det venstre aritmetiske skift er identisk med det logiske.
Aritmetiske venstre- og højreforskydninger bruges til hurtig multiplikation og division med 2.
Cyklisk skift
I en rotation kopieres værdien af den sidste bit i skiftets retning til den første bit (og kopieres til bærebitten).
Der er også et cyklisk skift gennem bærebitten - hvor den første bit i skiftets retning modtager værdien fra bærebitten, og værdien af den sidste bit flyttes ind i bærebitten.
I programmeringssprog
Indbyggede operatører og funktioner, der implementerer bitvise logiske operationer i nogle programmeringssprog:
| Sprog | IKKE | Og | ELLER | Ekskl. ELLER | Skift til venstre | skift til højre | Andet |
|---|---|---|---|---|---|---|---|
| C , C++ , Java [4] , C# , Ruby , Python , JavaScript | ~ | & | | | ^ | << | >> | |
| Pascal [5] | ikke | og | eller | xor | shl | shr | |
| Kotlin [6] | inv | ||||||
| PL/1 [7] | JEG IKKE | JEG OG | IOR | IEOR | BOOL | ||
| ¬ | & | | | ¬ | ||||
| Prolog [8] | \ | /\ | \/ |
2-adic fortolkning
Et heltal skrevet (i to-komplement) i et uendeligt (i retning af positive potenser af to) binært register er et naturligt objekt for teorien om p-adiske tal for . Sættet af 2-adiske heltal (det vil sige vilkårlige uendelige bitsekvenser) kan ses som en boolsk algebra, ligesom værdisættet i et bitregister med endelig længde. Alle de ovennævnte bitvise operationer viser sig at være kontinuerlige kortlægninger . Selvom praktisk programmering ikke har registre af uendelig længde, forhindrer dette ikke brugen af denne teoretiske kendsgerning i kryptografi til at skabe højhastighedskrypteringsalgoritmer.
Praktiske applikationer
Fysisk implementering af bitoperationer
Implementeringen af bitoperationer kan i princippet være en hvilken som helst: mekanisk (inklusive hydraulisk og pneumatisk), kemisk, termisk, [9] elektrisk, magnetisk og elektromagnetisk (områder - IR, synlig optisk, UV og yderligere i faldende rækkefølge af bølgelængder ), såvel som i form af kombinationer, for eksempel elektromekaniske .
I første halvdel af det 20. århundrede, før opfindelsen af transistorer , blev elektromekaniske relæer og vakuumrør brugt .
Under brand og eksplosive forhold bruges pneumatiske logiske enheder (pneumonics) stadig.
De mest almindelige elektroniske implementeringer af bitoperationer ved hjælp af transistorer , for eksempel modstand-transistor-logik (RTL), diode-transistor-logik (DTL), emitter-koblet logik (ECL), transistor-transistor-logik (TTL), N-MOS- logik , CMOS -logik osv.
I kvanteberegning, af de anførte booleske operationer, kun NOT og ekskl. ELLER (med nogle forbehold). Der er ingen kvanteanaloger af AND, OR osv.
Hardware logiske diagrammer
Resultatet af en ELLER-NOT- eller ELLER-operation på alle bits i et binært register kontrollerer, om værdien af registret er nul; samme, taget fra udkørsel ekskl. ELLER af to registre, kontrollerer ligheden af deres værdier indbyrdes.
Bitoperationer bruges i tegngeneratorer og grafikadaptere .
Brug i programmering
Gennem implementering i processorens aritmetiske logiske enhed ( ALU ) er mange registerbit-operationer tilgængelige i hardware på lavniveau-sprog . De fleste processorer implementerer et register IKKE som en instruktion; register to-argument OG, ELLER, XOR; nul lighedskontrol (se ovenfor); tre typer af bitskift, samt cykliske bitskift.
AND register operationen bruges til at:
- check bit for 0 eller 1
- sæt 0 til specificeret bit (nulstil bit)
Register-ELLER-operationen bruges til at:
- indstilling 1 til den angivne bit
Register XOR-operationen bruges til at invertere bits af et register med en maske.
Venstre- og højreforskydninger bruges til henholdsvis at gange med 2 og heltalsdivision med 2 og udtrække individuelle bits.
Så for eksempel i internetnetværksteknologier bruges OG-operationen mellem værdien af en IP-adresse og værdien af en undernetmaske til at bestemme, om en given adresse tilhører et undernet.
Noter
- ↑ Samlesprog for 8086-mikroprocessoren . Hentet 19. januar 2010. Arkiveret fra originalen 26. januar 2013.
- ↑ Multiplikation og division // Håndbog i Turbo Assembler-programmeringssystemet / Ed. S. B. Orlova.
- ↑ PL/I sprogreference Arkiveret 25. september 2018 på Wayback Machine - s. 393
- ↑ Java-sprogspecifikationen. Heltalsoperationer . Dato for adgang: 17. januar 2010. Arkiveret fra originalen 28. februar 2012.
- ↑ Free Pascal: Referenceguide. Logiske operatorer . Hentet 20. maj 2018. Arkiveret fra originalen 21. maj 2018.
- ↑ Grundlæggende typer - Kotlin-programmeringssprog . Kotlin. Hentet 2. januar 2017. Arkiveret fra originalen 2. januar 2017.
- ↑ PL/I sprogreference . Hentet 17. januar 2010. Arkiveret fra originalen 25. september 2018.
- ↑ GNU-Prolog Manual. Aritmetik . Dato for adgang: 18. januar 2010. Arkiveret fra originalen 23. januar 2010.
- ↑ En logisk port til en termisk computer er blevet oprettet // Lenta.ru . - Udstedelse. 05.11.2007 .