Binárna aritmetika

Názov parametra	Význam
Téma článku:	Binárna aritmetika
Rubrika (tematická kategória)	Počítačová veda

Binárny číselný systém

Číselné sústavy používané pri práci s počítačom

Základ P = 2. Abeceda obsahuje dve binárne číslice: 0, 1. Ľubovoľné číslo C = C n C n-1 ...C 1 C 0 C -1 C -m je súčet mocnin čísla P = 2 ,

C = Cn × 2 n + C n-1 × 2 n-1 +…+C 1 × 2 1 +C 0 × 2 0 +C -1 × 2 -1 +…+C -m × 2 -m

Príklad 3.6.

101011.11 2 = 1×2 5 + 0×2 4 + 1×2 3 + 0×2 2 +1×2 1 + 1×2 0 +1×2 -1 + 1×2 -2 = 32+8 +2 +1+0,5+0,25=43,75 10.

Váhy číslic v binárnej číselnej sústave sú 1, 4, 8,16,... naľavo od desatinnej čiarky a 0,5; 0,25; 0,125; 0,625;... napravo od desatinnej čiarky.

Niekedy sa používa pri programovaní hexadecimálny notový zápis. Na znázornenie čísel väčších ako 9 v systéme hexadecimálnych čísel sa používajú latinské písmená A, B, C, D, E, F. Obrázky prvých šestnástich čísel v desiatkovej, binárnej a šestnástkovej sústave sú uvedené v tabuľke. 2.

Tabuľka kódov v rôzne systémy mŕtve zúčtovanie

tabuľka 2

Desatinná sústava	Binárny systém	Hexadecimálny systém	Desatinná sústava	Binárny systém	Hexadecimálny systém
					A
					B
					C
					D
					E
					F

Binárne desiatkové čísloČíselná sústava sa v moderných počítačoch rozšírila vďaka ľahkému prevodu na desiatkovú sústavu a naopak. Používa sa tam, kde sa hlavná pozornosť nevenuje jednoduchosti technickej konštrukcie stroja, ale pohodliu užívateľa. V tomto číselnom systéme sú všetky desatinné číslice oddelene zakódované štyrmi binárnymi číslicami.

Príklad 3.7.

Desatinné číslo 9703 v BCD vyzerá takto: 1001 0111 0000 0011.

Výhoda dvojkovej číselnej sústavy oproti desiatkovej číselnej sústave z pohľadu číslicového počítača je nasledovná:

• sú potrebné prvky s dvoma stabilnými stavmi;
• aritmetické operácie sú výrazne zjednodušené;
• Vyžaduje sa 1,5-krát menej vybavenia;
• umožňuje použiť prístroj matematickej logiky na analýzu a syntézu obvodov.

Nevýhody binárneho číselného systému sú nasledovné:

• dĺžka záznamu veľkého počtu;
• Pri zadávaní a výstupe informácií je potrebná konverzia do systému desiatkových čísel.

Pozrime sa, ako sa vykonávajú základné operácie v binárnej aritmetike.

Pravidlá aritmetiky vo všetkých pozičných číselných sústavách sú rovnaké, ᴛ.ᴇ. sčítanie, násobenie a odčítanie začínajú od najnižších číslic, delenie - od najvyšších.

Pri pridávaní sa nosná jednotka pripočítava k číslicam susednej najvýznamnejšej číslice. Po odpočítaní jednotka pôžičky na najvyššej číslici dáva dve jednotky na najnižšej susednej číslici.

Príklad 3.8

Násobenie binárnych čísel je podobné ako násobenie desiatkových čísel, ale... Ak násobíme iba 0 a 1, násobenie sa zredukuje na operáciu posunu a sčítania.

Príklad 3.9

Binárna aritmetika - pojem a typy. Klasifikácia a vlastnosti kategórie "Binárna aritmetika" 2017, 2018.

- Binárna aritmetika

Pretože informačných procesov V digitálnych systémov nadobúdať hodnoty iba 0 a 1, potom sa reprezentácia údajov vykonáva pomocou binárnych čísel. Sčítanie a odčítanie binárnych čísel, ako aj všetky ostatné aritmetické operácie sa vykonávajú podľa rovnakých pravidiel ako... .

- Binárna číselná sústava a binárna aritmetika

V dvojkovej číselnej sústave môžete s číslami vykonávať rovnaké operácie ako v desiatkovej číselnej sústave. Sčítanie sa vykonáva na rovnakom princípe ako v desiatkovej číselnej sústave: iba ak z danej číslice vznikne množstvo, ktoré sa do nej nezmestí, potom...

, Súťaž „Prezentácia na lekciu“

Prezentácia na lekciu

Späť dopredu

Pozor! Náhľad Snímky slúžia len na informačné účely a nemusia predstavovať všetky funkcie prezentácie. Ak máš záujem táto práca, stiahnite si plnú verziu.

Ciele lekcie: (snímka 2)

1. Oboznámiť žiakov s binárnou číselnou sústavou.
2. Rozvíjať zručnosti pri vykonávaní aritmetických operácií s binárnymi číslami

Počas vyučovania

I. Začiatok hodiny

Učiteľ: Aby ste lepšie zvládli systém binárnych čísel, musíte zvládnuť vykonávanie aritmetických operácií s binárnymi číslami.

Všetky pozičné číselné systémy sú „rovnaké“, konkrétne vo všetkých sa aritmetické operácie vykonávajú podľa rovnakých pravidiel:

• platia rovnaké aritmetické zákony: komutatívny, asociačný, distributívny;
• platia pravidlá sčítania, odčítania, násobenia a delenia;
• Pravidlá pre vykonávanie aritmetických operácií sú založené na sčítacích a násobiacich tabuľkách.

Pozrime sa na pravidlá vykonávania aritmetických operácií

II. Učenie sa nového materiálu

