Ebben a cikkben bemutatom a bitműveletek működését. Első pillantásra bonyolultnak és haszontalannak tűnhetnek, de valójában egyáltalán nem az. Erről igyekszem meggyőzni.
A bitenkénti operátorok közvetlenül egy szám bitjein működnek, így a példákban szereplő számok binárisak lesznek.
A következő bitenkénti operátorokra térek ki:
A bitműveleteket a diszkrét matematika tanulmányozza, és a digitális technológia alapját is képezi, mivel ezek a logikai kapuk működésének logikáján alapulnak - az alapvető elemek digitális áramkörök. A diszkrét matematikában, akárcsak a digitális technológiában, igazságtáblázatokat használnak a működésük leírására. Úgy tűnik, hogy az igazságtáblázatok nagyban megkönnyítik a bitenkénti műveletek megértését, ezért ebben a cikkben bemutatom őket. A magas szintű programozási nyelvekben azonban szinte soha nem használják a bitenkénti operátorok magyarázatában.
A bitenkénti operátorokról is tudnia kell:
A bitenkénti VAGY egyenértékű a logikai VAGY-val, de egy bináris szám minden bitpárjára vonatkozik. Az eredmény bináris számjegye csak akkor 0, ha B-ben mindkét megfelelő bit 0. Minden más esetben a bináris eredmény 1. Vagyis ha a következő igazságtáblázatunk van:
38 | Az 53 ilyen lesz:
| A | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| B | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| A | B | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
Ennek eredményeként 110111 2 vagy 55 10 értéket kapunk.
A bitenkénti ÉS a bitenkénti VAGY ellentéte. Az eredmény bináris számjegye csak akkor 1, ha az operandusok mindkét megfelelő bitje 1. Más szóval azt mondhatjuk, hogy az eredményül kapott szám bináris számjegyei az operandus megfelelő bitjeinek szorzásának eredménye: 1x1 \u003d 1 , 1x0 \u003d 0. A következő igazságtáblázat a bitenkénti ÉS-nek felel meg:
Példa a bitenkénti ÉS műveletre a 38-as és 53-as kifejezésen:
| A | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| B | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| A&B | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 |
Ennek eredményeként 100100 2-t vagy 36 10-et kapunk.
A bitenkénti ÉS operátor segítségével ellenőrizheti, hogy egy szám páros vagy páratlan. Egész számok esetében, ha a legkisebb jelentőségű bit 1, akkor a szám páratlan (binárisból decimálissá történő konverzión alapul). Miért van erre szükség, ha csak a %2-t használhatod? Az én számítógépemen például az &1 66%-kal gyorsabb. Elég jó teljesítménynövelés, mondom.
Az XOR és a bitenkénti VAGY közötti különbség az, hogy 1-es értékhez a párban csak egy bit lehet 1:
Például a 138^43 kifejezés a következő lenne...
| A | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
|---|---|---|---|---|---|---|---|---|
| B | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 |
| A^B | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
… 10100001 2 vagy 160 10
A ^-vel megváltoztathatja két változó értékét (azonos adattípussal) anélkül, hogy ideiglenes változót használna.
A szöveget XOR használatával is titkosíthatja. Ehhez csak ismételnie kell az összes karaktert, és ^ őket a kulcskarakterrel. Bonyolultabb titkosításhoz használhat karakterláncot:
String msg = "Ez egy üzenet"; char message = msg.toCharArray(); String key = ".*)"; String encryptedString = new String(); for(int i = 0; i< message.length; i++){ encryptedString += message[i]^key.toCharArray(); }
XOR nem a legtöbb megbízható módon titkosítás, de a titkosítási algoritmus részévé tehető.
A bitenkénti negáció az operandus összes bitjét megfordítja. Vagyis ami 1 volt, az 0 lesz, és fordítva.
Itt például a ~52 művelet:
| A | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|---|---|---|---|
| ~A | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 |
Az eredmény 203 10 lesz
Bitenkénti negáció használatakor az eredmény előjele mindig ellentétes lesz az eredeti szám előjelével (előjeles számokkal dolgozva). Miért történik ez, most megtudhatja.
Itt szeretnék egy kicsit mesélni a negatív egész számok számítógépekben való ábrázolásáról, nevezetesen a kettő komplementeréről. Anélkül, hogy belemennénk a részletekbe, szükség van rá, hogy megkönnyítse a kettes számok aritmetikáját.
A legfontosabb dolog, amit tudnia kell a kettő komplementszámairól, hogy a legjelentősebb bit előjeles. Ha egyenlő 0-val, akkor a szám pozitív, és egybeesik ennek a számnak a közvetlen kódban való ábrázolásával, ha pedig 1, akkor negatív. Vagyis az 10111101 negatív, a 01000011 pedig pozitív.
Ahhoz, hogy egy negatív számot kettős komplementerré alakítsunk át, a szám összes bitjét meg kell invertálni (vagyis bitenkénti negációt kell használni), és az eredményhez hozzá kell adni 1-et.
Például, ha 109-ünk van:
| A | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| ~A | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 |
| ~A+1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
A fenti módszerrel -109-et kapunk kettős komplementerben.
A kiegészítő kód nagyon leegyszerűsített magyarázatát most mutattuk be, és határozottan azt tanácsolom, hogy tanulmányozza ezt a témát részletesebben.
A bitenkénti eltolás kissé eltér a korábban tárgyalt bitenkénti műveletektől. A bitenkénti balra eltolás az operandus N bit bitjeit balra tolja, a legkisebb jelentőségű bittől kezdve. A műszak utáni üres helyeket nullák töltik ki. Ez így történik:
| A | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 |
|---|---|---|---|---|---|---|---|---|
| A<<2 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
Az N pozícióval balra való eltolás érdekes tulajdonsága, hogy ez egyenértékű egy szám 2 N-vel való szorzásával. Szóval 43<<4 == 43*Math.pow(2,4) . Использование сдвига влево вместо Math.pow обеспечит неплохой прирост производительности.
Ahogy azt sejteni lehetett, >> az operandus bitjeit meghatározott számú bittel jobbra tolja.
Ha az operandus pozitív, akkor az üres helyeket nullákkal töltjük ki. Ha kezdetben negatív számmal dolgozunk, akkor a bal oldali üres helyeket egységekkel töltjük ki. Ez a jel megőrzése érdekében történik a korábban ismertetett kiegészítő kód szerint.
Mivel a bitenkénti jobbra eltolás a bitenkénti balra tolódás ellentéte, könnyen kitalálható, hogy ha egy számot jobbra tolunk N számú pozícióval, akkor ez a szám 2 N-nel is elosztódik. Ez ismét sokkal gyorsabb, mint a normál felosztás.
Tehát most többet tud a bitműveletekről, és ne féljen tőlük. Úgy gondolom, hogy nem fogod használni a >>1-et minden alkalommal, amikor 2-vel osztod. A bitenkénti műveletek azonban jó, ha a tarsolyodban vannak, és most már használhatod őket, ha kell, vagy válaszolhatsz egy trükkös interjúkérdésre.
| Operátor | Szintaxis | Leírás |
| ÉS | A ÉS B | Konjunkció: Ha A-nak és B-nek van igazi érték, akkor - Igaz. Ellenkező esetben - Hamis |
| VAGY | A VAGY B | Diszjunkció: Ha bármelyik operandus igaz, akkor igaz. Ellenkező esetben - Hamis |
| NEM | NEM A | Tagadás: Ha A hamis, akkor igaz. Ellenkező esetben - Hamis |
| XOR | A XOR B | Kivétel: Ha A igaz vagy B igaz, akkor igaz. Ellenkező esetben - Hamis |
| EQV | A EQV B | Egyenértékűség: Ha A értéke megegyezik B-vel, akkor igaz. Ellenkező esetben - Hamis |
| MANÓ | A IMP B | Következmény: Ha A igaz és B hamis, akkor hamis. Különben – igaz |
A logikai operátor operandusaként bármilyen érvényes kifejezést használhat, amely logikai eredménnyel rendelkezik, valamint olyan számot, amely logikai értékké konvertálható.
Egy logikai művelet eredménye egy logikai típusú érték (vagy Null, ha legalább az egyik operandus nulla).
Szintaxis:
Operandus_1 ÉS Operandus_2
Az ÉS operátor végrehajtja logikai kötőszó.
A művelet eredménye csak akkor igaz, ha mindkét operandus igaz, egyébként pedig hamis.
igazságtáblázat
Az ÉS operátor több operandushoz is használható:
(5 3) ÉS (5=6) eredmény hamis
Az operandusok számától függetlenül a logikai ÉS művelet csak akkor ad igaz eredményt, ha a kifejezés minden operandusa igaz értékre van kiértékelve. Minden más esetben az eredmény hamis lesz. Vegye figyelembe, hogy az operandusok zárójelben vannak. A VBA először kiértékeli az egyes operandusok értékét a zárójelben, majd a teljes kifejezést.
Szintaxis:
Operandus_1 VAGY Operandus_2
A VAGY operátor végrehajtja logikai diszjunkció.
A művelet eredménye igaz, ha legalább az egyik operandus igaz, egyébként pedig hamis.
igazságtáblázat
Az OR operátor több operandushoz is használható:
(5 3) VAGY (5=6) eredmény igaz
Az operandusok számától függetlenül a logikai VAGY művelet eredménye mindig igaz lesz, ha a kifejezés legalább egyik operandusa igazra értékeli. Ellenkező esetben az eredmény hamis lesz.
Az ÉS és VAGY operátorok kombinálhatók:
((5 3)) VAGY (5=6) eredmény igaz
Szintaxis:
NEM operandus
A NOT operátor igen logikai tagadás.
A NOT operátor csak egy operandust használ.
igazságtáblázat
Az ÉS VAGY NEM operátorok kombinálhatók:
((5 3)) VAGY NEM (5=6) eredmény igaz
Szintaxis:
Operandus_1 XOR Operandus_2
Az XOR operátor végrehajtja logikai kivétel.
Ennek a műveletnek az eredménye True, ha az operandusok eltérő értékekkel rendelkeznek, egyébként pedig False.
igazságtáblázat
((5 3)) VAGY NEM (5=6) XOR (5=5) eredmény hamis
Szintaxis:
Operandus_1 EQV Operandus_2
Az EQV operátor az operátor logikai egyenértékűség.
Ennek a műveletnek az eredménye igaz, ha az operandusok értéke megegyezik, ellenkező esetben False.
igazságtáblázat
((5 3)) VAGY NEM (5=6) EQV (5=5) eredmény igaz
Szintaxis:
Operandus_1 IMP Operandus_2
Az IMP utasítás logikai műveletet hajt végre következményei.
igazságtáblázat
((5 3)) VAGY NEM (5=6) IMP (5=5) eredmény igaz
Az IMP logikai operátor a legkevésbé intuitív az összes közül logikai operátorok. Szerencsére használatának igénye meglehetősen ritkán merül fel.
A "vagy ... vagy ..." beszédfigurával jelölve Az "A vagy B" összetett állítás akkor tekinthető igaznak, ha A vagy B igaz, de nem mindkettő egyszerre; ellenkező esetben az összetett állítás hamis.
Azok. az eredmény igaz (egyenlő 1-gyel), Ha A nem egyenlő B-vel (A≠B).
Ezt a műveletet gyakran a diszjunkcióhoz hasonlítják, mert nagyon hasonló tulajdonságokkal rendelkeznek, és mindkettő hasonló a mindennapi beszéd "vagy" uniójához. Hasonlítsa össze az alábbi műveletek szabályait:
1. igaz ha igaz vagy , vagy mindkettőt egyszerre.
2. igaz ha igaz vagy, De Nem mindkettőt egyszerre.
Művelet kizárja az utolsó lehetőség („mindkettő egyszerre”), és emiatt kizárólagos „VAGY”-nak hívják. Kétértelműség a természetes nyelv az, hogy a „vagy” unió mindkét esetben használható.
5. Implikáció (logikai következmény) két állítás egybevonásával jön létre a "ha ..., akkor ...." beszédfigura használatával.
Belépés: A®B
Az implikáció műveletével alkotott összetett állítás akkor és csak akkor hamis, ha egy igaz premisszából (az első állításból) hamis következtetés következik (a második állítás).
Azok. ha 1 0-t jelent, akkor az eredmény 0, ellenkező esetben 1.
Például a „Ha egy szám osztható 10-zel, akkor osztható 5-tel” állítás igaz, mert az első és a második állítás is igaz.
A "Ha egy szám osztható 10-zel, akkor osztható 3-mal" állítás hamis, mert hamis következtetést vonunk le egy igaz premisszából.
"Ez a négyszög egy négyzet" (A) És "Egy adott négyszög köré kör írható" (BAN BEN). Ezután az összetett utasítás így szól "Ha az adott négyszög négyzet, akkor körbeírható."
A hétköznapi beszédben a link "ha akkor" az állítások közötti ok-okozati összefüggést írja le. De a logikai műveleteknél az állítások jelentését nem veszik figyelembe. Csak azok igazságát vagy hamisságát veszik figyelembe. Ezért nem szabad zavarba hozni a tartalmilag teljesen független kijelentések implikációinak "értelmetlenségét". Például így: "Ha az Egyesült Államok elnöke demokrata, akkor Afrikában vannak zsiráfok", "Ha a görögdinnye bogyó, akkor a benzinkútban van benzin."
6. Az ekvivalenciát (logikai egyenlőség, ~ º Û) úgy alakítjuk ki, hogy két állítást egyesítünk a „...ha és csak ha...” beszédfigura segítségével.
Az ekvivalencia-művelettel alkotott összetett állítás akkor és csak akkor igaz, ha mindkét állítás egyszerre hamis vagy igaz.
Például a "A számítógép akkor és csak akkor tud számításokat végezni, ha be van kapcsolva" és "A számítógép nem tud számításokat végezni, ha és csak akkor, ha nincs bekapcsolva" igazak, mivel mindkét egyszerű állítás egyszerre igaz.
igazságtáblázatok
Minden összetett állításhoz (logikai függvényhez) fel lehet építeni egy igazságtáblázatot, amely meghatározza annak igazságát vagy hamisságát az egyszerű állítások kezdeti értékeinek összes lehetséges kombinációjára.
igazságtáblázat egy logikai áramkör (művelet) táblázatos ábrázolása, amely felsorolja az igazságértékek összes lehetséges kombinációját bemeneti jelek(operandusok) a kimeneti jel (a művelet eredménye) igazságértékével együtt ezekre a kombinációkra vonatkozóan.
A fenti logikai műveleteket tükrözzük az igazságtáblázatban:
Az állítások algebrájában minden logikai függvény logikai transzformációkkal redukálható három alapvetőre: logikai összeadásra, logikai szorzásra és logikai tagadásra.
Bizonyítsuk be, hogy az A®B műveletimplikáció ekvivalens a logikai kifejezéssel:
Az egyrétegű perceptronok korlátozott képességeinek bemutatása érdekében gyakran az ún. probléma mérlegeléséhez folyamodnak. XOR – Exkluzív VAGY.
A probléma lényege a következő. Az XOR logikai függvény adott - kizárólagos VAGY. Ez két argumentum függvénye, amelyek mindegyike lehet nulla vagy egy. Akkor veszi fel az értéket, ha az egyik argumentum egyenlő eggyel, de nem mindkettő, ellenkező esetben. A probléma az alábbi ábrán látható egyrétegű, egyneuronos, kétbemenetes rendszerrel szemléltethető.
Jelölje az egyik bemenetet -vel, a másikat pedig -vel, akkor ezek összes lehetséges kombinációja négy pontból áll majd a síkon. Az alábbi táblázat a bemenetek és a kimenetek közötti szükséges kapcsolatot mutatja, ahol a nulla kimenetet eredményező bemeneti kombinációk címkével, az egyetlen kimenet pedig címkével vannak ellátva.
| pontokat | Jelentése | Jelentése | Szükséges kimenet |
| 0 | 0 | 0 | |
| 1 | 0 | 1 | |
| 0 | 1 | 1 | |
| 1 | 1 | 0 |
Egy idegsejt két bemenettel tetszőleges egyenes formájában döntési felületet alkothat. Ahhoz, hogy a hálózat megvalósítsa a fenti táblázatban megadott XOR függvényt, úgy kell elhelyezni az egyenest, hogy a pontok a vonal egyik oldalán, a pontok pedig a másik oldalon legyenek. Ha megpróbálunk ilyen egyenes vonalat húzni az alábbi ábrán, meg vagyunk győződve arról, hogy ez lehetetlen. Ez azt jelenti, hogy függetlenül attól, hogy milyen értékek vannak hozzárendelve a súlyokhoz és a küszöbértékekhez, az egyrétegű neurális hálózat nem képes reprodukálni az XOR függvény megjelenítéséhez szükséges bemenet-kimenet kapcsolatot.
Az XOR függvény azonban könnyen kialakítható kétrétegű hálózattal, és sokféleképpen. Tekintsük az egyik módot. Modernizáljuk az ábrán látható hálózatot egy újabb rejtett neuronréteg hozzáadásával:
Vegye figyelembe, hogy ezt a hálózatotúgy adva, ahogy van, azaz. feltételezhető, hogy már kiképzett. A nyilak feletti számok a szinaptikus súlyok értékeit mutatják. Aktiválási függvényként az egységugrás függvényt használjuk a küszöbértékkel, amelynek a következő grafikonja van:
Ekkor egy ilyen neurális hálózat működésének eredménye a következő táblázatban ábrázolható:
| pontokat | Jelentése | Jelentése | Szükséges kimenet | |||
| 0 | 0 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 1 | 1 | 0 | 1 | |
| 0 | 1 | 1 | 0 | 1 | 1 | |
| 1 | 1 | 0 | 0 | 0 | 0 |
Az első réteg két neuronja tetszőleges egyenes formájában döntési felületet alkot (a síkot két félsíkra osztja), a kimeneti réteg neuronja pedig ezt a két megoldást egyesíti, döntési felületet alkotva a az első réteg neuronjainak párhuzamos egyenesei által alkotott csík alakja:
A cikkben az XOR probléma megoldására használt neurális hálózat primitív, és nem használja a többrétegű hálózatok összes funkcióját. Nyilván többrétegű neurális hálózatok nagyobb reprezentációs erejük van, mint az egyrétegűeknek, csak a nemlinearitás megléte esetén. És ebben a hálózatban egy küszöbérték lineáris aktiválási funkciót alkalmaznak. Egy ilyen hálózat nem tanítható például a visszaterjesztési algoritmus alkalmazásával.
A gyakorlatban leggyakrabban kétbemenetes XOR elemeket használnak. ábrán. 1. feltételes grafikai megjelölés inverzió nélküli elem és állapottáblázata. Egyszerűen fogalmazva ennek az elemnek a lényege a következő, a kimeneti jel csak akkor jelenik meg, ha a logikai szintek a bemeneteken nem azonosak.
Ebben az áramkörben három XOR elemet használnak az impulzusok késleltetésére. DD1.4 - összegzés. A kimeneti impulzusok stabil felfutó és lefutó élekkel rendelkeznek. Az egyes kimeneti impulzusok időtartama a három elem mindegyikének kapcsolási késleltetési idejének háromszorosa. A kimeneti impulzusok frontja közötti időintervallum megegyezik a bemeneti impulzus időtartamával. Ez az eszköz a bemeneti jel frekvenciáját is megduplázza.
Van még egy érdekes ingatlan "XOR". Ha az egyik bemenetre állandó „0” kerül, akkor az elem kimenetén lévő jel megismétli a bemeneti jelet, ha pedig az állandó „0” állandó „1”-re változik, akkor a kimeneti jel már a bemenet inverziója.
Néha szükségessé válik egy XOR elem beszerzése különálló szabványos logikai elemekből. Példa erre a négy 2-AND-NOT elemen megvalósított XOR elem áramkör. A 3. ábra az XOR áramkört mutatja négy állapotában. Ez az összes lehetséges logikai szintet mutatja az egyes használt 2-NAND kapukon.
Az ilyen elemek szerepelnek a rendszerben. Ebben az áramkörben az XOR elem a K561LA7 mikroáramkör egyik házában található négy 2-AND-NOT elemen készül.
Az alakító áramkör a 4. ábrán látható. Itt az XOR logikai elem négy 2-AND-NOT elemen is megvalósul.
Az alakformáló 1. és 2. bemenetére négyszögletes impulzusok esnek (lásd 1. és 2. grafikon), amelyek ismétlési arányban különböznek egymástól. A DD1.1-DDI.4 logikai elemek csomópontja megszorozza ezeket a jeleket. A DD1.4 elemből a kimenő impulzusjel (3. grafikon) az R3, C1 integráló áramkörbe kerül, amely a bemeneti jelek frekvenciakülönbségével megegyező frekvenciájú háromszögjellé (4. grafikon) alakítja át, és a A DA1 műveleti erősítő a vett jelet meanderré alakítja (lásd az 5. ábrát). Az R1 ellenállás szabályozza a kimeneti jel pozitív és negatív félhullámának időtartamát. Nagyon érdekes séma. Rádiótervező, van min gondolkodni. Például a harmadik grafikonon látható jel egy PWM szinuszos jel.
Természetesen az XOR elemek felhasználási köre sokkal szélesebb. Véleményem szerint a rádióamatőrök számára érdekesebbet hoztam ide.
