Bitová operace - Bitwise operation

V programování počítače , je bitové operace působí na bitový řetězec , je bitové pole nebo binární číslice (považovaného za bitového řetězce) na úrovni jednotlivých bitů . Jedná se o rychlou a jednoduchou akci, základní pro aritmetické operace vyšší úrovně a přímo podporovanou procesorem . Většina bitových operací je prezentována jako instrukce se dvěma operandy, kde výsledek nahrazuje jeden ze vstupních operandů.

U jednoduchých levných procesorů jsou bitové operace obvykle podstatně rychlejší než dělení, několikrát rychlejší než násobení a někdy výrazně rychlejší než sčítání. Zatímco moderní procesory obvykle provádějí sčítání a násobení stejně rychle jako bitové operace kvůli jejich delším instrukčním kanálům a dalším možnostem architektonického návrhu, bitové operace běžně využívají méně energie kvůli omezenému využívání zdrojů.

Bitové operátory

V níže uvedených vysvětlivkách se jakákoli indikace pozice bitu počítá z pravé (nejméně významné) strany, postupující doleva. Například binární hodnota 0001 (desetinná 1) má nuly na každé pozici, ale na první (tj. Úplně vpravo).

NE

Bitové NOT , nebo komplement , je unární operace , které provádí logické negace na každý bit, tvořit doplněk ty daného binární hodnota. Bity, které jsou 0, se stanou 1 a ty, které jsou 1, se stanou 0. Například:

NOT 0111  (decimal 7)
  = 1000  (decimal 8)

NOT 10101011  (decimal 171)
  = 01010100  (decimal 84)

Bitový doplněk se rovná dvojkovému doplňku hodnoty mínus jedna. Pokud je použita aritmetika dvou komplementů, pak NOT x = -x − 1.

V případě celých čísel bez znaménka je bitový doplněk čísla „zrcadlovým odrazem“ čísla napříč polovičním bodem rozsahu celého čísla bez znaménka. Například pro 8bitová celá čísla bez znaménka NOT x = 255 - x, která lze na grafu zobrazit jako sestupnou čáru, která efektivně „překlopí“ rostoucí rozsah od 0 do 255, do klesajícího rozsahu od 255 do 0. Jednoduchý, ale ilustrativní příklad použití je invertovat obraz ve stupních šedi, kde je každý pixel uložen jako celé číslo bez znaménka.

A

Bitové operace AND 4-bitových celých čísel

Bitové A je binární operace , která má dva stejné délky binární reprezentace a provádí logické AND operace na každé dvojice odpovídajících bitů, což je ekvivalentní k jejich násobení. Pokud jsou tedy oba bity v porovnávané pozici 1, bit ve výsledné binární reprezentaci je 1 (1 × 1 = 1); jinak je výsledek 0 (1 × 0 = 0 a 0 × 0 = 0). Například:

    0101 (decimal 5)
AND 0011 (decimal 3)
  = 0001 (decimal 1)

Operaci lze použít k určení, zda je konkrétní bit nastaven (1) nebo vymazán (0). Například vzhledem k bitovému vzoru 0011 (desítkové 3), abychom určili, zda je nastaven druhý bit, použijeme bitový AND s bitovým vzorem obsahujícím 1 pouze ve druhém bitu:

    0011 (decimal 3)
AND 0010 (decimal 2)
  = 0010 (decimal 2)

Protože je výsledek 0010 nenulový, víme, že byl nastaven druhý bit v původním vzoru. Toto se často nazývá bitové maskování . (Analogicky použití krycích pásek nebo masek , částí, které by neměly být měněny, nebo částí, které nejsou zajímavé. V tomto případě hodnoty 0 maskují bity, které nejsou zajímavé.)

Bitový AND lze použít k vymazání vybraných bitů (nebo příznaků ) registru, ve kterém každý bit představuje individuální booleovský stav. Tato technika je efektivní způsob, jak ukládat řadu booleovských hodnot pomocí co nejméně paměti.

Například 0110 (desetinné číslo 6) lze považovat za sadu čtyř příznaků, kde první a čtvrtý příznak jsou jasné (0) a druhý a třetí příznak jsou nastaveny (1). Třetí příznak lze vymazat pomocí bitového AND se vzorem, který má nulu pouze ve třetím bitu:

    0110 (decimal 6)
