Bitová operace

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 16. prosince 2021; kontroly vyžadují 10 úprav .

Bitová operace v programování  je operace s řetězci bitů , do této třídy jsou zpravidla zahrnuty logické bitové operace a bitové posuny . Používají se v programovacích jazycích a digitální technologii , studují se v diskrétní matematice .

Bitové operace jsou základem digitálního zpracování signálu : pomocí nich se získá nový signál z jednoho nebo více signálů na vstupu, který může být zase přiveden na vstup jedné nebo více takových operací. Právě bitové operace v kombinaci s paměťovými prvky (například spouštěči ) realizují veškeré bohatství možností moderní digitální technologie.

Bitové operace

Řada zdrojů o jazycích nižší úrovně nazývá bitové logické operace jednoduše logické [1] [2] , ale v terminologii programování v jazycích vyšší úrovně obsahují názvy bitových operací přídavná jména bitwise , bitwise (například: „bitové logické AND “, je to také „bitové násobení“), bitové .

V některých programovacích jazycích jsou názvy operátorů odpovídajících logickým a bitovým logickým operacím podobné. Kromě toho může programovací jazyk umožňovat implicitní převod numerického typu na booleovský typ a naopak. V takových programovacích jazycích je třeba dávat pozor na používání logických a bitových operací, jejichž míchání může vést k chybám. Například v C++ je výsledkem výrazu "2 && 1" ( logický AND ) logická hodnota true a výsledkem výrazu "2 & 1" ( bitový AND ) je celočíselná hodnota 0 .

Bitová negace

Bitová negace (nebo bitová NEgace , doplněk ) je unární operace, jejíž akce je ekvivalentní aplikaci logické negace na každý bit binární reprezentace operandu. Jinými slovy, na pozici, kde byla v binární reprezentaci operandu 0, bude výsledek 1, a naopak, kde byla 1, bude 0. Například:

NE 01
deset

Bitově AND

Bitové "AND"  je binární operace , jejíž akce je ekvivalentní aplikaci logického "AND" na každý pár bitů, které jsou na stejných pozicích v binárních reprezentacích operandů. Jinými slovy, pokud jsou oba odpovídající bity operandů 1, výsledný bit je 1; pokud je alespoň jeden bit z páru 0, výsledný bit je 0.

Příklad:

A 0011
0101
0001

Bitově NEBO

Bitový OR  je binární operace, která je ekvivalentní aplikaci logického OR na každý pár bitů, které mají stejnou pozici v binárních reprezentacích operandů. Jinými slovy, pokud jsou oba odpovídající bity operandů 0, binární bit výsledku je 0; pokud je alespoň jeden bit z páru 1, binární bit výsledku je 1.

Příklad:

NEBO 0011
0101
0111

Bitový XOR

Bitový exkluzivní OR (modulo 2 sčítání) je binární operace, jejíž akce je ekvivalentní aplikaci logického výlučného OR na každý pár bitů, které jsou na stejných pozicích v binárních reprezentacích operandů. Jinými slovy, pokud jsou oba odpovídající bity operandů navzájem stejné, binární bit výsledku je 0; jinak je binární číslice výsledku 1.

Příklad:

Vyjma NEBO 0011
0101
0110

První ruský název operace je způsoben tím, že výsledek této operace se liší od výsledku "OR" pouze v jednom případě ze 4 vstupních případů - oba 1 (případ současné pravdivosti argumentů je "vyloučen" "). I v ruské gramatice je význam tohoto logického spojovacího výrazu zprostředkován spojením „nebo“.

Druhý název je ten, který je ve skutečnosti sčítáním v kruhu zbytků modulo dva, z čehož plynou některé zajímavé vlastnosti. Například na rozdíl od výše uvedených "AND" a "OR" je tato operace vratná: .

V počítačové grafice se při zobrazování skřítků na obrázku používá "addition modulo two" - jeho opakovaná aplikace skřítka z obrázku odstraní. Díky involutivitě našla stejná operace uplatnění v kryptografii jako nejjednodušší implementace absolutně bezpečné šifry ( Vernamova šifra ). "Modulo two add" lze také použít k výměně dvou proměnných pomocí XOR výměnného algoritmu .

Tuto operaci lze také nazvat "inverze masky", to znamená, že bity, které odpovídají 1 v masce, jsou invertovány z původního binárního čísla.

V běžných programovacích jazycích jsou vestavěnými nástroji implementovány pouze čtyři bitové logické operace: AND, OR, NOT a XOR . Pro specifikaci libovolné bitové logické operace stačí ty uvedené a navíc, jak vyplývá z teorie booleovských funkcí, lze se omezit na ještě menší množinu základních operací. Existují také programovací jazyky, kde je vestavěna schopnost provádět jakoukoli binární logickou operaci bit po bitu. Například PL/I má vestavěnou funkci BOOL, jejíž třetí argument je pro specifikaci libovolné logické operace, která se má bitově aplikovat na první dva argumenty [3] .

Bitové posuny

Bitové operace také zahrnují bitové posuny. Při posunu se bitové hodnoty zkopírují do sousedních ve směru posunu. Existuje několik typů posunů - logické , aritmetické a cyklické , v závislosti na zpracování krajních bitů.

Dochází také k posunu doleva (ve směru od nejméně významného bitu k nejvýznamnějšímu) a doprava (ve směru od nejvýznamnějšího bitu k nejméně významnému).

Logický posun

Během logického posunu se hodnota posledního bitu ve směru posunu ztratí (zkopíruje se do bitu přenosu) a první bit se stane nulou.

Aritmetický posun

Aritmetický posun je podobný logickému posunu, ale číslo je považováno za číslo se znaménkem, zastoupené v doplňkovém kódu. Takže s posunutím doprava si nejvýznamnější bit zachová svou hodnotu. Levý aritmetický posun je shodný s logickým.

Aritmetické posuny doleva a doprava se používají pro rychlé násobení a dělení 2.

Cyklický posun

Při rotaci se hodnota posledního bitu ve směru posunu zkopíruje do prvního bitu (a zkopíruje se do bitu přenosu).

Dochází také k cyklickému posunu přes bit přenosu  - ve kterém první bit ve směru posunu přijímá hodnotu z bitu přenosu a hodnota posledního bitu je posunuta do bitu přenosu.

V programovacích jazycích

Vestavěné operátory a funkce, které implementují bitové logické operace v některých programovacích jazycích:

Jazyk NE A NEBO Vyjma NEBO Shift doleva posunout doprava jiný
C , C++ , Java [4] , C# , Ruby , Python , JavaScript ~ & | ^ << >>
Pascal [5] ne a nebo xor shl shr
Kotlin [6] inv
PL/1 [7] JÁ NE IAND IOR IEOR BOOL
¬ & | ¬
Prolog [8] \ /\ \/

2-adický výklad

Celé číslo zapsané (ve dvojkovém doplňku) v nekonečném (ve směru kladných mocnin dvojky) binárním registru je přirozeným objektem pro teorii p-adických čísel pro . Na sadu 2-adických celých čísel (to znamená libovolné nekonečné bitové sekvence) lze pohlížet jako na booleovskou algebru, stejně jako na sadu hodnot bitového registru konečné délky. Všechny výše uvedené bitové operace se ukáží jako spojitá zobrazení . Přestože praktické programování nemá registry nekonečné délky, nebrání to využití této teoretické skutečnosti v kryptografii k vytvoření vysokorychlostních šifrovacích algoritmů.

Praktické aplikace

Fyzická implementace bitových operací

Provádění bitových operací může být v zásadě libovolné: mechanické (včetně hydraulických a pneumatických), chemické, tepelné, [9] elektrické, magnetické a elektromagnetické (rozsahy - IR, viditelné optické, UV a dále v sestupném pořadí vlnových délek ), stejně jako ve formě kombinací, například elektromechanické .

V první polovině 20. století, před vynálezem tranzistorů , se používaly elektromechanická relé a elektronky .

V požárních a výbušných podmínkách se stále používají pneumatická logická zařízení (pneumonika).

Nejběžnější elektronické implementace bitových operací pomocí tranzistorů , například logika rezistoru a tranzistoru (RTL), logika dioda-tranzistor (DTL), logika s emitorem (ECL), logika tranzistor-tranzistor (TTL), logika N-MOS , logika CMOS atd.

V kvantovém počítání z uvedených booleovských operací pouze NOT a bez. NEBO (s určitými výhradami). Neexistují žádné kvantové analogy AND, OR atd.

Hardwarová logická schémata

Výsledek operace OR-NOT nebo OR na všech bitech binárního registru zkontroluje, zda je hodnota registru nula; totéž, převzato z východu bez. NEBO dvou registrů kontroluje rovnost jejich hodnot mezi sebou.

Bitové operace se používají v generátorech znaků a grafických adaptérech .

Použití v programování

Díky implementaci v aritmetické logické jednotce ( ALU ) procesoru je v hardwaru k dispozici mnoho bitových operací registru v nízkoúrovňových jazycích . Většina procesorů implementuje registr NOT jako instrukci; registr dvouargumentů AND, OR, XOR; kontrola nulové rovnosti (viz výše); tři typy bitových posunů, stejně jako cyklické bitové posuny.

Operace registru AND se používá k:

Operace registru OR se používá k:

Operace registru XOR se používá k invertování bitů registru s maskou.

Posuny vlevo a vpravo se používají pro násobení 2 a dělení celého čísla 2 a extrahování jednotlivých bitů.

Takže například v internetových síťových technologiích se operace AND mezi hodnotou IP adresy a hodnotou masky podsítě používá k určení, zda daná adresa patří do podsítě.

Poznámky

  1. ↑ Jazyk symbolických instrukcí mikroprocesoru 8086 . Získáno 19. ledna 2010. Archivováno z originálu 26. ledna 2013.
  2. ↑ Násobení a dělení // Příručka programovacího systému Turbo Assembler / Ed. S. B. Orlová.
  3. ↑ Jazyková reference PL/I archivována 25. září 2018 na Wayback Machine  - str. 393
  4. ↑ Specifikace jazyka Java. Celočíselné operace . Datum přístupu: 17. ledna 2010. Archivováno z originálu 28. února 2012.
  5. ↑ Free Pascal: Referenční příručka. Logické operátory . Staženo 20. 5. 2018. Archivováno z originálu 21. 5. 2018.
  6. ↑ Základní typy – programovací jazyk Kotlin . Kotlin. Staženo 2. ledna 2017. Archivováno z originálu 2. ledna 2017.
  7. ↑ Reference jazyka PL/I . Získáno 17. ledna 2010. Archivováno z originálu 25. září 2018.
  8. ↑ Manuál GNU-Prolog. Aritmetika . Datum přístupu: 18. ledna 2010. Archivováno z originálu 23. ledna 2010.
  9. ↑ Bylo vytvořeno logické hradlo pro termální počítač  // Lenta.ru . - Problém. 05.11.2007 .