Pri delení podľa stĺpca musíte vykonať násobenie a odčítanie ako medzivýsledky. Ale v binárnom číselnom systéme sú medzinásobenia redukované na násobenie deliteľa buď 0 alebo 1, takže najťažšou operáciou zostáva odčítanie, ktoré sa musíte naučiť robiť presne.

III. Upevnenie toho, čo sa naučilo. (snímka 12)

Chlapci robia prácu svojpomocne. Potom otvorte snímku s odpoveďami.

Odpovede. (Snímka 13)

IV. Domáca úloha (snímka 14)

1. Naučte sa pravidlá pre vykonávanie aritmetických operácií v dvojkovej číselnej sústave.

2. Postupujte podľa týchto krokov:

1. 110010+11,01
2. 1111001-1101
3. 10101,1*11
4. 10101110:101

Domov \ Dokumentácia \ Pre učiteľa informatiky

Pri použití materiálov z tejto stránky - a umiestnenie banneru je POVINNÉ!!!

Binárna aritmetika

Čísla, ktoré sme zvyknutí používať, sa nazývajú desiatkové a aritmetika, ktorú používame, sa nazýva aj desiatkové. Každé číslo sa totiž môže skladať zo sady čísiel obsahujúcich 10 znakov – číslic – „0123456789“.

Matematika sa vyvinula tak, že táto konkrétna množina sa stala hlavnou, ale desiatková aritmetika nie je jediná. Ak vezmeme iba päť číslic, potom na ich základe môžeme zostaviť päťcifernú aritmetiku a zo siedmich číslic sedemcifernú aritmetiku. V oblastiach vedomostí súvisiacich s počítačové vybavenieČasto sa používa aritmetika, v ktorej čísla pozostávajú zo šestnástich číslic; podľa toho sa táto aritmetika nazýva hexadecimálna. Aby sme pochopili, čo je číslo v desiatkovej aritmetike, najprv zistíme, čo je číslo v desiatkovej aritmetike.

Vezmite si napríklad číslo 246. Tento zápis znamená, že v čísle sú dve stovky, štyri desiatky a šesť jednotiek. Preto môžeme napísať nasledujúcu rovnosť:

246 = 200 + 40 + 6 = 2 * 10 2 + 4 * 10 1 + 6 * 10 0

Znamienko rovnosti oddeľuje tri spôsoby zápisu toho istého čísla. Teraz je pre nás najzaujímavejšia tretia forma zápisu: 2 * 10 2 + 4 * 10 1 + 6 * 10 0 . Je štruktúrovaný nasledovne:

Naše číslo má tri číslice. Vedúca číslica "2" je číslo 3. Takže sa vynásobí 10 na druhú mocninu. Ďalšia číslica „4“ má poradové číslo 2 a v prvej sa vynásobí 10. Už je jasné, že číslice sa násobia desiatimi na mocninu o jednu menej, ako je poradové číslo číslice. Po pochopení vyššie uvedeného si môžeme zapísať všeobecný vzorec na vyjadrenie desatinného čísla. Dajme číslo s N číslicami. Budeme označovať i-tá číslica cez i. Potom možno číslo zapísať v nasledujúcom tvare: a n a n-1 ....a 2 a 1 . Toto je prvý formulár a tretí vstupný formulár bude vyzerať takto:

a n a n-1 ....a 2 a 1 = a n * 10 n-1 + a n-1 * 10 n-2 + .... + a 2 * 10 1 + a 1 * 10 0

kde a i je znak z množiny "0123456789"

Úloha desiatky je na tejto nahrávke veľmi jasne viditeľná. Desať je základom pre tvorbu čísel. A mimochodom, nazýva sa to „základ číselného systému“ a samotný číselný systém je dôvod, prečo sa nazýva „desiatkový“. Samozrejme, že číslo desať nemá žiadne špeciálne vlastnosti. Desiatku môžeme jednoducho nahradiť ľubovoľným iným číslom. Napríklad číslo v päťmiestnej číselnej sústave možno zapísať takto:

a n a n-1 ....a 2 a 1 = a n * 5 n-1 + a n-1 * 5 n-2 + .... + a 2 * 5 1 + a 1 * 5 0

kde a i je znak z množiny "01234"

Vo všeobecnosti nahradíme 10 akýmkoľvek iným číslom a získame úplne inú číselnú sústavu a inú aritmetiku. Najjednoduchšia aritmetika sa získa, ak sa 10 nahradí 2. Výsledná číselná sústava sa nazýva binárna a číslo v nej je definované takto:

a n a n-1 ....a 2 a 1 = a n * 2 n-1 + a n-1 * 2 n-2 + .... + a 2 * 2 1 + a 1 * 2 0

kde a i je znak z množiny "01"

Tento systém je najjednoduchší zo všetkých možných, keďže v ňom je každé číslo tvorené len z dvoch číslic 0 a 1. Je jasné, že jednoduchší už ani nemôže byť. Príklady binárnych čísel: 10, 111, 101.

Veľmi dôležitá otázka. Je možné reprezentovať binárne číslo ako desiatkové číslo a naopak? desatinné číslo reprezentujú ho v binárnej forme.

Binárne na desiatkové. Je to veľmi jednoduché. Spôsob takéhoto prekladu je daný naším spôsobom zápisu čísel. Vezmime si napríklad nasledujúce dvojkové číslo 1011. Rozviňme ho na mocniny dvojky. Získame nasledovné:

1011 = 1 * 2 3 + 0 * 2 2 + 1 * 2 1 + 1 * 2 0

Vykonajte všetky zaznamenané akcie a získajte:

1 * 2 3 + 0 * 2 2 + 1 * 2 1 + 1 * 2 0 = 8 + 0+ 2 + 1 = 11. Dostaneme teda, že 1011 (binárne) = 11 (desiatkové). Mierna nepríjemnosť binárneho systému je okamžite viditeľná. Rovnaké číslo, ktoré je zapísané v desiatkovej sústave jednou číslicou v dvojkovej sústave, potrebuje na svoj zápis štyri číslice. Ale toto je cena za jednoduchosť (nič nie je zadarmo). Binárny systém však poskytuje obrovský zisk v aritmetických operáciách. A to uvidíme neskôr.

Vyjadrite nasledujúce binárne čísla ako desatinné.

a) 10010 b) 11101 c) 1010 c) 1110 d) 100011 e) 1100111 f) 1001110

Sčítanie binárnych čísel.

Metóda sčítania stĺpcov je vo všeobecnosti rovnaká ako pre desatinné číslo. To znamená, že sčítanie sa vykonáva po bitoch, počnúc najmenej významnou číslicou. Ak je pri sčítaní dvoch číslic SÚČET väčší ako deväť, zapíše sa číslica = SÚČET - 10 a CELÁ ČASŤ (SÚČET / 10) sa pripočíta ako najvýznamnejšia číslica. (Pridajte niekoľko čísel do stĺpca, nezabudnite, ako sa to robí.) To isté s binárnym číslom. Pridajte jeden po druhom, počnúc najnižšou číslicou. Ak je výsledok väčší ako 1, zapíše sa 1 a k najvýznamnejšej číslici sa pridá 1 (hovorí sa „z hlavy“).

Urobme príklad: 10011 + 10001.

Prvá kategória: 1+1 = 2. Píšeme 0 a 1, ako nás napadne.

Druhá kategória: 1+0+1 (zapamätaná jednotka) =2. Zapisujeme si 0 a 1, prišlo na um.

Tretia kategória: 0+0+1 (zapamätaná jednotka) = 1. Napíšte 1.

Štvrtá kategória 0+0=0. Píšeme 0.

Piata kategória 1+1=2. Zapíšeme 0 a pripočítame 1 k šiestej číslici.

Prevedieme všetky tri čísla do desiatkovej sústavy a skontrolujeme správnosť sčítania.

10011 = 1*2 4 + 0*2 3 + 0*2 2 + 1*2 1 + 1*2 0 = 16 + 2 + 1 =19

10001 = 1*2 4 + 0*2 3 + 0*2 2 + 0*2 1 + 1*2 0 = 16 + 1 = 17

100100 = 1*2 5 + 0*2 4 + 0*2 3 + 1*2 2 + 0*2 1 + 0*2 0 =32+4=36

17 + 19 = 36 správna rovnosť

Príklady nezávislých riešení:

a) 11 001 + 101 =

b) 11001 +11001 =

c) 1001 + 111 =

e) 10 011 + 101 =

e) 11011 + 1111 =

e) 11111 + 10011 =

Ako previesť desiatkové číslo na binárne. Ďalšou operáciou je odčítanie. Ale touto operáciou sa budeme zaoberať o niečo neskôr a teraz zvážime metódu prevodu desatinného čísla na binárne.

Aby bolo možné previesť desiatkové číslo na binárne, musí byť rozšírené na mocniny dvoch. Ale ak sa rozšírenie v mocninách desať dosiahne okamžite, potom to, ako expandovať v mocninách dvoch, vyžaduje trochu premýšľania. Najprv sa pozrime, ako to urobiť pomocou metódy výberu. Zoberme si desatinné číslo 12.

Krok jedna. 2 2 = 4, to nestačí. Tiež 2 3 = 8 nestačí, ale 2 4 = 16 je už veľa. Preto necháme 2 3 =8. 12 - 8 = 4. Teraz to musíte vyjadriť ako mocninu dvoch 4.

Krok dva. 4 = 22.

Potom je naše číslo 12 = 2 3 + 2 2. Najvyššia číslica má číslo 4, najvyšší stupeň = 3, preto musia existovať členy s mocninami dvoch 1 a 0. Tie však nepotrebujeme, aby sme sa zbavili nepotrebných stupňov a nechali potrebné , zapíšeme číslo takto: 1*2 3 + 1* 2 2 +0*2 1 + 0*2 0 = 1100 - toto je binárne vyjadrenie čísla 12. Je ľahké si všimnúť, že každá nasledujúca mocnina je najväčšia mocnina dvojky, ktorá je menšia ako rozkladové číslo. Na konsolidáciu metódy sa pozrime na ďalší príklad. Číslo 23.

Krok 1. Najbližšia mocnina dvoch je 2 4 = 16. 23 -16 = 7.

Krok 2. Najbližšia mocnina dvoch 2 2 = 4. 7 - 4 = 3

Krok 3. Najbližšia mocnina dvoch 2 1 = 2. 3 - 2 = 1

Krok 4. Najbližšia mocnina dvoch 2 0 =1 1 - 1 =0

Dostaneme nasledujúce rozšírenie: 1*2 4 + 0*2 3 +1*2 2 +1*2 1 +1*2 0

A naše požadované binárne číslo je 10111

Vyššie diskutovaná metóda dobre rieši problém, ktorý jej bol pridelený, ale existuje metóda, ktorá je algoritmizovaná oveľa lepšie. Algoritmus pre túto metódu je napísaný nižšie:

Ak je ČÍSLO väčšie ako nula, urobte to

NEXT DIGIT = zvyšok ČÍSLA delený 2

NUMBER = celá časť čísla NUMBER delená 2

Keď tento algoritmus dokončí svoju prácu, postupnosť vypočítaných NEXT DIGITS bude predstavovať binárne číslo. Pracujme napríklad s číslom 19.

Začiatok algoritmu ČÍSLO = 19

ĎALŠIA ČÍSLICA = 1

ĎALŠIA ČÍSLICA = 1

ĎALŠIA ČÍSLICA = 0

ĎALŠIA ČÍSLICA = 0

ĎALŠIA ČÍSLICA = 1