AND 1011 (decimal 11)
  = 0010 (decimal 2)

Kvůli této vlastnosti je snadné zkontrolovat paritu binárního čísla kontrolou hodnoty nejnižšího bitu. Pomocí výše uvedeného příkladu:

    0110 (decimal 6)
AND 0001 (decimal 1)
  = 0000 (decimal 0)

Protože 6 AND 1 je nula, 6 je dělitelné dvěma, a proto sudé.

NEBO

Bitový NEBO 4bitová celá čísla

Bitový je binární operace , která vyžaduje dva vzorky bitů stejné délky a vykonává logický včetně nebo operace na každý pár odpovídajících bitů. Výsledek na každé pozici je 0, pokud jsou oba bity 0, zatímco jinak je výsledek 1. Například:

   0101 (decimal 5)
OR 0011 (decimal 3)
 = 0111 (decimal 7)

Bitový OR lze použít k nastavení 1 vybraných bitů registru popsaného výše. Například čtvrtý bit 0010 (desetinný 2) lze nastavit provedením bitového NEBO se vzorem pouze se čtvrtou bitovou sadou:

   0010 (decimal 2)
OR 1000 (decimal 8)
 = 1010 (decimal 10)

XOR

Bitový XOR 4bitových celých čísel

Bitový XOR je binární operace , která vyžaduje dva vzorky bitů stejné délky a provádí logické exkluzivní OR operace na každý pár odpovídajících bitů. Výsledek v každé pozici je 1, pokud je pouze jeden z bitů 1, ale bude 0, pokud jsou oba 0 nebo oba jsou 1. V tomto provedeme srovnání dvou bitů, přičemž 1, pokud jsou dva bity různé, a 0 pokud jsou stejné. Například:

    0101 (decimal 5)
XOR 0011 (decimal 3)
  = 0110 (decimal 6)

Bitový XOR lze použít k invertování vybraných bitů v registru (také se nazývá přepínání nebo překlápění). Jakýkoli bit může být přepnut XORing to s 1. Například, vzhledem k bitovému vzoru 0010 (desítkové 2) mohou být druhý a čtvrtý bit přepnuty bitovým XOR s bitovým vzorem obsahujícím 1 na druhé a čtvrté pozici:

    0010 (decimal 2)
XOR 1010 (decimal 10)
  = 1000 (decimal 8)

Tuto techniku ​​lze použít k manipulaci s bitovými vzory představujícími sady booleovských stavů.

Programátoři v jazyce Assembly a optimalizující kompilátory někdy používají XOR jako zkratku pro nastavení hodnoty registru na nulu. Provedení XOR na hodnotě proti sobě vždy vede k nule a v mnoha architekturách tato operace vyžaduje méně hodinových cyklů a paměti, než načtení nulové hodnoty a její uložení do registru.

Pokud je množina bitových řetězců pevné délky n (tj. Strojová slova ) považována za n -dimenzionální vektorový prostor nad polem , pak přidání vektoru odpovídá bitovému XOR. ${\ displaystyle {\ bf {F}} _ {2}^{n}}$ ${\ displaystyle {\ bf {F}} _ {2}}$

Matematické ekvivalenty

Za předpokladu , že pro nezáporná celá čísla lze bitové operace zapsat následujícím způsobem: ${\ Displaystyle x \ geq y}$

${\ Displaystyle {\ begin {aligned} \ operatorname {NOT} x & = \ sum _ {n = 0}^{\ lfloor \ log _ {2} (x) \ rfloor} 2^{n} \ left [\ left (\ left \ lfloor {\ frac {x} {2^{n}}} \ right \ rfloor {\ bmod {2}}+1 \ right) {\ bmod {2}} \ right] = 2^{\ left \ lfloor \ log _ {2} (x) \ right \ rfloor +1} -1-x \\ x \ operatorname {AND} y & = \ sum _ {n = 0}^{\ lfloor \ log _ {2 } (x) \ rfloor} 2^{n} \ left (\ left \ lfloor {\ frac {x} {2^{n}}} \ right \ rfloor {\ bmod {2}} \ right) \ left ( \ left \ lfloor {\ frac {y} {2^{n}}} \ right \ rfloor {\ bmod {2}} \ right) \\ x \ operatorname {OR} y & = \ sum _ {n = 0} ^{\ lfloor \ log _ {2} (x) \ rfloor} 2^{n} \ left (\ left [\ left (\ left \ lfloor {\ frac {x} {2^{n}}} \ right \ rfloor {\ bmod {2}} \ right)+\ left (\ left \ lfloor {\ frac {y} {2^{n}}} \ right \ rfloor {\ bmod {2}} \ right)+\ vlevo (\ left \ lfloor {\ frac {x} {2^{n}}} \ right \ rfloor {\ bmod {2}} \ right) \ left (\ left \ lfloor {\ frac {y} {2^ {n}}} \ right \ rfloor {\ bmod {2}} \ right) \ right] {\ bmod {2}} \ right) \\ x \ operatorname {XOR} y & = \ sum _ {n = 0} ^{\ lfloor \ log _ {2} (x) \ rfloor} 2^{n} \ left (\ left [\ left (\ left \ lfloor {\ frac {x} {2^{n}}} \ right \ rfloor {\ bmod {2}} \ right)+\ vlevo (\ left \ lfloor {\ frac {y} {2^{n}}} \ right \ rfloor {\ bmod {2}} \ right) \ right] {\ bmod {2}} \ right) = \ sum _ {n = 0}^{\ lfloor \ log _ {2} (x) \ rfloor} 2^{n} \ left [\ left (\ left \ lfloor {\ frac {x} {2^{n}} } \ right \ rfloor +\ left \ lfloor {\ frac {y} {2^{n}}} \ right \ rfloor \ right) {\ bmod {2}} \ right] \ end {aligned}}}$

Tabulka pravdy pro všechny binární logické operátory

Existuje 16 možných pravdivostních funkcí dvou binárních proměnných ; toto definuje tabulku pravdy .

Zde jsou bitově ekvivalentní operace dvou bitů P a Q:

Bitové posuny

Tyto bitové posuny jsou někdy považovány za bitové operace, protože léčbě hodnotu jako řada bitů spíše než jako numerický množství. Při těchto operacích se číslice přesouvají nebo posouvají doleva nebo doprava. Registry v počítačovém procesoru mají pevnou šířku, takže některé bity budou „vysunuty“ z registru na jednom konci, zatímco stejný počet bitů je „posunut“ z druhého konce; rozdíly mezi operátory bitového posunu spočívají v tom, jak určují hodnoty posunutých bitů.

Bitové adresování

Pokud je šířka registru (často 32 nebo dokonce 64) větší než počet bitů (obvykle 8) nejmenší adresovatelné jednotky (atomový prvek), často nazývané byte, operace posunu vyvolávají schéma adresování od bytů do bitů. Orientace „doleva“ a „doprava“ jsou tedy převzaty ze standardního psaní čísel v zápisu hodnoty místa , takže posun vlevo se zvýší a posun vpravo hodnotu čísla sníží-pokud se nejprve čtou levé číslice, tvoří big-endianskou orientaci. Bez ohledu na hraniční efekty na obou koncích registru se aritmetické a logické operace posunu chovají stejně a posun o 8 bitových pozic přenáší bitový vzor o 1 bajtovou pozici následujícím způsobem:

Aritmetický posun

Aritmetický posun doleva

Pravý aritmetický posun

Při aritmetickém posunu jsou bity, které jsou posunuty z obou konců, zahozeny. Při levém aritmetickém posunu jsou nuly posunuty vpravo; v pravém aritmetickém posunu je znaménkový bit (MSB v doplňku dvou) posunut vlevo, čímž je zachováno znaménko operandu.

Tento příklad používá 8bitový registr, interpretovaný jako dvojkový doplněk:

   00010111 (decimal +23) LEFT-SHIFT
=  00101110 (decimal +46)

   10010111 (decimal −105) RIGHT-SHIFT
=  11001011 (decimal −53)

V prvním případě byla číslice úplně vlevo posunuta za konec registru a nová 0 byla posunuta do polohy úplně vpravo. Ve druhém případě byla pravá 1 posunuta (možná do vlajky přenosu ) a nová 1 byla zkopírována do polohy úplně vlevo, přičemž se zachoval znak čísla. Vícenásobné směny jsou někdy zkráceny na jednu směnu o určitý počet číslic. Například:

   00010111 (decimal +23) LEFT-SHIFT-BY-TWO
=  01011100 (decimal +92)

A vlevo aritmetický posun o n je ekvivalentní vynásobením 2 ⁿ (za předpokladu, že hodnota není přetečení ), zatímco pravý aritmetický posun o n z a doplňkovém hodnota se rovná brát podlahu dělení o 2 ⁿ . Pokud je binární číslo považováno za komplement , pak stejná operace pravého posunu má za následek dělení 2 ⁿ a zaokrouhlování směrem k nule .

Logický posun

Levý logický posun

Správný logický posun

V logickém posunu jsou nuly posunuty, aby nahradily zahozené bity. Logické a aritmetické posuny doleva jsou proto naprosto stejné.

Protože však logický posun doprava vkládá do nejvýznamnějšího bitu hodnotu 0 bitů, místo kopírování znakového bitu je ideální pro binární čísla bez znaménka, zatímco aritmetický posun doprava je ideální pro binární čísla komplementu podepsaných dvou .

Kruhový posun

Další formou posunu je kruhový posun , bitová rotace nebo bitová rotace .

Točit se

Kruhový posun doleva nebo otočení

Pravý kruhový posun nebo otočení

Při této operaci, někdy nazývané rotate no carry , se bity „otáčejí“, jako by se spojil levý a pravý konec registru. Hodnota, která je při posunu doleva posunuta doprava, je jakákoli hodnota, která byla posunuta doleva, a naopak pro operaci posunu doprava. To je užitečné, pokud je nutné zachovat všechny existující bity, a často se to používá v digitální kryptografii .

Otočit skrz přenášení

Otočit doleva skrz přenášení

Otočení doprava přenášením

Rotate through carry je varianta operace rotate, kde bit, který je posunut (na obou koncích) je stará hodnota příznaku carry a bit, který je posunut ven (na druhém konci), se stane novou hodnotou vlajka nošení.

Jediné otočení přenášením může simulovat logický nebo aritmetický posun jedné polohy předem nastavením vlajky přenosu. Pokud například příznak přenosu obsahuje 0, pak x RIGHT-ROTATE-THROUGH-CARRY-BY-ONEjde o logický posun doprava a pokud příznak přenosu obsahuje kopii znakového bitu, pak x RIGHT-ROTATE-THROUGH-CARRY-BY-ONEjde o aritmetický posun doprava. Z tohoto důvodu se některé mikrokontroléry, jako jsou low -endové PIC, jen otáčejí a otáčejí přenášením a neobtěžují se pokyny pro aritmetické nebo logické posuny.

Rotate through carry je obzvláště užitečné při provádění posunů na číslech větších než je velikost nativního slova procesoru , protože pokud je velké číslo uloženo ve dvou registrech, bit, který je posunut z jednoho konce prvního registru, musí přijít na druhém konci druhý. Při rotaci při přenosu je tento bit „uložen“ do vlajky přenosu během první směny, připraven k zařazení během druhé směny bez jakékoli další přípravy.

V jazycích vysoké úrovně

C-rodina

V jazycích rodiny C jsou operátory logických posunů " <<" pro posun vlevo a " >>" pro posun vpravo. Počet míst k posunu je uveden jako druhý argument operátora. Například,

x = y << 2;

přiřadí xvýsledek posunu ydoleva o dva bity, což je ekvivalent násobení čtyřmi.

Posuny mohou mít za následek implementačně definované chování nebo nedefinované chování , takže při jejich používání je třeba dávat pozor. Výsledkem posunutí o počet bitů větší nebo rovný velikosti slova je nedefinované chování v C a C ++. Posunutí záporné hodnoty doprava je definováno implementací a není doporučeno správnou kódovací praxí; výsledek posunutí podepsané hodnoty doleva není definován, pokud výsledek nelze v typu výsledku reprezentovat.

V C#je pravý posun aritmetický posun, když je první operand int nebo long. Pokud je první operand typu uint nebo ulong, pravý posun je logický posun.

Kruhové posuny

C-rodina jazyků postrádá rotační operátor (ačkoli C ++ 20 poskytuje std::rotla std::rotr), ale jeden může být syntetizován z operátorů směny. Je třeba dbát na to, aby prohlášení bylo dobře formulováno, aby se zabránilo nedefinovanému chování a načasování útoků v softwaru s požadavky na zabezpečení. Například naivní implementace, která odešla, otočí 32bitovou hodnotu bez znaménka xpodle npozic jednoduše:

uint32_t x = ..., n = ...;
uint32_t y = (x << n) | (x >> (32 - n));

Posun o 0bity však má za následek nedefinované chování ve výrazu pravé ruky, (x >> (32 - n))protože 32 - 0je 32a 32je mimo rozsah [0 - 31]včetně. Druhý pokus může mít za následek:

uint32_t x = ..., n = ...;
uint32_t y = n ? (x << n) | (x >> (32 - n)) : x;

kde je částka posunu testována, aby se zajistilo, že nezavede nedefinované chování. Větev však přidá další cestu k kódu a představuje příležitost pro časovou analýzu a útok, což je u softwaru s vysokou integritou často nepřijatelné. Kód se navíc kompiluje do více strojových instrukcí, což je často méně efektivní než nativní instrukce procesoru.

Abyste se vyhnuli nedefinovanému chování a větvím pod GCC a Clang, doporučujeme následující. Vzor je rozpoznán mnoha kompilátory a kompilátor vydá jednu instrukci otočení:

uint32_t x = ..., n = ...;
uint32_t y = (x << n) | (x >> (-n & 31));

Existují také kompilátor specifické intrinsics prováděcí kruhové směny , jako _rotl8, _rotl16 , _rotr8, _rotr16 v Microsoft Visual C ++ . Clang poskytuje některé vlastnosti rotace pro kompatibilitu společnosti Microsoft, které trpí výše uvedenými problémy. GCC nenabízí vnitřní rotaci. Intel také poskytuje x86 Intrinsics .

Jáva

V Javě jsou všechny typy celých čísel podepsány, takže operátory " <<" a " >>" provádějí aritmetické posuny. Java přidává operátor " >>>" k provádění logických posunů doprava, ale protože logické a aritmetické operace posunu doleva jsou stejné pro celé číslo se znaménkem, neexistuje <<<v Javě žádný operátor " ".

Další podrobnosti o operátorech Java shift:

• Operátory <<(posun vlevo), >>(podepsaný posun doprava) a >>>(nepodepsaný posun vpravo) se nazývají operátory posunu .
• Typ výrazu posunu je podporovaný typ levého operandu. Například aByte >>> 2je ekvivalentní .((int) aByte) >>> 2
• Pokud je podporovaný typ levého operandu int, použije se jako vzdálenost posunu pouze pět bitů nejnižšího řádu pravého operandu. Je to, jako kdyby pravý operand byl podroben bitovému logickému operátoru AND & s hodnotou masky 0x1f (0b11111). Skutečně použitá vzdálenost posunu je proto vždy v rozsahu 0 až 31 včetně.
• Pokud je podporovaný typ levého operandu dlouhý, pak se jako vzdálenost posunu použije pouze šest bitů nejnižšího řádu pravého operandu. Je to, jako kdyby pravý operand byl podroben bitovému logickému operátoru AND & s hodnotou masky 0x3f (0b111111). Skutečně použitá vzdálenost posunu je proto vždy v rozsahu 0 až 63 včetně.
• Hodnota n >>> sje n pravým posunuté s bitové pozice s nulovou-prodloužení.
• V bitových a posunových operacích je typ byteimplicitně převeden na int. Pokud je bajtová hodnota záporná, nejvyšší bit je jedna, pak se jednotky používají k vyplnění dalších bajtů v int. Výsledkem tedy bude .byte b1 = -5; int i = b1 | 0x0200;i == -5

JavaScript

JavaScript používá bitové operace k vyhodnocení každé ze dvou nebo více jednotek umístěných na 1 nebo 0.

Pascal

V Pascalu, stejně jako ve všech jeho dialektech (jako je Object Pascal a Standard Pascal ), jsou logické operátory levého a pravého posunu " shl" a " shr". I pro celá čísla se znaménkem se shrchová jako logický posun a nekopíruje znaménkový bit. Druhým argumentem je počet míst k posunu. Následující například přiřadí x výsledek posunutí y doleva o dva bity:

x := y shl 2;

jiný

• popcount , používaný v kryptografii
• počítat vedoucí nuly

Aplikace

Bitové operace jsou nutné zejména při programování na nižší úrovni, jako jsou ovladače zařízení, grafika na nízké úrovni, sestavování paketů komunikačních protokolů a dekódování.

Přestože stroje často mají účinné vestavěné pokyny pro provádění aritmetických a logických operací, všechny tyto operace lze provádět kombinací bitových operátorů a nulového testování různými způsoby. Například zde je implementace pseudokódu staroegyptského násobení, která ukazuje, jak vynásobit dvě libovolná celá čísla aa b( avětší než b) pomocí pouze bitshiftů a sčítání:

c ← 0
while b ≠ 0
    if (b and 1) ≠ 0
        c ← c + a
    left shift a by 1
    right shift b by 1
return c

Dalším příkladem je implementace pseudokódu sčítání, která ukazuje, jak vypočítat součet dvou celých čísel aa bpoužít bitové operátory a nulové testování:

while a ≠ 0
    c ← b and a
    b ← b xor a
    left shift c by 1
    a ← c
return b

Booleovská algebra

Někdy je užitečné zjednodušit složité výrazy tvořené bitovými operacemi. Například při psaní překladačů. Cílem kompilátoru je přeložit programovací jazyk na vysoké úrovni do co nejefektivnějšího strojového kódu . Booleovská algebra se používá ke zjednodušení složitých bitových výrazů.

A

• x & y = y & x
• x & (y & z) = (x & y) & z
• x & 0xFFFF = x
• x & 0 = 0

• x & x = x

NEBO

• x | y = y | x
• x | (y | z) = (x | y) | z
• x | 0 = x
• x | 0xFFFF = 0xFFFF
• x | x = x

NE

• ~(~x) = x

XOR

• x ^ y = y ^ x
• x ^ (y ^ z) = (x ^ y) ^ z
• x ^ 0 = x
• x ^ y ^ y = x
• x ^ x = 0
• x ^ 0xFFFF = ~x

XOR lze navíc skládat pomocí 3 základních operací (AND, OR, NOT)

• a ^ b = (a | b) & (~a | ~b)
• a ^ b = (a & ~b) | (~a & b)

Ostatní

• x | (x & y) = x
• x & (x | y) = x
• ~(x | y) = ~x & ~y
• ~(x & y) = ~x | ~y
• x | (y & z) = (x | y) & (x | z)
• x & (y | z) = (x & y) | (x & z)
• x & (y ^ z) = (x & y) ^ (x & z)
• x + y = (x ^ y) + ((x & y) << 1)
• x - y = ~(~x + y)

Inverze a řešení rovnic

Řešení proměnných v booleovské algebře může být obtížné, protože na rozdíl od běžné algebry nemá několik operací inverze. Operace bez inverzí ztratí při provádění některé z původních datových bitů a tyto chybějící informace nelze obnovit.

• Má inverzní
  • NE
  • XOR
  • Otočit doleva
  • Otočit doprava
• Žádný inverzní
  • A
  • NEBO
  • Řazení doleva
  • Posuňte doprava

Pořadí operací

Operace na začátku tohoto seznamu se provedou jako první. Úplnější seznam najdete v hlavním článku.

• ( )
• ~ -
• * / %
• + -
• << >>
• &
• ^
• |

Viz také

Reference

externí odkazy

• Online bitová kalkulačka podporuje bitové AND, OR a XOR
• Rozdělení pomocí bitshiftů
• „ Bitwise Operations Mod N “ od Enrique Zelenyho, Wolfram Demonstrations Project .
• „ Zápletky kompozic bitových operací “ od Enrique Zelenyho, The Wolfram Demonstrations Project.