Operare pe biți

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 16 decembrie 2021; verificările necesită 10 modificări .

O operație pe biți în programare  este o operație pe lanțuri de biți , de regulă, operațiile logice pe biți și deplasările de biți sunt incluse în această clasă . Sunt folosite în limbaje de programare și în tehnologia digitală , studiate în matematică discretă .

Operațiile pe biți sunt baza prelucrării semnalului digital : prin intermediul acestora, se obține un nou semnal de la unul sau mai multe semnale la intrare, care la rândul lor pot fi alimentate la intrarea uneia sau mai multor astfel de operațiuni. Operațiile pe biți în combinație cu elementele de stocare (de exemplu , declanșatoarele ) realizează toată bogăția posibilităților tehnologiei digitale moderne.

Operații pe biți

Un număr de surse despre limbaje de nivel scăzut numesc operații logice pe biți pur și simplu logice [1] [2] , dar în terminologia programării în limbaje de nivel înalt, numele operațiilor pe biți conțin adjective pe biți , pe biți (de exemplu: „ ȘI logic pe biți ”, este și „înmulțire pe biți”), pe biți .

În unele limbaje de programare, numele operatorilor corespunzătoare operațiilor logice și logice pe biți sunt similare. În plus, limbajul de programare poate permite conversia implicită a unui tip numeric într-un tip boolean și invers. În astfel de limbaje de programare, trebuie să fiți atenți la utilizarea operațiilor logice și pe biți, amestecarea cărora poate duce la erori. De exemplu, în C++ , rezultatul expresiei „2 && 1” ( ȘI logic ) este valoarea booleană adevărată , iar rezultatul expresiei „2 & 1” ( ȘI pe biți ) este valoarea întreagă 0 .

Negație pe biți

Negația pe biți (sau pe biți NOT , complement ) este o operație unară a cărei acțiune este echivalentă cu aplicarea negației logice fiecărui bit al reprezentării binare a operandului. Cu alte cuvinte, în poziția în care a fost 0 în reprezentarea binară a operandului, rezultatul va fi 1 și, invers, acolo unde a fost 1, va fi 0. De exemplu:

NU	01
	zece

Bitwise AND

„ȘI” pe biți  este o operație binară , a cărei acțiune este echivalentă cu aplicarea unui „ȘI” logic fiecărei perechi de biți care se află în aceleași poziții în reprezentările binare ale operanzilor. Cu alte cuvinte, dacă ambii biți corespunzători ai operanzilor sunt 1, bitul rezultat este 1; dacă cel puțin un bit al perechii este 0, bitul rezultat este 0.

Exemplu:

Și	0011
	0101
	0001

SAU pe biți

SAU pe biți  este o operație binară care este echivalentă cu aplicarea unui SAU logic fiecărei perechi de biți care au aceeași poziție în reprezentările binare ale operanzilor. Cu alte cuvinte, dacă ambii biți corespunzători ai operanzilor sunt 0, bitul binar al rezultatului este 0; dacă cel puțin un bit al perechii este 1, bitul binar al rezultatului este 1.

Exemplu:

SAU	0011
	0101
	0111

XOR pe biți

SAU exclusiv pe biți (adăugarea modulului 2) este o operație binară, a cărei acțiune este echivalentă cu aplicarea unui SAU exclusiv logic fiecărei perechi de biți care se află în aceleași poziții în reprezentările binare ale operanzilor. Cu alte cuvinte, dacă ambii biți corespunzători ai operanzilor sunt egali unul cu celălalt, bitul binar al rezultatului este 0; în caz contrar, cifra binară a rezultatului este 1.

Exemplu:

Excl. SAU	0011
	0101
	0110

Primul nume rusesc al operației se datorează faptului că rezultatul acestei operațiuni diferă de rezultatul „SAU” doar într-un caz din 4 cazuri de intrare - ambele 1 (cazul adevărului simultan al argumentelor este „exclus "). Chiar și în gramatica rusă, sensul acestui conjunctiv logic este transmis de uniunea „sau”.

Al doilea nume este cel care este într-adevăr adăugare în inelul de reziduuri modulo doi, din care urmează câteva proprietăți interesante. De exemplu, spre deosebire de „ȘI” și „SAU” de mai sus, această operație este reversibilă: .

În grafica computerizată , „adăugare modulo doi” este utilizată atunci când se afișează sprite -uri pe imagine - aplicarea sa repetată elimină sprite-ul din imagine. Datorită involutivității, aceeași operațiune și-a găsit aplicație în criptografie ca cea mai simplă implementare a unui cifr absolut sigur ( cifrul Vernam ). „Modulo two addition” poate fi folosit și pentru a schimba două variabile folosind algoritmul de schimb XOR .

De asemenea, această operație poate fi numită „inversie de mască”, adică biții care se potrivesc cu 1 din mască sunt inversați față de numărul binar original.

În limbajele obișnuite de programare, doar patru operații logice pe biți sunt implementate de instrumente încorporate: AND, OR, NOT și XOR . Pentru a specifica o operație logică arbitrară pe biți, cele enumerate sunt destul de suficiente și, în plus, după cum reiese din teoria funcțiilor booleene, ne putem limita la un set și mai mic de operații de bază. Există, de asemenea, limbaje de programare în care există o capacitate încorporată de a efectua orice operație logică binară bit cu bit. De exemplu, PL/I are o funcție BOOL încorporată al cărei al treilea argument este pentru specificarea unei operații logice arbitrare care să fie aplicată pe biți la primele două argumente [3] .

Schimbări de biți

Operațiile pe biți includ și deplasări de biți. La deplasare, valorile biților sunt copiate pe cele adiacente în direcția deplasării. Există mai multe tipuri de deplasări - logice , aritmetice și ciclice , în funcție de procesarea biților extremi.

Există, de asemenea, o deplasare la stânga (în direcția de la bitul cel mai puțin semnificativ la cel mai semnificativ) și la dreapta (în direcția de la bitul cel mai semnificativ la cel mai puțin semnificativ).

Schimbare logică

În timpul unei deplasări logice, valoarea ultimului bit în direcția deplasării este pierdută (copiată în bitul de transport), iar primul bit devine zero.

Deplasare aritmetică

O schimbare aritmetică este similară cu o schimbare logică, dar numărul este considerat un număr cu semn, reprezentat într-un cod suplimentar. Deci, cu o schimbare la dreapta, bitul cel mai semnificativ își păstrează valoarea. Deplasarea aritmetică la stânga este identică cu cea logică.

Deplasările aritmetice la stânga și la dreapta sunt folosite pentru înmulțirea și împărțirea rapidă cu 2.

Schimbarea ciclică

Într-o rotație, valoarea ultimului bit în direcția deplasării este copiată în primul bit (și copiată în bitul de transport).

Există , de asemenea, o deplasare ciclică prin bitul de transport  - în care primul bit în direcția deplasării primește valoarea de la bitul de transport, iar valoarea ultimului bit este deplasată în bitul de transport.

În limbaje de programare

Operatori și funcții încorporate care implementează operații logice pe biți în unele limbaje de programare:

Limba	NU	Și	SAU	Excl. SAU	Schimbați la stânga	schimba la dreapta	Alte
C , C++ , Java [4] , C# , Ruby , Python , JavaScript	~	&	|	^	<<	>>
Pascal [5]	nu	și	sau	xor	shl	shr
Kotlin [6]	inv
PL/1 [7]	EU NU	EU SI	IOR	IEOR			BOOL
	¬	&	|	¬
Prolog [8]	\	/\	\/

2-interpretare adica

Un număr întreg scris (în complement a doi) într-un registru binar infinit (în direcția puterilor pozitive a doi) este un obiect natural pentru teoria numerelor p-adice pentru . Setul de numere întregi cu 2 adice (adică secvențe de biți infinite arbitrare) poate fi privit ca o algebră booleană, la fel ca setul de valori ale unui registru de biți cu lungime finită. Toate operațiunile de mai sus pe biți se dovedesc a fi mapări continue . Deși programarea practică nu are registre de lungime infinită, acest lucru nu împiedică utilizarea acestui fapt teoretic în criptografie pentru a crea algoritmi de criptare de mare viteză.

Aplicații practice

Implementarea fizică a operațiilor pe biți

Implementarea operațiunilor cu biți poate fi, în principiu, oricare: mecanice (inclusiv hidraulice și pneumatice), chimice, termice, [9] electrice, magnetice și electromagnetice (domeni - IR, vizibil optic, UV și mai departe în ordinea descrescătoare a lungimii de undă ), precum și sub formă de combinații, de exemplu, electromecanice .

În prima jumătate a secolului al XX-lea, înainte de inventarea tranzistoarelor , se foloseau relee electromecanice și tuburi cu vid .

În condiții de incendiu și explozie, dispozitivele logice pneumatice (pneumonice) sunt încă utilizate.

Cele mai obișnuite implementări electronice ale operațiunilor pe biți care utilizează tranzistori , de exemplu, logica rezistor-tranzistor (RTL), logica diodă-tranzistor (DTL), logica cuplată cu emițător (ECL), logica tranzistor-tranzistor (TTL), logica N-MOS , CMOS -logic etc.

În calculul cuantic, dintre operațiile booleene enumerate, numai NOT și excl. SAU (cu unele rezerve). Nu există analogi cuantici ai AND, OR etc.

Diagrame logice hardware

Rezultatul unei operații OR-NOT sau OR pe toți biții unui registru binar verifică dacă valoarea registrului este zero; la fel, luat de la iesire excl. SAU a două registre, verifică egalitatea valorilor lor între ele.

Operațiile cu biți sunt utilizate în generatoarele de caractere și adaptoarele grafice .

Utilizare în programare

Prin implementarea în unitatea logică aritmetică ( ALU ) a procesorului , multe operațiuni de biți de registru sunt disponibile în hardware în limbaje de nivel scăzut . Majoritatea procesoarelor implementează un registru NU ca instrucțiune; înregistrează ȘI, SAU, XOR cu două argumente; verificare de egalitate zero (vezi mai sus); trei tipuri de deplasări de biți, precum și deplasări ciclice de biți.

Operația de registru AND este utilizată pentru:

• verificați bitul pentru 0 sau 1
• setați 0 la bitul specificat (bit de resetare)

Operația de registru SAU este utilizată pentru:

• setarea 1 la bitul specificat

Operația de registru XOR este utilizată pentru a inversa biții unui registru cu o mască.

Deplasările la stânga și la dreapta sunt folosite pentru înmulțirea cu 2 și, respectiv, împărțirea întregului cu 2, și pentru extragerea de biți individuali.

Deci, de exemplu, în tehnologiile de rețea Internet, operațiunea AND dintre valoarea unei adrese IP și valoarea unei măști de subrețea este utilizată pentru a determina dacă o anumită adresă aparține unei subrețele.

Note

1. ↑ Limbajul de asamblare al microprocesorului 8086 . Consultat la 19 ianuarie 2010. Arhivat din original pe 26 ianuarie 2013. (nedefinit)
2. ↑ Înmulțirea și împărțirea // Manualul sistemului de programare Turbo Assembler / Ed. S. B. Orlova.
3. ↑ PL/I Language Reference Arhivat 25 septembrie 2018 la Wayback Machine  - p. 393
4. ↑ Specificația limbajului Java. Operații cu numere întregi . Data accesului: 17 ianuarie 2010. Arhivat din original la 28 februarie 2012. (nedefinit)
5. ↑ Pascal gratuit: Ghid de referință. Operatori logici . Preluat la 20 mai 2018. Arhivat din original la 21 mai 2018. (nedefinit)
6. ↑ Tipuri de bază - Limbajul de programare Kotlin . Kotlin. Consultat la 2 ianuarie 2017. Arhivat din original pe 2 ianuarie 2017. (nedefinit)
7. ↑ PL/I Language Reference . Consultat la 17 ianuarie 2010. Arhivat din original la 25 septembrie 2018. (nedefinit)
8. ↑ Manual GNU-Prolog. Aritmetica . Data accesului: 18 ianuarie 2010. Arhivat din original la 23 ianuarie 2010. (nedefinit)
9. ↑ A fost creată o poartă logică pentru un computer termic  // Lenta.ru . - Problemă. 05.11.2007 .