V dôsledku toho máme nasledujúce číslo 10011. Všimnite si, že dve diskutované metódy sa líšia v poradí, v ktorom sa získajú ďalšie číslice. Pri prvom spôsobe je prvá prijatá číslica najvýznamnejšou číslicou binárneho čísla a pri druhom spôsobe je prvá prijatá číslica, naopak, najmenej významná.

Preveďte desatinné čísla na binárne dvoma spôsobmi

a) 14 b) 29 c) 134 d) 158 f) 1190 g) 2019

Ako previesť zlomok na desatinné číslo.

Je známe, že každé racionálne číslo môže byť reprezentované ako desatinný a obyčajný zlomok. Obyčajný zlomok, teda zlomok tvaru A/B, môže byť pravidelný a nesprávny. Zlomok sa nazýva vlastný, ak A<В и неправильной если А>IN.

Ak je racionálne číslo reprezentované nesprávnym zlomkom a čitateľ zlomku je delený menovateľom celkom, potom je toto racionálne číslo celé číslo, vo všetkých ostatných prípadoch sa objaví zlomková časť. Zlomková časť je často veľmi dlhé číslo a dokonca nekonečné (nekonečný periodický zlomok, napríklad 20/6), takže v prípade zlomkovej časti nemáme za úlohu len preložiť jednu reprezentáciu do druhej, ale preložiť pomocou určitú presnosť.

Pravidlo presnosti. Predpokladajme, že ste dostali desatinné číslo, ktoré možno znázorniť ako desatinný zlomok s presnosťou na N číslic. Aby bolo zodpovedajúce binárne číslo rovnako presné, je potrebné doň napísať znamienka M, aby

Teraz sa pokúsme získať pravidlo prekladu a najprv sa pozrime na príklad 5 401

Riešenie:

Celú časť získame podľa nám už známych pravidiel a rovná sa binárnemu číslu 101. A zlomkovú časť rozšírime o mocniny 2.

Krok 1: 2-2 = 0,25; 0,401 - 0,25 = 0,151. - toto je zvyšok.

Krok 2: Teraz musíme reprezentovať 0,151 ako mocninu dvoch. Urobme toto: 2 -3 = 0,125; 0,151 - 0,125 = 0,026

Pôvodná zlomková časť teda môže byť reprezentovaná ako 2 -2 +2 -3. To isté možno zapísať do tohto binárneho čísla: 0,011. Prvá zlomková číslica je nula, pretože v našom rozšírení neexistuje mocnina 2 -1.

Z prvého a druhého kroku je jasné, že toto znázornenie nie je presné a môže byť žiaduce pokračovať v rozširovaní. Pozrime sa na pravidlo. Hovorí, že potrebujeme toľko znakov M, že 10 3 je menej ako 2 M. To znamená 1000<2 M . То есть в двоичном разложении у нас должно быть не менее десяти знаков, так как 2 9 = 512 и только 2 10 = 1024. Продолжим процесс.

Krok 3: Teraz pracujeme s číslom 0,026. Najbližšia mocnina dvojky k tomuto číslu je 2 -6 = 0,015625; 0,026 - 0,015625 = 0,010375 Teraz je naše presnejšie binárne číslo: 0,011001. Za desatinnou čiarkou je už šesť miest, ale to je ešte málo, takže robíme ešte jeden krok.

Krok 4: Teraz pracujeme s číslom 0,010375. Najbližšia mocnina dvojky k tomuto číslu je 2 -7 = 0,0078125;

0,010375 - 0,0078125 = 0,0025625

Krok 5: Teraz pracujeme s číslom 0,0025625. Najbližšia mocnina dvojky k tomuto číslu je 2 -9 = 0,001953125;

0,0025625 - 0,001953125 = 0,000609375

Posledný výsledný zvyšok je menší ako 2 -10 a ak by sme chceli pokračovať v aproximácii pôvodného čísla, potrebovali by sme 2 -11, čo však už presahuje požadovanú presnosť, a preto je možné výpočty zastaviť a výslednú binárnu reprezentáciu zlomkovú časť možno zapísať.

0,401 = 0,011001101

Ako vidíte, prevod zlomkovej časti desatinného čísla na binárne je o niečo zložitejší ako prevod celej časti. Tabuľka mocnin dvojky na konci prednášky.

Teraz si zapíšme algoritmus konverzie:

Počiatočné údaje algoritmu: Prostredníctvom A budeme označovať pôvodný správny desatinný zlomok zapísaný v desatinnom tvare. Nech tento zlomok obsahuje N znakov.

Algoritmus

Činnosť 1. Určte počet požadovaných dvojkových číslic M z nerovnosti 10 N< 2 M

Činnosť 2: Cyklus na výpočet číslic binárnej reprezentácie (číslice po nule). Číselné číslo bude označené symbolom K.

1. Číselné číslo = 1
2. Ak 2-K > A

Potom k binárnemu číslu pridáme nulu

• pridajte 1 k binárnemu číslu
• A = A-2-K

1. K = K + 1
2. Ak K > M

• potom je algoritmus dokončený
• V opačnom prípade prejdite na bod 2.

Previesť desatinné čísla na binárne

a) 3,6 b) 12,0112 c) 0,231 d) 0,121 d) 23,0091

Odčítanie binárnych čísel. Odčítať budeme aj čísla v stĺpci a všeobecné pravidlo je rovnaké ako pri desatinných číslach, odčítanie sa vykonáva po bitoch a ak je na mieste málo, tak v najvyššom. Poďme vyriešiť nasledujúci príklad:

Prvá kategória. 1 - 0 = 1. Zapisujeme si 1.

Druhá kategória 0-1. Jeden chýba. Obsadzujeme ju v seniorskej kategórii. Jednotka z vyššej číslice prechádza do nižšej, ako sú dve jednotky (pretože horná číslica je reprezentovaná dvojkou vyššieho stupňa) 2-1 = 1. Zapisujeme si 1.

Tretia kategória. Obsadili sme jednotku tejto hodnosti, takže teraz v hodnosti 0 je potrebné obsadiť jednotku najvyššej hodnosti. 2-1 = 1. Zapisujeme si 1.

Výsledok skontrolujeme v desiatkovej sústave

1101 - 110 = 13 - 6 = 7 (111) Správna rovnosť.

Ďalší zaujímavý spôsob vykonávania odčítania zahŕňa koncept kódu dvojkového doplnku, ktorý vám umožňuje zredukovať odčítanie na sčítanie. Výsledok čísla v dvojkovom doplnkovom kóde je veľmi jednoduchý: vezmeme číslo, nuly nahradíme jednotkami, naopak, nahradíme jednotky nulami a k ​​najmenej významnej číslici pripočítame jednotku. Napríklad 10010, doplnkový kód bude 011011.

Pravidlo odčítania prostredníctvom dvojkového doplnku hovorí, že odčítanie môže byť nahradené sčítaním, ak je odpočet nahradený číslom v dvojkovom doplnku.

Príklad: 34 – 22 = 12

Napíšme tento príklad v binárnom tvare. 100010 – 10110 = 1100

Doplnkový kód čísla 10110 bude takýto

01001 + 00001 = 01010. Potom je možné pôvodný príklad nahradiť sčítaním takto: 100010 + 01010 = 101100 Ďalej je potrebné vyradiť jednu jednotku s najvýznamnejšou číslicou. Ak to urobíme, dostaneme 001100. Vyhoďme bezvýznamné nuly a dostaneme 1100, to znamená, že príklad bol vyriešený správne

Vykonajte odčítanie. Zvyčajným spôsobom a v dodatočnom kóde po predchádzajúcej konverzii desiatkových čísel na binárne:

Skontrolujte prevedením binárneho výsledku do desiatkovej číselnej sústavy.

Násobenie v dvojkovej číselnej sústave.

Najprv zvážte nasledujúci zaujímavý fakt. Na vynásobenie binárneho čísla 2 (desatinná dvojka je v dvojkovej sústave 10) stačí pridať jednu nulu naľavo od násobeného čísla.

Príklad. 10101 * 10 = 101010

Vyšetrenie.

10101 = 1*2 4 + 0*2 3 + 1*2 2 + 0*2 1 +1*2 0 = 16 + 4 + 1 = 21

101010 =1*2 5 + 0*2 4 + 1*2 3 + 0*2 2 +1*2 1 +0*2 0 = 32 + 8 + 2 = 42

Ak si spomenieme, že každé binárne číslo možno rozšíriť na mocniny dvoch, potom je jasné, že násobenie v systéme binárnych čísel sa redukuje na násobenie 10 (to znamená desatinnou čiarkou 2), a preto je násobenie sériou po sebe idúcich smeny. Všeobecným pravidlom je, že rovnako ako v prípade desiatkových čísel sa binárne násobenie vykonáva po bitoch. A za každú číslicu druhého násobiteľa sa napravo od prvého násobiteľa pridá jedna nula. Príklad (zatiaľ nie je v stĺpci):

1011 * 101 Toto násobenie možno zredukovať na súčet trojciferných násobení:

1011 * 1 + 1011 * 0 + 1011 * 100 = 1011 +101100 = 110111 To isté možno zapísať do stĺpca, ako je tento:

Vyšetrenie:

101 = 5 (desatinné)

1011 = 11 (desatinné)

110111 = 55 (desatinné)

5*11 = 55 správna rovnosť

Rozhodnite sa sami

a) 1101 * 1110 =

b) 1010 x 110 =

e) 101011 * 1101 =

e) 10 010 * 1 001 =

Poznámka: Mimochodom, tabuľka násobenia v binárnom systéme pozostáva iba z jednej položky 1 * 1 = 1

Delenie v dvojkovej číselnej sústave.

Pozreli sme sa už na tri akcie a myslím si, že už je jasné, že vo všeobecnosti sa akcie s binárnymi číslami líšia od akcií s desatinnými číslami. Jediný rozdiel je v tom, že sú tam dve čísla a nie desať, ale to len zjednodušuje aritmetické operácie. S delením je situácia rovnaká, ale pre lepšie pochopenie si algoritmus delenia rozoberieme podrobnejšie. Predpokladajme, že potrebujeme rozdeliť dve desatinné čísla, napríklad 234 delené 7. Ako to urobíme.

Vyberieme smerom doprava (od najvýznamnejšej číslice) taký počet číslic, aby výsledné číslo bolo čo najmenšie a zároveň väčšie ako deliteľ. 2 je menšie ako deliteľ, preto potrebujeme číslo 23. Výsledné číslo potom delíme deliteľom so zvyškom. Dostaneme nasledujúci výsledok:

Popísanú operáciu opakujeme, kým výsledný zvyšok nebude menší ako deliteľ. Keď sa to stane, číslo získané pod čiarou je kvocient a posledný zvyšok je zvyšok operácie. Takže operácia delenia binárneho čísla sa vykonáva presne rovnakým spôsobom. Vyskúšajme

Príklad: 10010111 / 101

Hľadáme číslo, ktorého prvá číslica je väčšia ako deliteľ. Ide o štvormiestne číslo 1001. Je zvýraznené tučným písmom. Teraz musíte nájsť deliteľa pre vybrané číslo. A tu opäť vyhrávame v porovnaní s desiatkovou sústavou. Faktom je, že vybraný deliteľ je nevyhnutne číslo a my máme iba dve čísla. Keďže 1001 je jednoznačne väčšie ako 101, potom je s deliteľom všetko jasné: 1. Vykonajte krok operácie.

Takže zvyšok dokončenej operácie je 100. To je menej ako 101, takže na vykonanie kroku druhého delenia musíte pridať ďalšiu číslicu k 100, toto je číslica 0. Teraz máme nasledujúce číslo:

1000 je väčšie ako 101, preto v druhom kroku opäť pripočítame k podielu číslo 1 a dostaneme nasledujúci výsledok (pre úsporu miesta hneď vynecháme ďalšiu číslicu).

Tretí krok. Výsledné číslo 110 je väčšie ako 101, preto v tomto kroku napíšeme do kvocientu 1. Dopadne to takto:

Výsledné číslo 11 je menšie ako 101, preto do podielu napíšeme číslo 0 a ďalšie číslo znížime nadol. Dopadá to takto:

Výsledné číslo je väčšie ako 101, preto do kvocientu zapíšeme číslo 1 a akcie vykonáme znova. Ukazuje sa tento obrázok:

1

0

Výsledný zvyšok 10 je menší ako 101, ale v dividende sa nám minuli číslice, takže 10 je konečný zvyšok a 1110 je požadovaný kvocient.

Pozrime sa na desatinné čísla

Toto uzatvára popis najjednoduchších aritmetických operácií, ktoré potrebujete vedieť, aby ste mohli používať binárnu aritmetiku, a teraz sa pokúsime odpovedať na otázku „Prečo je potrebná binárna aritmetika? Samozrejme, už vyššie sa ukázalo, že zápis čísla do dvojkovej sústavy výrazne zjednodušuje aritmetické operácie, no zároveň sa samotný záznam značne predĺži, čo znižuje hodnotu výsledného zjednodušenia, preto je potrebné hľadať napr. úlohy, ktorých riešenie je oveľa jednoduchšie v binárnych číslach.

Úloha 1: Získanie všetkých vzoriek

Veľmi často sa vyskytujú problémy, pri ktorých musíte byť schopní zostaviť všetky možné kombinácie z danej množiny objektov. Napríklad táto úloha:

Vzhľadom na veľkú hromadu kameňov usporiadajte kamene do dvoch kôp tak, aby hmotnosť týchto dvoch kôp bola čo najviac rovnaká.

Táto úloha môže byť formulovaná nasledovne:

Nájdite výber kameňov z veľkej kopy tak, aby sa ich celková hmotnosť čo najmenej líšila od polovice hmotnosti veľkej kopy.

Úloh tohto druhu je pomerne veľa. A všetky sa scvrkávajú, ako už bolo povedané, na schopnosť získať všetky možné kombinácie (ďalej ich budeme nazývať vzorky) z danej množiny prvkov. A teraz sa pozrieme na všeobecnú metódu získania všetkých možných vzoriek pomocou operácie binárneho sčítania. Začnime príkladom. Nech existuje súbor troch predmetov. Skonštruujme všetky možné vzorky. Predmety budeme označovať sériovými číslami. To znamená, že existujú nasledujúce položky: 1, 2, 3.

Vzorky: (0, 0, 1); (0, 1, 0); (0, 1, 1); (100); (1, 0, 1); (1, 1, 0); (1, 1, 1);

Ak je pozícia s nasledujúcim číslom jedna, znamená to, že prvok s číslom rovným tejto pozícii je prítomný vo výbere a ak je nula, prvok nie je prítomný. Napríklad vzorka (0, 1, 0); pozostáva z jedného prvku s číslom 2 a výber je (1, 1, 0); pozostáva z dvoch prvkov s číslami 1 a 2.

Tento príklad jasne ukazuje, že vzorka môže byť reprezentovaná ako binárne číslo. Okrem toho je ľahké vidieť, že všetky možné jedno, dvoj a trojmiestne binárne čísla sú napísané vyššie. Prepíšme ich takto:

001; 010; 011; 100; 101; 110; 111

1; 10; 11; 100; 101; 110; 111

Dostali sme sériu po sebe idúcich binárnych čísel, z ktorých každé sa získa z predchádzajúceho pridaním jedného. Môžete to skontrolovať. Pomocou tohto pozorovaného vzoru môžeme zostaviť nasledujúci algoritmus na získanie vzoriek.

Vstupné údaje algoritmu

Daný súbor objektov N - kusov. Ďalej budeme túto množinu nazývať množina počiatočných prvkov. Očíslujme všetky prvky pôvodnej množiny od 1 do N. Z N bezvýznamných núl urobme dvojkové číslo. 0000… 0 N Toto nulové binárne číslo bude označovať nulovú vzorku, s ktorou začne proces vzorkovania. Číslice čísla sa počítajú sprava doľava, to znamená, že číslica úplne vľavo je najvýznamnejšia.

Dohodnime sa, že toto binárne číslo budeme označovať veľkými písmenami BINARY

Algoritmus

Ak BINÁRNE číslo pozostáva výlučne z jednotiek

Potom algoritmus zastavíme

• Jedničku pripočítame k BINÁRNEMU číslu podľa pravidiel binárnej aritmetiky.
• Z výsledného BINARY čísla urobíme ďalšiu vzorku, ako je popísané vyššie.

Úloha 2: Nájdenie veľkých prvočísel

Na začiatok si pripomeňme, že prvočíslo je prirodzené číslo, ktoré je deliteľné iba 1 a sebou samým. Príklady prvočísel: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

Hľadanie veľkých prvočísel je veľmi dôležitý matematický problém. Veľké prvočísla sú potrebné pre niektoré šifrovacie algoritmy na bezpečné šifrovanie správ. Navyše sú potrebné nielen veľké počty, ale aj veľmi veľké. Čím väčšie číslo, tým spoľahlivejšia je šifra postavená na tomto čísle.

Poznámka. Silná šifra je šifra, ktorej rozlúštenie trvá veľmi dlho.

prečo? Prvočíslo funguje ako kľúč na šifrovanie a dešifrovanie. Okrem toho vieme, že v rade sa vyskytujú prvočísla prirodzené čísla nie príliš často. Medzi prvou tisíckou ich je pomerne veľa, potom ich počet začína rýchlo klesať. Ak teda vezmeme za kľúč nie veľmi veľké číslo, dešifrovač s pomocou ani nie veľmi veľkého, rýchly počítač sa k nemu budú môcť dostať (vyskúšaním všetkých jednoduchých ako kľúčových postupne po sebe) v obmedzenom čase.

Pomerne spoľahlivý kód možno získať, ak si vezmete jednoduchý, napríklad 150 znakov. Nájsť taký jednoduchý však nie je také jednoduché. Predpokladajme, že určité číslo A (veľmi veľké) je potrebné skontrolovať na primálnosť. Je to rovnaké ako pri hľadaní jeho deliteľov. Ak môžeme nájsť deliteľa v rozsahu od 2 do druhej odmocniny z A, potom to nie je prvočíslo. Odhadnime počet čísel, ktoré je potrebné otestovať na schopnosť rozdeliť číslo A.

Povedzme, že číslo A má 150 číslic. Jeho druhá odmocnina bude obsahovať najmenej 75 znakov. Na vymenovanie takého počtu možných deliteľov budeme potrebovať veľmi výkonný počítač a obrovské množstvo času, čo znamená, že problém je prakticky neriešiteľný.

Ako sa s tým vysporiadať.

Po prvé, môžete sa naučiť rýchlo kontrolovať deliteľnosť jedného čísla druhým a po druhé môžete skúsiť vybrať číslo A tak, aby bolo prvočíslo s vysokou pravdepodobnosťou. Ukazuje sa, že je to možné. Matematik Mersen objavil čísla nasledujúceho tvaru

Sú jednoduché s vysokou mierou pravdepodobnosti.

Aby sme pochopili frázu napísanú vyššie, spočítajme, koľko prvočísel je v prvej tisícke a koľko Mersenových čísel je prvočísel v tej istej tisícke. Mersenove čísla v prvej tisícke sú teda nasledovné:

2 1 - 1 = 1 ; 2 2 -1 = 3 ; 2 3 - 1 = 7 ; 2 4 - 1 = 15; 2 5 - 1 = 31 ; 2 6 -1 = 63;

2 7 - 1 =127 ; 2 8 -1 = 255; 2 9 - 1 = 511;

Prvočísla sú vyznačené tučným písmom. Na 9 Mersenových čísel pripadá 5 prvočísel. V percentách je to 5/9*100 = 55,6 %. Zároveň na každých 1000 prvých prirodzených čísel pripadá len 169 prvočísel. V percentách je to 169/1000*100 = 16,9 %. To znamená, že v prvej tisícke v percentuálnom vyjadrení sa prvočísla medzi Mersenovými číslami nachádzajú takmer 4-krát častejšie ako medzi jednoduchými prirodzenými číslami.

___________________________________________________________

Teraz si zoberme konkrétne Mersenovo číslo, napríklad 2 4 - 1. Zapíšme ho ako binárne číslo.

2 4 - 1 = 10000 - 1 = 1111

Zoberme si nasledujúce Mersenovo číslo 2 5 -1 a napíšme ho ako binárne číslo. Získame nasledovné:

2 5 -1 = 100000 - 1 = 11111

Už teraz je jasné, že všetky Mersenove čísla sú postupnosťou jednotiek a táto skutočnosť sama o sebe dáva veľký zisk. Po prvé, v dvojkovej číselnej sústave je veľmi jednoduché získať ďalšie Mersenovo číslo, stačí k ďalšiemu číslu pripočítať jedničku a po druhé, hľadanie deliteľov v dvojkovej sústave je oveľa jednoduchšie ako v desiatkovej sústave.

Rýchla konverzia z desatinných miest na binárne

Jedným z hlavných problémov pri používaní binárneho číselného systému je obtiažnosť prevodu desiatkového čísla na binárne. Toto je dosť náročná úloha. Samozrejme, nie je príliš ťažké preložiť malé čísla s tromi alebo štyrmi číslicami, ale pre desatinné čísla s 5 alebo viacerými číslicami je to už ťažké. To znamená, že potrebujeme spôsob, ako rýchlo previesť veľké desatinné čísla na binárne.

Túto metódu vynašiel francúzsky matematik Legendre. Dajme napríklad číslo 11183445. Vydelíme ho 64, dostaneme zvyšok 21 a podiel je 174741. Toto číslo opäť vydelíme 64, dostaneme zvyšok 21 a podiel 2730. , 2730 delené 64 dáva zvyšok 42 a kvocient 42, ale 64 v binárnom systéme je 1 000 000, 21 v binárnom je 10101 a 42 je 101010, preto je pôvodné číslo zapísané v binárnom formáte takto:

101010 101010 010101 010101

Aby to bolo jasnejšie, uvádzame ďalší príklad s menším číslom. Preveďme binárne znázornenie čísla 235. Rozdeľme 235 číslom 64 so zvyškom. Dostaneme:

QUANTIATE = 3, binárne 11 alebo 000011

ZOSTATOK = 43, binárne 101011

Potom 235 = 11101011. Pozrime sa na tento výsledok:

11101011 = 2 7 + 2 6 + 2 5 + 2 3 + 2 1 + 2 0 = 128+64+32+8+2+1 = 235

Poznámky:

1. Je ľahké vidieť, že konečné binárne číslo zahŕňa všetky zvyšky a v poslednom kroku aj zvyšok aj kvocient.
2. Kvocient sa píše pred zvyškom.
3. Ak má výsledný kvocient alebo zvyšok v binárnom vyjadrení menej ako 6 číslic (6 núl obsahuje binárne znázornenie čísla 64 = 1000000), pripočítajú sa k nemu nevýznamné nuly.

A ešte jeden komplexnejší príklad. Číslo je 25678425.

Krok 1: 25678425 delené 64

Súkromné ​​= 401225

Zostávajúce = 25 = 011001

Krok 2: 401225 delené 64

Podiel = 6269

Zvyšok = 9 = 001001

Krok 3: 6269 delené 64

Podiel = 97

Zostávajúce = 61 = 111101

Krok 4: 97 delené 64

Podiel = 1 = 000001

Zostávajúce = 33 = 100 001

Výsledok čísla = 1,100001,111101,001001,011001

V tomto čísle sú medzivýsledky zahrnuté v ňom oddelené bodkou.

Previesť čísla na binárne znázornenie:

PRÍLOHA: TABUĽKA 1

		0,015625
		0,0078125
		0,00390625
		0,001953125
		0,0009765625
		0,00048828125
		0,000244140625
		0,0001220703125
		0,00006103515625
		0,000030517578125
		0,0000152587890625
		0,00000762939453125
		0,000003814697265625
		0,0000019073486328125
		0,00000095367431640625
		0,000000476837158203125

Vykonávanie aritmetických operácií v ľubovoľnom pozičnom číselnom systéme sa vykonáva podľa rovnakých pravidiel, aké sa používajú v desiatkovom číselnom systéme.

Rovnako ako v systéme desiatkových čísel, na vykonávanie aritmetických operácií potrebujete poznať tabuľky sčítania (odčítania) a násobenia.

Tabuľka sčítania, odčítania a násobenia pre binárnu číselnú sústavu

Sčítanie binárnych čísel

Sčítanie v dvojkovej číselnej sústave sa riadi rovnakými pravidlami ako v desiatkovej číselnej sústave. Dve čísla sa zapíšu do stĺpca zarovnaného s oddeľovačom celých a zlomkových častí a v prípade potreby sa doplnia vpravo nevýznamnými nulami. Sčítanie začína od číslice úplne vpravo. Dve jednotky nižšieho rádu sú spojené do jednotky vyššieho rádu.

Príklad: 1011,1 2 + 1010,11 2

Zaujímavá je aj situácia, keď sa pridajú viac ako dve čísla. V tomto prípade je možný prevod cez niekoľko číslic.
Príklad: 111,1 2 + 111 2 + 101,1 2

Pri pridávaní na mieste jednotiek (bit 0) sú 4 jednotky, ktoré po spojení dávajú 100 2 . Preto sa prenáša z nulovej číslice na prvú 0 a v druhom - 1 .
Podobná situácia nastáva v druhej číslici, kde sa pri zohľadnení dvoch prevedených jednotiek získa číslo 5 = 101 2 . 1 zostáva v druhej kategórii, 0 prevedený na tretiu a 1 prenesený do štvrtého.

Odčítanie binárnych čísel

V prípadoch, keď je zapojená jednotka seniorskej kategórie, dáva dve jednotky juniorskej kategórie. Ak sa jednotka študuje po niekoľkých kategóriách, potom dáva jednu jednotku vo všetkých stredných nulových kategóriách a dve jednotky v kategórii, pre ktorú bola študovaná.
Príklad: 10110,01 2 — 1001,1 2

Aritmetické operácie vo všetkých pozičných číselných sústavách sa vykonávajú podľa rovnakých pravidiel, ktoré sú vám dobre známe.

Doplnenie. Uvažujme sčítanie čísel v binárnej číselnej sústave. Vychádza z tabuľky na sčítanie jednociferných binárnych čísel :

Je dôležité venovať pozornosť skutočnosti, že pri pridávaní dvoch sa číslica pretečie a prenesie sa na najvýznamnejšiu číslicu. Pretečenie číslic nastane, keď sa hodnota čísla v ňom rovná alebo je väčšia ako základ.

Sčítanie viacbitových binárnych čísel sa uskutočňuje v súlade s vyššie uvedenou tabuľkou sčítania, pričom sa zohľadňujú možné prevody z číslic nízkeho rádu na číslice vysokého rádu.

Ako príklad pridajme binárne čísla 110 2 a 11 2 do stĺpca :

Skontrolujeme správnosť výpočtov pridaním v desiatkovej číselnej sústave. Prevedieme binárne čísla do desiatkovej číselnej sústavy a potom ich pridáme:

110 2 =1*2 2 + 1*2 1 + 0*2 0 = 6 10 ;

11 2 = 1*2 1 + 1*2 0 = 3 10 ;

6 10 + 3 10 = 9 10 .

Teraz skonvertujme výsledok binárneho sčítania na desatinné číslo:

1001 2 = 1*2 3 +0*2 2 + 0*2 1 + 1*2 0 = 9 10 /

Porovnajme výsledky - sčítanie bolo vykonané správne.

Odčítanie. Pozrime sa na odčítanie binárnych čísel. Vychádza z tabuľky na odčítanie jednociferných binárnych čísel. Pri odčítaní väčšieho čísla (1) od menšieho čísla (0) sa pôžička poskytuje od najvyššej číslice. V tabuľke je pôžička označená 1 riadkom:

Odčítanie viacbitových binárnych čísel prebieha v súlade s vyššie uvedenou tabuľkou odčítania, berúc do úvahy možné pôžičky od najvýznamnejších bitov. Ako príklad si odčítajme binárne čísla 110 2 a 11 2:

Násobenie. Násobenie je založené na tabuľke násobenia pre jednociferné binárne čísla:

Násobenie viacciferných binárnych čísel nastáva v súlade s vyššie uvedenou tabuľkou násobenia podľa obvyklej schémy používanej v sústave desiatkových čísel s postupným násobením násobiteľa číslicami násobiteľa. Ako príklad si vynásobme binárne čísla a:

divízie. Operácia delenia sa vykonáva pomocou algoritmu podobného algoritmu vykonávania operácie delenia v desiatkovej číselnej sústave. Ako príklad si rozdeľme binárne číslo 110 2 a 11 2: