Binární aritmetika

Název parametru	Význam
Téma článku:	Binární aritmetika
Rubrika (tematická kategorie)	Počítačová věda

Binární číselná soustava

Číselné soustavy používané při práci s počítačem

Základ P = 2. Abeceda obsahuje dvě dvojkové číslice: 0, 1. Libovolné číslo C = C n C n-1 ...C 1 C 0 C -1 C -m je součet mocnin čísla P = 2 ,

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

Pří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ární číselné soustavě jsou 1, 4, 8,16,... nalevo od desetinné čárky a 0,5; 0,25; 0,125; 0,625;... napravo od desetinné čárky.

Někdy se používá v programování hexadecimální notový zápis. Pro znázornění čísel větších než 9 v hexadecimálním číselném systému se používají latinská písmena A, B, C, D, E, F. Obrázky prvních šestnácti čísel v desítkové, binární a šestnáctkové číselné soustavě jsou uvedeny v tabulce. 2.

Tabulka kódů v různé systémy mrtvé zúčtování

tabulka 2

Desetinná soustava	Binární systém	Hexadecimální soustava	Desetinná soustava	Binární systém	Hexadecimální soustava
					A
					B
					C
					D
					E
					F

Binární desítkovéČíselná soustava se v moderních počítačích rozšířila díky snadnému převodu na desítkovou soustavu a naopak. Používá se tam, kde se nehledí hlavně na jednoduchost technické konstrukce stroje, ale na pohodlí uživatele. V tomto číselném systému jsou všechny desetinné číslice odděleně kódovány čtyřmi binárními číslicemi.

Příklad 3.7.

Desetinné číslo 9703 v BCD vypadá takto: 1001 0111 0000 0011.

Výhoda dvojkové číselné soustavy oproti desítkové číselné soustavě z pohledu číslicového počítače je následující:

• jsou vyžadovány prvky se dvěma stabilními stavy;
• aritmetické operace jsou výrazně zjednodušeny;
• je zapotřebí 1,5krát méně vybavení;
• umožňuje používat aparát matematické logiky pro analýzu a syntézu obvodů.

Nevýhody binárního číselného systému jsou následující:

• velká délka záznamu;
• Při zadávání a výstupu informací je vyžadován převod do desítkové soustavy čísel.

Podívejme se, jak se základní operace provádějí v binární aritmetice.

Pravidla aritmetiky ve všech pozičních číselných soustavách jsou stejná, ᴛ.ᴇ. sčítání, násobení a odčítání začínají od nejnižších číslic, dělení - od nejvyšších.

Při sčítání se nosná jednotka přičte k číslicím sousední nejvýznamnější číslice. Když se odečte, jednotka výpůjčky na nejvyšší číslici dává dvě jednotky na nejnižší sousední číslici.

Příklad 3.8

Násobení binárních čísel je podobné jako násobení desítkových čísel, ale... Pokud násobíme pouze 0 a 1, pak se násobení redukuje na operaci posunu a sčítání.

Příklad 3.9

Binární aritmetika - pojem a typy. Klasifikace a vlastnosti kategorie "Binární aritmetika" 2017, 2018.

- Binární aritmetika

Protože informační procesy PROTI digitální systémy nabývají hodnoty pouze 0 a 1, pak se reprezentace dat provádí pomocí binárních čísel. Sčítání a odčítání binárních čísel, stejně jako všechny ostatní aritmetické operace, se provádějí podle stejných pravidel jako... .

- Binární číselná soustava a binární aritmetika

V binární číselné soustavě můžete s čísly provádět stejné operace jako v desítkové číselné soustavě. Sčítání se provádí na stejném principu jako v desítkové číselné soustavě: pouze pokud z dané číslice vznikne množství, které se do ní nevejde, pak...

, Soutěž "Prezentace k lekci"

Prezentace na lekci

Zpět dopředu

Pozornost! Náhled Snímky slouží pouze pro informační účely a nemusí představovat všechny funkce prezentace. Jestli máte zájem tato práce, stáhněte si prosím plnou verzi.

Cíle lekce: (snímek 2)

1. Seznámit studenty s binární číselnou soustavou.
2. Rozvíjet dovednosti v provádění aritmetických operací s binárními čísly

Během vyučování

I. Začátek lekce

Učitel: Abyste lépe zvládli binární číselný systém, musíte zvládnout provádění aritmetických operací s binárními čísly.

Všechny poziční číselné soustavy jsou „stejné“, totiž ve všech se aritmetické operace provádějí podle stejných pravidel:

• platí stejné aritmetické zákony: komutativní, asociativní, distributivní;
• platí pravidla sčítání, odčítání, násobení a dělení;
• Pravidla pro provádění aritmetických operací jsou založena na tabulkách sčítání a násobení.

Podívejme se na pravidla pro provádění aritmetických operací

II. Učení nového materiálu

Při dělení sloupcem musíte jako mezivýsledky provést násobení a odčítání. Ale v binární číselné soustavě jsou mezilehlá násobení redukována na násobení dělitele buď 0 nebo 1, takže nejobtížnější operací zůstává odečítání, které se musíte naučit dělat přesně.

III. Upevňování naučeného. (snímek 12)

Kluci dělají práci sami. Poté otevřete snímek s odpověďmi.

Odpovědi. (Snímek 13)

IV. Domácí úkol (snímek 14)

1. Naučte se pravidla pro provádění aritmetických operací v binární číselné soustavě.

2. Postupujte takto:

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

Domov \ Dokumentace \ Pro učitele informatiky

Při použití materiálů z tohoto webu - a umístění banneru je POVINNÉ!!!

Binární aritmetika

Čísla, která jsme zvyklí používat, se nazývají desítková a aritmetika, kterou používáme, se také nazývá desítková. Každé číslo totiž může být složeno ze sady čísel obsahující 10 znaků – čísel – „0123456789“.

Matematika se vyvíjela tak, že právě tato množina se stala hlavní, ale desítková aritmetika není jediná. Pokud vezmeme pouze pět číslic, pak na jejich základě můžeme sestavit pětimístnou aritmetiku a ze sedmi číslic sedmimístnou aritmetiku. V oblastech znalostí souvisejících s počítačové vybaveníČasto se používá aritmetika, ve které jsou čísla tvořena šestnácti číslicemi; podle toho se tato aritmetika nazývá hexadecimální. Abychom pochopili, co je číslo v nedesítkové aritmetice, nejprve zjistíme, co je to číslo v desítkové aritmetice.

Vezměte si například číslo 246. Tento zápis znamená, že v čísle jsou dvě stovky, čtyři desítky a šest jedniček. Můžeme tedy napsat následující rovnost:

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

Rovnítko zde odděluje tři způsoby zápisu stejného čísla. Nyní je pro nás nejzajímavější třetí forma zápisu: 2 * 10 2 + 4 * 10 1 + 6 * 10 0 . Je strukturován takto:

Naše číslo má tři číslice. Vedoucí číslice "2" je číslo 3. Vynásobí se tedy 10 na druhou mocninu. Další číslice „4“ má pořadové číslo 2 a v první číslici se násobí 10. Již je jasné, že číslice se násobí deseti na mocninu o jednu méně, než je pořadové číslo číslice. Po pochopení výše uvedeného si můžeme zapsat obecný vzorec pro vyjádření desetinného čísla. Dostaneme číslo s N číslicemi. Budeme označovat i-tá číslice prostřednictvím i. Potom lze číslo zapsat v následujícím tvaru: a n a n-1 ....a 2 a 1 . Toto je první formulář a třetí formulář bude vypadat 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 ze sady "0123456789"

Role desítky je na této nahrávce velmi jasně vidět. Desítka je základem pro tvoření čísel. A mimochodem, nazývá se „základ číselné soustavy“ a samotná číselná soustava je důvodem, proč se nazývá „desítková“. Číslo deset samozřejmě nemá žádné speciální vlastnosti. Desítku snadno nahradíme jakýmkoli jiným číslem. Například číslo v pětimístné číselné soustavě lze zapsat 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 ze sady "01234"

Obecně nahradíme 10 jakýmkoli jiným číslem a získáme úplně jinou číselnou soustavu a jinou aritmetiku. Nejjednodušší aritmetiku získáme, když 10 nahradíme 2. Výsledná číselná soustava se nazývá binární a číslo v ní je definováno 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 nejjednodušší ze všech možných, protože v něm je libovolné číslo tvořeno pouze dvěma číslicemi 0 a 1. Je jasné, že jednodušší už to být nemůže. Příklady binárních čísel: 10, 111, 101.

Velmi důležitá otázka. Je možné reprezentovat binární číslo jako desítkové číslo a naopak? desetinné číslo reprezentovat v binární podobě.

Binární na desítkové. Je to velmi jednoduché. Způsob takového překladu je dán naším způsobem zápisu čísel. Vezměme si například následující binární číslo 1011. Rozložme ho na mocniny dvou. Získáme následující:

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

Proveďme všechny zaznamenané akce a získáme:

1 * 2 3 + 0 * 2 2 + 1 * 2 1 + 1 * 2 0 = 8 + 0+ 2 + 1 = 11. Dostaneme tedy, že 1011 (binární) = 11 (desetinně). Okamžitě je vidět drobná nepříjemnost binárního systému. Stejné číslo, které je zapsáno v desítkové soustavě jednou číslicí ve dvojkové soustavě, vyžaduje pro svůj záznam čtyři číslice. Ale to je cena za jednoduchost (nic není zadarmo). Ale binární systém dává obrovský zisk v aritmetických operacích. A to uvidíme později.

Vyjádřete následující binární čísla jako desítkové.

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

Sčítání binárních čísel.

Způsob sčítání sloupců je obecně stejný jako u desetinného čísla. To znamená, že sčítání se provádí bitově, počínaje nejméně významnou číslicí. Pokud je při sčítání dvou číslic SOUČET větší než devět, zapíše se číslice = SOUČET - 10 a CELÁ ČÁST (SOUČET / 10) se přičte jako nejvýznamnější číslice. (Přidejte několik čísel do sloupce, pamatujte si, jak se to dělá.) Totéž s binárním číslem. Přidejte jeden po druhém, počínaje nejnižší číslicí. Pokud je výsledek větší než 1, zapíše se 1 a k nejvýznamnější číslici se přičte 1 (říkají „z hlavy“).

Udělejme příklad: 10011 + 10001.

První kategorie: 1+1 = 2. Píšeme 0 a 1, jak nás napadne.

Druhá kategorie: 1+0+1 (uložená jednotka) =2. Zapisujeme si 0 a 1, napadlo mě.

Třetí kategorie: 0+0+1 (zapamatovaná jednotka) = 1. Napište 1.

Čtvrtá kategorie 0+0=0. Píšeme 0.

Pátá kategorie 1+1=2. Zapíšeme 0 a přidáme 1 k šesté číslici.

Převeďme všechna tři čísla do desítkové soustavy a zkontrolujme správnost sčítání.

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ávná rovnost

Příklady nezávislých řešení:

a) 11001 +101 =

b) 11001 +11001 =

c) 1001 + 111 =

e) 10 011 + 101 =

e) 11011 + 1111 =

e) 11111 + 10011 =

Jak převést desítkové číslo na binární. Další operací je odečítání. Touto operací se ale budeme zabývat o něco později a nyní zvážíme způsob převodu desítkového čísla na binární.

Aby bylo možné převést desetinné číslo na binární, musí být rozšířeno na mocniny dvě. Ale pokud se expanze v mocninách deseti získá okamžitě, pak to, jak expandovat v mocninách dvou, vyžaduje trochu přemýšlení. Nejprve se podívejme, jak to provést pomocí metody výběru. Vezměme si desetinné číslo 12.

Krok první. 2 2 = 4, to nestačí. Také 2 3 = 8 nestačí, ale 2 4 = 16 už je hodně. Proto ponecháme 2 3 =8. 12 - 8 = 4. Nyní to musíte vyjádřit jako mocninu dvou 4.

Krok dva. 4 = 22.

Pak je naše číslo 12 = 2 3 + 2 2. Nejvyšší číslice má číslo 4, nejvyšší stupeň = 3, proto musí existovat členy s mocninami dvou 1 a 0. Ty ale nepotřebujeme, abychom se zbavili zbytečných stupňů a nechali potřebné , zapíšeme číslo takto: 1*2 3 + 1* 2 2 +0*2 1 + 0*2 0 = 1100 - toto je binární reprezentace čísla 12. Je snadné si všimnout, že každá následná mocnina je největší mocnina dvou, což je menší než rozkladové číslo. Pro konsolidaci metody se podívejme na jiný příklad. Číslo 23.

Krok 1. Nejbližší mocnina dvou je 2 4 = 16. 23 -16 = 7.

Krok 2. Nejbližší mocnina dvou 2 2 = 4. 7 - 4 = 3

Krok 3. Nejbližší mocnina dvou 2 1 = 2. 3 - 2 = 1

Krok 4. Nejbližší mocnina dvou 2 0 =1 1 - 1 =0

Dostaneme následující rozšíření: 1*2 4 + 0*2 3 +1*2 2 +1*2 1 +1*2 0

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

Výše diskutovaná metoda dobře řeší problém, který je jí přiřazen, ale existuje metoda, která je algoritmizována mnohem lépe. Algoritmus pro tuto metodu je napsán níže:

Pokud je ČÍSLO větší než nula, udělejte to

NEXT DIGIT = zbytek ČÍSLA děleno 2

ČÍSLO = celá část čísla ČÍSLO děleno 2

Když tento algoritmus dokončí svou práci, posloupnost vypočítaných NEXT DIGITS bude představovat binární číslo. Pracujme například s číslem 19.

Začátek algoritmu ČÍSLO = 19

DALŠÍ ČÍSLICE = 1

DALŠÍ ČÍSLICE = 1

DALŠÍ ČÍSLICE = 0

DALŠÍ ČÍSLICE = 0

DALŠÍ ČÍSLICE = 1

Ve výsledku tedy máme následující číslo 10011. Všimněte si, že obě diskutované metody se liší v pořadí, ve kterém se získávají další číslice. U prvního způsobu je první přijatá číslice nejvýznamnější číslicí binárního čísla a u druhého způsobu je první přijatá číslice naopak nejméně významná.

Převeďte desetinná čísla na binární dvěma způsoby

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

Jak převést zlomek na desetinné číslo.

Je známo, že jakékoli racionální číslo může být reprezentováno jako desetinný a obyčejný zlomek. Obyčejný zlomek, tedy zlomek tvaru A/B, může být pravidelný a nevlastní. Zlomek se nazývá správný, pokud A<В и неправильной если А>V.

Pokud je racionální číslo reprezentováno nevlastním zlomkem a čitatel zlomku je dělen jmenovatelem celkem, pak je toto racionální číslo celé číslo, ve všech ostatních případech se objevuje zlomková část. Zlomková část je často velmi dlouhé číslo a dokonce nekonečno (nekonečný periodický zlomek, například 20/6), takže v případě zlomkové části nemáme za úkol pouze přeložit jednu reprezentaci do druhé, ale přeložit pomocí jistá přesnost.

Pravidlo přesnosti. Předpokládejme, že je vám přiděleno desetinné číslo, které lze vyjádřit jako desetinný zlomek s přesností na N číslic. Aby bylo odpovídající binární číslo stejně přesné, je nutné do něj napsat znaménka M, takže

Nyní se pokusíme získat pravidlo překladu a nejprve se podívejme na příklad 5 401

Řešení:

Celou část získáme podle nám již známých pravidel a rovná se binárnímu číslu 101. A zlomkovou část rozšíříme o mocniny 2.

Krok 1: 2-2 = 0,25; 0,401 - 0,25 = 0,151. - to je zbytek.

Krok 2: Nyní potřebujeme vyjádřit 0,151 jako mocninu dvou. Udělejme toto: 2 -3 = 0,125; 0,151 - 0,125 = 0,026

Původní zlomkovou část lze tedy reprezentovat jako 2 -2 +2 -3. Totéž lze zapsat do tohoto binárního čísla: 0,011. První desetinná číslice je nula, protože v našem rozšíření neexistuje mocnina 2 -1.

Z prvního a druhého kroku je zřejmé, že tato reprezentace není přesná a může být žádoucí v expanzi pokračovat. Podívejme se na pravidlo. Říká, že potřebujeme tolik znaků M, že 10 3 je méně než 2 M. To znamená 1000<2 M . То есть в двоичном разложении у нас должно быть не менее десяти знаков, так как 2 9 = 512 и только 2 10 = 1024. Продолжим процесс.

Krok 3: Nyní pracujeme s číslem 0,026. Nejbližší mocnina dvou k tomuto číslu je 2 -6 = 0,015625; 0,026 - 0,015625 = 0,010375 Nyní je naše přesnější binární číslo: 0,011001. Za desetinnou čárkou je již šest míst, ale to ještě nestačí, takže provedeme ještě jeden krok.

Krok 4: Nyní pracujeme s číslem 0,010375. Nejbližší mocnina dvou k tomuto číslu je 2 -7 = 0,0078125;

0,010375 - 0,0078125 = 0,0025625

Krok 5: Nyní pracujeme s číslem 0,0025625. Nejbližší mocnina dvou k tomuto číslu je 2 -9 = 0,001953125;

0,0025625 - 0,001953125 = 0,000609375

Poslední výsledný zbytek je menší než 2 -10 a pokud bychom chtěli pokračovat v aproximaci původního čísla, potřebovali bychom 2 -11, ale to již přesahuje požadovanou přesnost, a proto lze výpočty zastavit a výslednou binární reprezentaci zlomkovou část lze zapsat.

0,401 = 0,011001101

Jak vidíte, převod zlomkové části desetinného čísla na binární je o něco složitější než převod části celého čísla. Tabulka mocnin dvojky na konci přednášky.

Nyní si zapišme konverzní algoritmus:

Počáteční data algoritmu: Prostřednictvím A budeme označovat původní vlastní desetinný zlomek zapsaný v desítkovém tvaru. Nechť tento zlomek obsahuje N znaků.

Algoritmus

Akce 1. Určete počet požadovaných binárních číslic M z nerovnosti 10 N< 2 M

Akce 2: Cyklus pro výpočet číslic binárního zobrazení (číslice po nule). Číselné číslo bude označeno symbolem K.

1. Číslice = 1
2. Pokud 2-K > A

Poté k binárnímu číslu přidáme nulu

• přidejte 1 k binárnímu číslu
• A = A-2-K

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

• pak je algoritmus dokončen
• V opačném případě přejděte k bodu 2.

Převeďte desetinná čísla na binární

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

Odečítání binárních čísel. Odečítat budeme i čísla ve sloupci a obecné pravidlo je stejné jako u desetinných čísel, odčítání se provádí bit po bitu a pokud je na místě málo, tak v nejvyšším. Vyřešme následující příklad:

První kategorie. 1 - 0 = 1. Zapisujeme 1.

Druhá kategorie 0-1. Jeden chybí. Obsazujeme ji v seniorské kategorii. Jednotka z vyšší číslice přechází do nižší, jako dvě jednotky (protože vyšší číslice je reprezentována dvojkou vyššího stupně) 2-1 = 1. Zapisujeme 1.

Třetí kategorie. Obsadili jsme jednotku této hodnosti, takže nyní v hodnosti 0 je potřeba obsadit jednotku nejvyšší hodnosti. 2-1 = 1. Zapisujeme 1.

Výsledek zkontrolujeme v desítkové soustavě

1101 - 110 = 13 - 6 = 7 (111) Správná rovnost.

Další zajímavý způsob provádění odčítání zahrnuje koncept kódu dvojkového doplňku, který umožňuje omezit odčítání na sčítání. Výsledek čísla ve dvojkovém kódu je velmi jednoduchý: vezmeme číslo, nuly nahradíme jedničkami, naopak jedničky nahradíme nulami a k ​​nejméně významné číslici přidáme jedničku. Například 10010, doplňkový kód bude 011011.

Pravidlo odčítání přes dvojkový doplněk říká, že odčítání může být nahrazeno sčítáním, pokud je odčítání nahrazeno číslem ve dvojkovém doplňku.

Příklad: 34 - 22 = 12

Zapišme tento příklad v binárním tvaru. 100010–10110 = 1100

Doplňkový kód čísla 10110 bude vypadat takto

01001 + 00001 = 01010. Pak lze původní příklad nahradit sčítáním takto: 100010 + 01010 = 101100 Dále je třeba vyřadit jednu jednotku v nejvýznamnější číslici. Pokud to uděláme, dostaneme 001100. Zahoďme bezvýznamné nuly a dostaneme 1100, to znamená, že příklad byl vyřešen správně

Provádějte odčítání. Obvyklým způsobem a v dodatečném kódu, po předchozím převedení desetinných čísel na binární:

Zkontrolujte převodem binárního výsledku do desítkové číselné soustavy.

Násobení v binární číselné soustavě.

Nejprve zvažte následující zajímavý fakt. K vynásobení binárního čísla 2 (desetinná dvojka je ve dvojkové soustavě 10) stačí přidat jednu nulu vlevo od násobeného čísla.

Příklad. 10101 * 10 = 101010

Zkouška.

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

Pokud si pamatujeme, že každé binární číslo lze rozšířit na mocniny dvou, pak je jasné, že násobení v binárním číselném systému je redukováno na násobení 10 (tj. dekadickým číslem 2), a proto je násobení řadou po sobě jdoucích směny. Obecným pravidlem je, že stejně jako u desítkových čísel se binární násobení provádí bitově. A za každou číslici druhého násobitele se napravo od prvního násobitele přičte jedna nula. Příklad (zatím není ve sloupci):

1011 * 101 Toto násobení lze zredukovat na součet tříciferných násobení:

1011 * 1 + 1011 * 0 + 1011 * 100 = 1011 +101100 = 110111 Totéž lze zapsat do sloupce, jako je tento:

Zkouška:

101 = 5 (desítkové)

1011 = 11 (desítkové)

110111 = 55 (desítkové)

5*11 = 55 správná rovnost

Rozhodněte se sami

a) 1101 * 1110 =

b) 1010 * 110 =

e) 101011 * 1101 =

e) 10010 * 1001 =

Poznámka: Mimochodem, násobící tabulka ve dvojkové soustavě se skládá pouze z jedné položky 1 * 1 = 1

Dělení v binární číselné soustavě.

Už jsme se podívali na tři akce a myslím, že už je jasné, že obecně se akce na binárních číslech od akcí na desítková čísla liší jen málo. Jediný rozdíl je v tom, že existují dvě čísla a ne deset, ale to pouze zjednodušuje aritmetické operace. U dělení je situace stejná, ale pro lepší pochopení si algoritmus dělení rozebereme podrobněji. Předpokládejme, že potřebujeme vydělit dvě desetinná čísla, například 234 děleno 7. Jak to uděláme.

Vybereme doprava (od nejvýznamnější číslice) takový počet číslic, aby výsledné číslo bylo co nejmenší a zároveň větší než dělitel. 2 je menší než dělitel, proto potřebujeme číslo 23. Výsledné číslo pak vydělíme dělitelem se zbytkem. Dostaneme následující výsledek:

Popsanou operaci opakujeme, dokud výsledný zbytek není menší než dělitel. Když k tomu dojde, číslo získané pod čarou je podíl a poslední zbytek je zbytek operace. Operace dělení binárního čísla se tedy provádí úplně stejným způsobem. Zkusme to

Příklad: 10010111 / 101

Hledáme číslo, jehož první číslice je větší než dělitel. Toto je čtyřmístné číslo 1001. Je zvýrazněno tučně. Nyní musíte pro vybrané číslo najít dělitele. A zde opět vítězíme ve srovnání s desítkovou soustavou. Faktem je, že vybraný dělitel je nutně číslo a my máme pouze dvě čísla. Protože 1001 je jasně větší než 101, pak je s dělitelem vše jasné: 1. Proveďme krok operace.

Zbytek dokončené operace je tedy 100. To je méně než 101, takže k provedení kroku druhého dělení je třeba přidat další číslici ke 100, toto je číslice 0. Nyní máme následující číslo:

1000 je větší než 101, takže ve druhém kroku opět přičteme k podílu číslo 1 a dostaneme následující výsledek (pro úsporu místa hned vynecháme další číslici).

Třetí krok. Výsledné číslo 110 je větší než 101, takže v tomto kroku zapíšeme do podílu 1. Dopadne to takto:

Výsledné číslo 11 je menší než 101, takže do podílu zapíšeme číslo 0 a snížíme další číslo dolů. Dopadne to takto:

Výsledné číslo je větší než 101, proto do podílu zapíšeme číslo 1 a provedeme akce znovu. Ukazuje se tento obrázek:

1

0

Výsledný zbytek 10 je menší než 101, ale v dividendě nám došly číslice, takže 10 je konečný zbytek a 1110 je požadovaný kvocient.

Pojďme zkontrolovat desetinná čísla

Tím končí popis nejjednodušších aritmetických operací, které potřebujete znát, abyste mohli používat binární aritmetiku, a nyní se pokusíme odpovědět na otázku „Proč je binární aritmetika potřebná? Již výše se samozřejmě ukázalo, že zápis čísla ve dvojkové soustavě výrazně zjednodušuje početní operace, ale zároveň se samotný záznam značně prodlužuje, což snižuje hodnotu výsledného zjednodušení, takže je nutné hledat úlohy, jejichž řešení je mnohem jednodušší v binárních číslech.

Úkol 1: Načtení všech vzorků

Velmi často se vyskytují problémy, ve kterých je potřeba umět sestavit všechny možné kombinace z dané množiny objektů. Například tento úkol:

Vzhledem k velké hromadě kamenů uspořádejte kameny do dvou hromádek tak, aby hmotnost těchto dvou hromádek byla co nejvíce stejná.

Tento úkol lze formulovat následovně:

Najděte výběr kamenů z velké hromady tak, aby se jejich celková hmotnost co nejméně lišila od poloviny hmotnosti velké hromady.

Úkolů tohoto druhu je poměrně hodně. A všechny se scvrkají, jak již bylo řečeno, na schopnost získat z dané množiny prvků všechny možné kombinace (dále jim budeme říkat vzorky). A nyní se podíváme na obecnou metodu získání všech možných vzorků pomocí operace binárního sčítání. Začněme příkladem. Nechť existuje soubor tří objektů. Pojďme sestrojit všechny možné vzorky. Předměty budeme označovat sériovými čísly. To znamená, že existují následující 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);

Pokud je pozice s dalším číslem jedna, znamená to, že prvek s číslem rovným této pozici je ve výběru přítomen, a pokud je nula, pak prvek není přítomen. Například vzorek (0, 1, 0); sestává z jednoho prvku s číslem 2 a výběr je (1, 1, 0); se skládá ze dvou prvků s čísly 1 a 2.

Tento příklad jasně ukazuje, že vzorek může být reprezentován jako binární číslo. Navíc je dobře vidět, že výše jsou zapsána všechna možná jedno, dvou a třímístná binární čísla. Přepišme je takto:

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

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

Obdrželi jsme řadu po sobě jdoucích binárních čísel, z nichž každé získáme z předchozího přidáním jednoho. Můžete to zkontrolovat. Pomocí tohoto pozorovaného vzoru můžeme sestavit následující algoritmus pro získání vzorků.

Vstupní data algoritmu

Daný soubor objektů N - kusů. V následujícím budeme tuto množinu nazývat množina počátečních prvků. Očíslujme všechny prvky původní množiny od 1 do N. Udělejme binární číslo z N nevýznamných nul. 0000… 0 N Toto nulové binární číslo bude označovat nulový vzorek, se kterým začne proces vzorkování. Číslice čísla se počítají zprava doleva, to znamená, že číslice nejvíce vlevo je nejvýznamnější.

Dohodněme se, že toto binární číslo budeme označovat velkými písmeny BINARY

Algoritmus

Pokud BINARY číslo sestává výhradně z jedniček

Poté algoritmus zastavíme

• Jedničku přičteme k BINÁRNÍMU číslu podle pravidel binární aritmetiky.
• Z výsledného BINARY čísla vytvoříme další vzorek, jak je popsáno výše.

Úloha 2: Hledání velkých prvočísel

Pro začátek si připomeňme, že prvočíslo je přirozené číslo, které je dělitelné pouze 1 a sebou samým. Příklady prvočísel: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

Hledání velkých prvočísel je velmi důležitý matematický problém. Velká prvočísla jsou nezbytná pro některé šifrovací algoritmy pro bezpečné šifrování zpráv. Navíc jsou potřeba nejen velké počty, ale i velmi velké. Čím větší číslo, tím spolehlivější je šifra postavená na tomto čísle.

Poznámka. Silná šifra je šifra, jejíž rozluštění trvá velmi dlouho.

Proč? Prvočíslo funguje jako klíč pro šifrování a dešifrování. Navíc víme, že prvočísla se vyskytují v řadě přirozená čísla ne příliš často. Mezi první tisícovkou jich je poměrně hodně, pak jejich počet začíná rychle klesat. Vezmeme-li tedy za klíč nepříliš velké číslo, dešifrovač s pomocí ani ne příliš velkého, rychlý počítač se k ní budou moci dostat (vyzkoušením všech jednoduchých jako klíčových postupně) v omezeném čase.

Poměrně spolehlivý kód lze získat, pokud vezmete jednoduchý, například 150 znaků. Najít takový jednoduchý však není tak snadné. Předpokládejme, že určité číslo A (velmi velké) potřebuje zkontrolovat primálnost. Je to stejné jako hledat jeho dělitele. Pokud najdeme dělitele v rozsahu od 2 do druhé odmocniny z A, pak to není prvočíslo. Odhadněme počet čísel, která je potřeba otestovat pro schopnost dělit číslo A.

Řekněme, že číslo A má 150 číslic. Jeho druhá odmocnina bude obsahovat alespoň 75 znaků. K vyjmenování takového počtu možných dělitelů budeme potřebovat velmi výkonný počítač a obrovské množství času, což znamená, že problém je prakticky neřešitelný.

Jak se s tím vypořádat.

Za prvé se můžete naučit rychle kontrolovat dělitelnost jednoho čísla druhým a za druhé můžete zkusit vybrat číslo A tak, aby bylo prvočíslo s vysokou mírou pravděpodobnosti. Ukazuje se, že je to možné. Matematik Mersen objevil tato čísla následujícího tvaru

Jsou jednoduché s vysokou mírou pravděpodobnosti.

Abychom porozuměli výše napsané frázi, spočítejme, kolik prvočísel je v prvním tisíci a kolik Mersenových čísel je prvočísel ve stejném tisíci. Takže Mersenova čísla v první tisícovce jsou následující:

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 jsou vyznačena tučně. Na 9 Mersenových čísel připadá 5 prvočísel. V procentech je to 5/9*100 = 55,6 %. Přitom na každých 1000 prvních přirozených čísel připadá pouze 169 prvočísel. V procentech je to 169/1000*100 = 16,9 %. To znamená, že v první tisícině, v procentech, se prvočísla mezi Mersenovými čísly nacházejí téměř 4krát častěji než mezi jednoduchými přirozenými čísly.

___________________________________________________________

Nyní si vezměme konkrétní Mersenovo číslo, například 2 4 - 1. Zapišme ho jako binární číslo.

2 4 - 1 = 10000 - 1 = 1111

Vezměme následující Mersenovo číslo 2 5 -1 a zapišme ho jako binární číslo. Získáme následující:

2 5 -1 = 100000 - 1 = 11111

Již nyní je jasné, že všechna Mersenova čísla jsou posloupností jedniček a tato skutečnost sama o sobě dává velký zisk. Za prvé, v binární číselné soustavě je velmi jednoduché získat další Mersenovo číslo, stačí k dalšímu číslu přičíst jedničku a za druhé je hledání dělitelů ve dvojkové soustavě mnohem jednodušší než v desítkové soustavě.

Rychlý převod z desítkové soustavy na binární

Jedním z hlavních problémů s používáním binárního číselného systému je obtížnost převodu desítkového čísla na binární. To je docela pracný úkol. Samozřejmě není příliš obtížné překládat malá čísla o třech nebo čtyřech číslicích, ale pro desetinná čísla s 5 a více číslicemi je to již obtížné. To znamená, že potřebujeme způsob, jak rychle převést velká desetinná čísla na binární.

Tuto metodu vynalezl francouzský matematik Legendre. Nechť dostaneme například číslo 11183445. Vydělíme ho 64, dostaneme zbytek 21 a podíl je 174741. Toto číslo opět vydělíme 64, dostaneme zbytek 21 a podíl 2730. , 2730 děleno 64 dává zbytek 42 a podíl 42, ale 64 v binárním systému je 1000000, 21 v binárním je 10101 a 42 je 101010, Původní číslo je tedy zapsáno binárně takto:

101010 101010 010101 010101

Aby to bylo jasnější, zde je další příklad s menším číslem. Převeďme binární reprezentaci čísla 235. Vydělme 235 číslem 64 se zbytkem. Dostaneme:

QUANTIATE = 3, binární 11 nebo 000011

ZBYTEK = 43, binární 101011

Pak 235 = 11101011. Zkontrolujeme tento výsledek:

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

Poznámky:

1. Je snadné vidět, že konečné binární číslo zahrnuje všechny zbytky a v posledním kroku jak zbytek, tak podíl.
2. Kvocient se zapisuje před zbytek.
3. Pokud má výsledný kvocient nebo zbytek v binárním vyjádření méně než 6 číslic (6 nul obsahuje binární vyjádření čísla 64 = 1000000), pak se k němu přičtou nevýznamné nuly.

A ještě jeden složitější příklad. Číslo je 25678425.

Krok 1: 25678425 děleno 64

Soukromé = 401225

Zbývající = 25 = 011001

Krok 2: 401225 děleno 64

Podíl = 6269

Zbytek = 9 = 001001

Krok 3: 6269 děleno 64

Podíl = 97

Zbývající = 61 = 111101

Krok 4: 97 děleno 64

Podíl = 1 = 000001

Zbývající = 33 = 100 001

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

V tomto čísle jsou mezivýsledky v něm zahrnuté oddělené tečkou.

Převést čísla na binární reprezentaci:

PŘÍLOHA: TABULKA 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

Provádění aritmetických operací v libovolné poziční číselné soustavě se provádí podle stejných pravidel, která se používají v desítkové číselné soustavě.

Stejně jako v desítkové číselné soustavě potřebujete k provádění aritmetických operací znát tabulky sčítání (odčítání) a násobení.

Tabulka sčítání, odčítání a násobení pro binární číselnou soustavu

Sčítání binárních čísel

Sčítání v binární číselné soustavě se řídí stejnými pravidly jako v desítkové číselné soustavě. Dvě čísla se zapisují do sloupce zarovnaného s oddělovačem celých a zlomkových částí a v případě potřeby se zprava doplní nevýznamnými nulami. Sčítání začíná od číslice úplně vpravo. Dvě jednotky nižšího řádu jsou spojeny do jednotky vyššího řádu.

Příklad: 1011,1 2 + 1010,11 2

Zajímavá je i situace, kdy se sčítají více než dvě čísla. V tomto případě je možný převod pomocí několika číslic.
Příklad: 111,1 2 + 111 2 + 101,1 2

Při sčítání na místě jedniček (bit 0) jsou 4 jedničky, které po spojení dávají 100 2 . Přenáší se tedy z nulové číslice na první 0 a ve druhém - 1 .
Podobná situace nastává u druhé číslice, kde se s přihlédnutím ke dvěma převedeným jednotkám získá číslo 5 = 101 2 . 1 zůstává ve druhé kategorii, 0 převedeno na třetí a 1 převedena do čtvrtého.

Odečítání binárních čísel

V případech, kdy je zapojena jednotka kategorie senior, dává dvě jednotky kategorie junior. Pokud je jednotka studována po několika kategoriích, pak dává jednu jednotku ve všech středních nulových kategoriích a dvě jednotky v kategorii, pro kterou byla studována.
Příklad: 10110,01 2 — 1001,1 2

Aritmetické operace ve všech polohových číselných soustavách se provádějí podle stejných pravidel, která jsou vám dobře známá.

Přidání. Zvažme sčítání čísel v binární číselné soustavě. Vychází z tabulky pro sčítání jednociferných binárních čísel :

Je důležité věnovat pozornost skutečnosti, že při sčítání dvou jedniček se číslice přeteče a přenese se na číslici nejvýznamnější. Přetečení číslic nastane, když hodnota čísla v něm bude rovna nebo větší než základ.

Sčítání vícebitových binárních čísel probíhá v souladu s výše uvedenou tabulkou sčítání, přičemž se berou v úvahu možné převody z číslic nízkého řádu na číslice vysokého řádu.

Jako příklad sečteme binární čísla 110 2 a 11 2 do sloupce :

Zkontrolujme si správnost výpočtů přidáním v desítkové číselné soustavě. Převedeme binární čísla do desítkové číselné soustavy a poté je sečteme:

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 .

Nyní převedeme výsledek binárního sčítání na desítkové číslo:

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

Porovnejme výsledky – sčítání proběhlo správně.

Odčítání. Podívejme se na odečítání binárních čísel. Vychází z tabulky pro odečítání jednociferných binárních čísel. Při odečtení většího čísla (1) od menšího čísla (0) se půjčka provede od nejvyšší číslice. V tabulce je půjčka označena 1 řádkem:

Odečítání vícebitových binárních čísel probíhá v souladu s výše uvedenou tabulkou odečítání, přičemž se berou v úvahu možné výpůjčky z nejvýznamnějších bitů. Jako příklad odečteme binární čísla 110 2 a 11 2:

Násobení. Násobení je založeno na tabulce násobení pro jednociferná binární čísla:

Násobení vícemístných binárních čísel probíhá v souladu s výše uvedenou násobící tabulkou podle obvyklého schématu používaného v desítkové číselné soustavě se sekvenčním násobením násobitele číslicemi násobitele. Jako příklad vynásobme binární čísla a:

Divize. Operace dělení se provádí pomocí algoritmu podobného algoritmu pro provádění operace dělení v desítkové soustavě čísel. Jako příklad si rozdělme binární číslo 110 2 a 11 2: