Binarna aritmetika

Ime parametra	Pomen
Tema članka:	Binarna aritmetika
Rubrika (tematska kategorija)	Računalništvo

Dvojiški številski sistem

Sistemi števil, ki se uporabljajo pri delu z računalniki

Osnova P = 2. Abeceda vključuje dve dvojiški števki: 0, 1. Vsako število C = C n C n-1 ...C 1 C 0 C -1 C -m je vsota potenc števila 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

Primer 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.

Uteži števk v binarnem številskem sistemu so 1, 4, 8,16,... levo od decimalne vejice in 0,5; 0,25; 0,125; 0,625;... desno od decimalne vejice.

Včasih se uporablja pri programiranju šestnajstiško zapis. Za predstavitev števil, večjih od 9 v šestnajstiškem številskem sistemu, se uporabljajo latinične črke A, B, C, D, E, F. Slike prvih šestnajstih števil v decimalnem, dvojiškem in šestnajstiškem številskem sistemu so podane v tabeli. 2.

Kodna tabela v različne sisteme mrtvo obračunavanje

tabela 2

Decimalni sistem	Dvojiški sistem	Šestnajstiški sistem	Decimalni sistem	Dvojiški sistem	Šestnajstiški sistem
					A
					B
					C
					D
					E
					F

Binarno decimalnoŠtevilski sistem je postal zelo razširjen v sodobnih računalnikih zaradi enostavnosti pretvorbe v decimalni sistem in obratno. Uporablja se tam, kjer glavna pozornost ni namenjena preprostosti tehnične konstrukcije stroja, temveč udobju uporabnika. V tem številskem sistemu so vse decimalne števke ločeno kodirane s štirimi binarnimi števkami.

Primer 3.7.

Decimalno število 9703 v BCD izgleda takole: 1001 0111 0000 0011.

Prednost binarnega številskega sistema pred decimalnim številskim sistemom z vidika digitalnega računalnika je naslednja:

• potrebni so elementi z dvema stabilnima stanjema;
• aritmetične operacije so bistveno poenostavljene;
• 1,5-krat manj opreme;
• vam omogoča uporabo aparata matematične logike za analizo in sintezo vezij.

Slabosti binarnega številskega sistema so naslednje:

• velika dolžina zapisa števila;
• Pri vnosu in izpisu informacij je potrebna pretvorba v decimalni številski sistem.

Poglejmo, kako se izvajajo osnovne operacije v binarni aritmetiki.

Pravila aritmetike v vseh pozicijskih številskih sistemih so enaka, ᴛ.ᴇ. seštevanje, množenje in odštevanje se začnejo od najnižjih števk, deljenje - od najvišjih.

Pri seštevanju se prenosna enota doda števkam sosednje najpomembnejše števke. Ko se odšteje, dobi enota izposoje v najvišji števki dve enoti v najnižji sosednji števki.

Primer 3.8

Množenje binarnih števil je podobno množenju decimalnih števil, vendar ... Če množimo le z 0 in 1, potem se množenje zmanjša na operacijo premika in seštevanja.

Primer 3.9

Binarna aritmetika - pojem in vrste. Razvrstitev in značilnosti kategorije "Binarna aritmetika" 2017, 2018.

- Binarna aritmetika

Ker informacijskih procesov V digitalni sistemi vzemite vrednosti samo 0 in 1, potem se predstavitev podatkov izvede z uporabo binarnih števil. Seštevanje in odštevanje binarnih števil, kot tudi vse druge aritmetične operacije, se izvajajo po enakih pravilih kot... .

- Dvojiški številski sistem in binarna aritmetika

V binarnem številskem sistemu lahko s števili izvajate enake operacije kot v decimalnem številskem sistemu. Seštevanje poteka po istem principu kot v decimalnem številskem sistemu: le če dana cifra proizvede znesek, ki vanjo ne sodi, potem ...

, Natečaj "Predstavitev za lekcijo"

Predstavitev za lekcijo

Nazaj naprej

Pozor! Predogled Diapozitivi so zgolj informativne narave in morda ne predstavljajo vseh funkcij predstavitve. Če vas zanima to delo, prenesite polno različico.

Cilji lekcije: (diapozitiv 2)

1. Učence seznanite z dvojiškim številskim sistemom.
2. Razviti spretnosti pri izvajanju aritmetičnih operacij z binarnimi številkami

Med poukom

I. Začetek lekcije

Učitelj: Da bi bolje obvladali binarni številski sistem, morate obvladati izvajanje aritmetičnih operacij z binarnimi številkami.

Vsi pozicijski številski sistemi so "enaki", namreč v vseh se aritmetične operacije izvajajo po enakih pravilih:

• veljajo isti zakoni aritmetike: komutativni, asociativni, distributivni;
• veljajo pravila seštevanja, odštevanja, množenja in deljenja;
• Pravila za izvajanje aritmetičnih operacij temeljijo na tabelah seštevanja in množenja.

Poglejmo si pravila za izvajanje aritmetičnih operacij

II. Učenje nove snovi

Pri deljenju s stolpcem morate izvesti množenje in odštevanje kot vmesna rezultata. Toda v dvojiškem številskem sistemu so vmesna množenja zmanjšana na množenje delitelja z 0 ali 1, zato ostaja najtežja operacija odštevanje, ki se ga morate naučiti izvajati natančno.

III. Utrjevanje naučenega. (diapozitiv 12)

Fantje delo opravljajo sami. Nato odprite diapozitiv z odgovori.

odgovori. (Slide 13)

IV. Domača naloga (diapozitiv 14)

1. Naučite se pravil za izvajanje aritmetičnih operacij v dvojiškem številskem sistemu.

2. Sledite tem korakom:

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

domov \ Dokumentacija \ Za učitelja računalništva

Pri uporabi materialov s tega mesta - in postavitev transparenta je OBVEZNA!!!

Binarna aritmetika

Števila, ki smo jih navajeni uporabljati, se imenujejo decimalna in aritmetika, ki jo uporabljamo, se imenuje tudi decimalna. To je zato, ker je vsako število lahko sestavljeno iz niza številk, ki vsebuje 10 znakov - številk - "0123456789".

Matematika se je razvila tako, da je prav ta sklop postal glavni, a decimalna aritmetika ni edina. Če vzamemo le pet števk, lahko na njihovi podlagi sestavimo petmestno aritmetiko, iz sedmih števk pa sedemmestno aritmetiko. Na področjih znanja, povezanih z računalniška oprema Pogosto se uporablja aritmetika, pri kateri so števila sestavljena iz šestnajstih števk, zato se ta aritmetika imenuje šestnajstiška. Da bi razumeli, kaj je število v nedecimalni aritmetiki, najprej ugotovimo, kaj je število v decimalni aritmetiki.

Vzemimo za primer število 246. Ta zapis pomeni, da je v številu dve stotici, štiri desetice in šest enic. Zato lahko zapišemo naslednjo enakost:

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

Tukaj enačaji ločijo tri načine pisanja istega števila. Zdaj nam je najbolj zanimiva tretja oblika zapisa: 2 * 10 2 + 4 * 10 1 + 6 * 10 0 . Zgrajen je na naslednji način:

Naša številka je trimestna. Prva številka "2" je številka 3. Torej je pomnožena z 10 na drugo potenco. Naslednja številka "4" ima zaporedno številko 2 in je v prvi pomnožena z 10. Jasno je že, da se števke množijo z deset na potenco ena manj od zaporedne številke števke. Ko razumemo zgornje, lahko zapišemo splošno formulo za predstavitev decimalne številke. Naj bo podano število z N ciframi. Bomo označili i-ta številka skozi i. Potem lahko število zapišemo v naslednji obliki: a n a n-1 ....a 2 a 1 . To je prvi obrazec, tretji vpisni obrazec pa bo videti takole:

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

kjer je i znak iz niza "0123456789"

Na tem posnetku je zelo jasno vidna vloga desetke. Deset je osnova za nastanek števil. In mimogrede, imenuje se "osnova številskega sistema" in sam številski sistem je razlog, zakaj se imenuje "decimalni." Število deset seveda nima posebnih lastnosti. Deset lahko enostavno nadomestimo s katerim koli drugim številom. Na primer, številko v petmestnem številskem sistemu lahko zapišemo takole:

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

kjer je i znak iz niza "01234"

Na splošno 10 zamenjamo s katerim koli drugim številom in dobimo popolnoma drugačen številski sistem in drugačno aritmetiko. Najenostavnejšo aritmetiko dobimo, če 10 nadomestimo z 2. Nastali številski sistem imenujemo dvojiški in število v njem definiramo takole:

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

kjer je i znak iz niza "01"

Ta sistem je najenostavnejši od vseh možnih, saj je v njem poljubno število sestavljeno samo iz dveh števk 0 in 1. Jasno je, da bolj preprosto ne more biti. Primeri binarnih števil: 10, 111, 101.

Zelo pomembno vprašanje. Ali je mogoče dvojiško število predstaviti kot decimalno in obratno? decimalno število predstavi v binarni obliki.

Binarno v decimalno. Je zelo preprosto. Način takega prevajanja je podan z našim načinom zapisovanja številk. Vzemimo za primer naslednje binarno število 1011. Razširimo ga na potence dvojke. Dobimo naslednje:

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

Izvedimo vsa posneta dejanja in dobimo:

1 * 2 3 + 0 * 2 2 + 1 * 2 1 + 1 * 2 0 = 8 + 0+ 2 + 1 = 11. Tako dobimo, da je 1011 (binarno) = 11 (decimalno). Rahla nevšečnost binarnega sistema je vidna takoj. Enako število, ki je v decimalnem sistemu zapisano z eno števko v dvojiškem sistemu, zahteva za zapis štiri števke. Toda to je cena za preprostost (nič ni zastonj). Toda binarni sistem daje velik dobiček pri aritmetičnih operacijah. In to bomo videli kasneje.

Naslednja binarna števila izrazite kot decimalna.

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

Seštevanje binarnih števil.

Metoda seštevanja stolpcev je na splošno enaka kot pri decimalnem številu. To pomeni, da se seštevanje izvede bitno, začenši z najmanj pomembno števko. Če je pri seštevanju dveh števk SUM večji od devet, se zapiše števko = SUM - 10, v najpomembnejši števki pa se prišteje CELOTNI DEL (SUM / 10). (Dodajte nekaj števil v stolpec; zapomnite si, kako to storiti.) Enako z binarnim številom. Seštevajte eno za drugo, začenši z najnižjo števko. Če je rezultat večji od 1, se 1 zapiše in najpomembnejši številki doda 1 (pravijo »na pamet«).

Naredimo primer: 10011 + 10001.

Prva kategorija: 1+1 = 2. 0 in 1 zapišemo, kot nam pade na pamet.

Druga kategorija: 1+0+1(pomnjena enota) =2. Zapišemo 0 in 1, je prišlo na misel.

Tretja kategorija: 0+0+1(pomnjena enota) = 1. Zapišite 1.

Četrta kategorija 0+0=0. Pišemo 0.

Peta kategorija 1+1=2. Zapišemo 0 in šestemu mestu prištejemo 1.

Vsa tri števila pretvorimo v decimalni sistem in preverimo pravilnost seštevanja.

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 pravilna enakost

Primeri neodvisnih rešitev:

a) 11001 +101 =

b) 11001 +11001 =

c) 1001 + 111 =

e) 10011 + 101 =

e) 11011 + 1111 =

e) 11111 + 10011 =

Kako pretvoriti decimalno število v binarno. Naslednja operacija je odštevanje. Toda to operacijo bomo obravnavali nekoliko kasneje, zdaj pa bomo razmislili o metodi pretvorbe decimalne številke v binarno.

Če želite decimalno število pretvoriti v binarno, ga je treba razširiti na potenco dvojke. Če pa razširitev v potenco števila deset dobimo takoj, potem je treba malo razmisliti o tem, kako razširiti v potenco števila dva. Najprej si poglejmo, kako to storiti z izbirno metodo. Vzemimo decimalno število 12.

Prvi korak. 2 2 = 4, to ni dovolj. Tudi 2 3 = 8 ni dovolj, vendar je 2 4 = 16 že veliko. Zato pustimo 2 3 =8. 12 - 8 = 4. Zdaj ga morate predstaviti kot potenco dveh 4.

Drugi korak. 4 = 2 2 .

Potem je naše število 12 = 2 3 + 2 2. Najvišja števka ima številko 4, najvišja stopnja = 3, zato morajo obstajati izrazi s potencami dveh 1 in 0. Vendar jih ne potrebujemo, da se znebimo nepotrebnih stopinj in pustimo potrebne , zapišemo število takole: 1*2 3 + 1* 2 2 +0*2 1 + 0*2 0 = 1100 - to je dvojiška predstavitev števila 12. Zlahka opazimo, da je vsaka naslednja potenca največja potenca dvojke, ki je manjša od razloženega števila. Za utrditev metode si poglejmo še en primer. Številka 23.

1. korak. Najbližja potenca dvojke je 2 4 = 16. 23 -16 = 7.

2. korak. Najbližja potenca dvojke 2 2 = 4. 7 - 4 = 3

3. korak. Najbližja potenca dvojke 2 1 = 2. 3 - 2 = 1

Korak 4. Najbližja potenca dvojke 2 0 =1 1 - 1 =0

Dobimo naslednjo razširitev: 1*2 4 + 0*2 3 +1*2 2 +1*2 1 +1*2 0

In naše želeno binarno število je 10111

Zgoraj obravnavana metoda dobro reši problem, ki ji je dodeljen, vendar obstaja metoda, ki je algoritmizirana veliko bolje. Algoritem za to metodo je napisan spodaj:

Dokler je ŠTEVILO večje od nič, naredite

NASLEDNJA ŠTEVKA = ostanek ŠTEVILA deljeno z 2

ŠTEVILO = celo število ŠTEVILA deljeno z 2

Ko ta algoritem zaključi svoje delo, bo zaporedje izračunanih NASLEDNJIH ŠTEVK predstavljalo binarno število. Na primer, delajmo s številko 19.

ŠTEVILO začetka algoritma = 19

NASLEDNJA ŠTEVKA = 1

NASLEDNJA ŠTEVKA = 1

NASLEDNJA ŠTEVKA = 0

NASLEDNJA ŠTEVKA = 0

NASLEDNJA ŠTEVKA = 1

Tako imamo kot rezultat naslednje število 10011. Upoštevajte, da se obravnavani metodi razlikujeta v vrstnem redu, v katerem so pridobljene naslednje števke. Pri prvi metodi je prva prejeta številka najpomembnejša številka binarnega števila, pri drugi metodi pa je prva prejeta številka, nasprotno, najmanj pomembna.

Decimalna števila pretvorite v binarna na dva načina

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

Kako pretvoriti ulomek v decimalno število.

Znano je, da lahko vsako racionalno število predstavimo kot decimalni in navadni ulomek. Navadni ulomek, torej ulomek oblike A/B, je lahko pravilen in nepravilen. Ulomek se imenuje pravi, če A<В и неправильной если А>IN.

Če je racionalno število predstavljeno z nepravilnim ulomkom in je števec ulomka deljen z imenovalcem s celoto, potem je to racionalno število celo število, v vseh drugih primerih pa se pojavi ulomek. Ulomek je pogosto zelo dolgo število in celo neskončno (neskončen periodični ulomek, na primer 20/6), zato v primeru ulomka nimamo le naloge prevajanja ene predstavitve v drugo, temveč prevajanje z določena natančnost.

Pravilo točnosti. Recimo, da vam je dano decimalno število, ki ga je mogoče predstaviti kot decimalni ulomek z natančnostjo N števk. Da bi bilo ustrezno binarno število enako natančno, je treba vanj vpisati M - znake, tako da

Zdaj pa poskusimo dobiti pravilo prevajanja in najprej si oglejmo primer 5401

rešitev:

Celo število bomo dobili po že znanih pravilih in je enako binarnemu številu 101. Ulomek pa bomo razširili na potence števila 2.

Korak 1: 2 -2 = 0,25; 0,401 - 0,25 = 0,151. - to je ostanek.

2. korak: Zdaj moramo 0,151 predstaviti kot potenco dvojke. Naredimo tole: 2 -3 = 0,125; 0,151 - 0,125 = 0,026

Tako lahko prvotni ulomek predstavimo kot 2 -2 +2 -3. Enako lahko zapišemo v to binarno število: 0,011. Prva ulomka je nič, to je zato, ker v naši razširitvi ni stopnje 2 -1.

Iz prvega in drugega koraka je jasno, da ta predstavitev ni točna in bi bilo morda zaželeno nadaljevati širitev. Poglejmo pravilo. Pravi, da potrebujemo toliko znakov za M, da je 10 3 manj kot 2 M. To je 1000<2 M . То есть в двоичном разложении у нас должно быть не менее десяти знаков, так как 2 9 = 512 и только 2 10 = 1024. Продолжим процесс.

3. korak: Zdaj delamo s številko 0,026. Najbližja potenca dvojke temu številu je 2 -6 = 0,015625; 0,026 - 0,015625 = 0,010375 Zdaj je naše natančnejše binarno število: 0,011001. Za decimalno vejico je že šest mest, a to še ni dovolj, zato naredimo še en korak.

4. korak: Zdaj delamo s številko 0,010375. Najbližja potenca dvojke temu številu je 2 -7 = 0,0078125;

0,010375 - 0,0078125 = 0,0025625

5. korak: Zdaj delamo s številko 0,0025625. Najbližja potenca dvojke temu številu je 2 -9 = 0,001953125;

0,0025625 - 0,001953125 = 0,000609375

Zadnji nastali ostanek je manjši od 2 -10 in če bi želeli nadaljevati s približevanjem prvotnemu številu, bi potrebovali 2 -11, vendar to že presega zahtevano natančnost, zato se lahko izračuni ustavijo in končna binarna predstavitev ulomek lahko zapišemo.

0,401 = 0,011001101

Kot lahko vidite, je pretvorba ulomka decimalnega števila v dvojiško nekoliko bolj zapletena kot pretvorba celega dela. Tabela potence dvojke na koncu predavanja.

Zdaj pa zapišimo algoritem pretvorbe:

Začetni podatki algoritma: Z A bomo označili prvotni pravi decimalni ulomek, zapisan v decimalni obliki. Naj ta ulomek vsebuje N znakov.

Algoritem

Ukrep 1. Določite število zahtevanih binarnih števk M iz neenačbe 10 N< 2 M

Akcija 2: Cikel za izračun števk binarne predstavitve (števke za ničlo). Številčno številko bomo označili s simbolom K.

1. Številka = 1
2. Če je 2 -K > A

Nato binarnemu številu dodamo ničlo

• binarnemu številu dodajte 1
• A = A - 2 -K

1. K = K + 1
2. Če je K > M

• potem je algoritem zaključen
• V nasprotnem primeru pojdite na točko 2.

Pretvarjanje decimalnih števil v binarna

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

Odštevanje binarnih števil. Števila bomo odštevali tudi v stolpcu, splošno pravilo pa je enako kot pri decimalnih številih, odštevanje poteka bit za bit in če ni dovolj enega na mestu, se izvede v najvišjem. Rešimo naslednji primer:

Prva kategorija. 1 - 0 =1. Zapišemo 1.

Druga kategorija 0 -1. Eden manjka. Zasedamo jo v starejši kategoriji. Enota iz starejše števke gre v mlajšo, kot dve enoti (ker je starejša števka predstavljena z dvojko višje stopnje) 2-1 = 1. Zapišemo 1.

Tretja kategorija. Enoto tega ranga smo zasedli, zato je sedaj v rangu 0 treba zasesti enoto najvišjega ranga. 2-1 =1. Zapišemo 1.

Preverimo rezultat v decimalnem sistemu

1101 - 110 = 13 - 6 = 7 (111) Pravilna enakost.

Drug zanimiv način izvajanja odštevanja vključuje koncept kode komplementa dveh, ki vam omogoča, da zmanjšate odštevanje na seštevanje. Rezultat števila v kodi komplementa dvojke je zelo preprost: vzamemo število, ničle zamenjamo z enicami, nasprotno, enice zamenjamo z ničlami ​​in najmanj pomembno števko dodamo ena. Na primer 10010, dodatna koda bo 011011.

Pravilo odštevanja prek komplementa dvojke pravi, da lahko odštevanje nadomestimo s seštevanjem, če odštevanec nadomestimo s številom v komplementu dvojke.

Primer: 34 - 22 = 12

Zapišimo ta primer v dvojiški obliki. 100010 - 10110 = 1100

Dodatna koda številke 10110 bo takšna

01001 + 00001 = 01010. Nato lahko izvirni primer nadomestite s seštevanjem, kot je ta: 100010 + 01010 = 101100 Nato morate zavreči eno enoto v najpomembnejši števki. Če to naredimo, dobimo 001100. Zavrzimo nepomembne ničle in dobimo 1100, se pravi, primer je bil pravilno rešen

Izvedite odštevanja. Na običajen način in v dodatni kodi, po predhodni pretvorbi decimalnih števil v binarne:

Preverite tako, da binarni rezultat pretvorite v decimalni številski sistem.

Množenje v dvojiškem številskem sistemu.

Najprej razmislite o naslednjem zanimivem dejstvu. Da bi binarno število pomnožili z 2 (decimalna dve je v binarnem sistemu 10), je dovolj, da dodate eno ničlo levo od števila, ki ga množite.

Primer. 10101 * 10 = 101010

Pregled.

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

Če se spomnimo, da je katero koli binarno število mogoče razširiti na potenco dvojke, potem postane jasno, da je množenje v binarnem številskem sistemu zmanjšano na množenje z 10 (to je z decimalno 2), zato je množenje niz zaporednih izmene. Splošno pravilo je, da se binarno množenje, tako kot pri decimalnih številih, izvede bitno. In za vsako števko drugega množitelja se desno od prvega množitelja doda ena ničla. Primer (še ni v stolpcu):

1011 * 101 To množenje lahko zmanjšamo na vsoto trimestnega množenja:

1011 * 1 + 1011 * 0 + 1011 * 100 = 1011 +101100 = 110111 Enako lahko zapišemo v stolpec, kot je ta:

Pregled:

101 = 5 (decimalno)

1011 = 11 (decimalno)

110111 = 55 (decimalno)

5*11 = 55 pravilna enakost

Odločite se sami

a) 1101 * 1110 =

b) 1010 * 110 =

e) 101011 * 1101 =

e) 10010 * 1001 =

Opomba: Mimogrede, tabela množenja v dvojiškem sistemu je sestavljena iz samo enega elementa 1 * 1 = 1

Deljenje v dvojiškem številskem sistemu.

Ogledali smo si že tri dejanja in mislim, da je že jasno, da se dejanja na binarnih številih na splošno malo razlikujejo od dejanj na decimalnih številih. Edina razlika je v tem, da sta števili dve in ne deset, kar pa le poenostavi računske operacije. Enako je z deljenjem, vendar bomo za boljše razumevanje podrobneje analizirali algoritem deljenja. Recimo, da moramo razdeliti dve decimalni števili, na primer 234 deljeno s 7. Kako to naredimo.

Desno (od najpomembnejše števke) izberemo toliko števk, da je dobljeno število čim manjše in hkrati večje od delitelja. 2 manjše od delitelja, zato je potrebno število 23. Nato dobljeno število delimo z deliteljem z ostankom. Dobimo naslednji rezultat:

Opisano operacijo ponavljamo, dokler dobljeni ostanek ni manjši od delitelja. Ko se to zgodi, je število, dobljeno pod črto, količnik, zadnji ostanek pa ostanek operacije. Torej se operacija deljenja binarnega števila izvede na povsem enak način. Poskusimo

primer: 10010111 / 101

Iščemo število, katerega prva števka je večja od delitelja. To je štirimestno število 1001. Označeno je v krepkem tisku. Zdaj morate najti delitelj za izbrano število. In tu spet zmagamo v primerjavi z decimalnim sistemom. Dejstvo je, da je izbrani delitelj nujno število, mi pa imamo le dve števili. Ker je 1001 očitno večje od 101, je z deliteljem vse jasno: 1. Izvedemo operacijski korak.

Torej je preostanek dokončane operacije 100. To je manj kot 101, zato morate za izvedbo drugega koraka deljenja 100 dodati naslednjo številko, to je številka 0. Zdaj imamo naslednje število:

1000 je večje od 101, zato bomo v drugem koraku k količniku spet prišteli število 1 in dobili naslednji rezultat (zaradi prihranka prostora bomo naslednjo števko takoj izpustili).

Tretji korak. Dobljeno število 110 je večje od 101, zato bomo v tem koraku v količnik vpisali 1. Izpadlo bo takole:

Dobljeno število 11 je manjše od 101, zato v količnik zapišemo število 0 in naslednje število znižamo navzdol. Izkazalo se je takole:

Dobljeno število je večje od 101, zato število 1 zapišemo v količnik in ponovimo dejanja. Izkazalo se je ta slika:

1

0

Dobljeni ostanek 10 je manjši od 101, vendar nam je v dividendi zmanjkalo števk, tako da je 10 končni ostanek, 1110 pa zahtevani količnik.

Preverimo decimalna števila

S tem se zaključi opis najpreprostejših aritmetičnih operacij, ki jih morate poznati za uporabo binarne aritmetike, zdaj pa bomo poskušali odgovoriti na vprašanje "Zakaj je potrebna binarna aritmetika?" Seveda je bilo že zgoraj pokazano, da zapis števila v dvojiškem sistemu bistveno poenostavi aritmetične operacije, hkrati pa se sam zapis precej podaljša, kar zmanjša vrednost nastale poenostavitve, zato je treba iskati problemi, katerih rešitev je veliko enostavnejša v binarnih številih.

Naloga 1: Pridobivanje vseh vzorcev

Zelo pogosto obstajajo težave, pri katerih morate biti sposobni sestaviti vse možne kombinacije iz danega nabora predmetov. Na primer, ta naloga:

Glede na velik kup kamnov razporedite kamne v dva kupa tako, da bo masa teh dveh kupov čim bolj enaka.

To nalogo je mogoče formulirati na naslednji način:

Poiščite izbor kamnov iz velikega kupa tako, da se njegova skupna masa čim manj razlikuje od polovice mase velikega kupa.

Tovrstnih nalog je kar nekaj. In vse se spuščajo, kot že rečeno, v zmožnost pridobitve vseh možnih kombinacij (v nadaljevanju jih bomo imenovali vzorci) iz dane množice elementov. In zdaj si bomo ogledali splošno metodo pridobivanja vseh možnih vzorcev z uporabo operacije binarnega dodajanja. Začnimo s primerom. Naj obstaja niz treh predmetov. Sestavimo vse možne vzorce. Predmete bomo označevali z zaporednimi številkami. To pomeni, da obstajajo naslednji elementi: 1, 2, 3.

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

Če je položaj z naslednjo številko ena, to pomeni, da je v izboru prisoten element s številko, ki je enaka temu položaju, in če je ničla, elementa ni. Na primer vzorec (0, 1, 0); je sestavljen iz enega elementa s številko 2, izbor pa je (1, 1, 0); je sestavljen iz dveh elementov s številkama 1 in 2.

Ta primer jasno kaže, da je vzorec mogoče predstaviti kot binarno število. Poleg tega je enostavno videti, da so zgoraj zapisana vsa možna eno-, dvo- in trimestna binarna števila. Prepišimo jih takole:

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

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

Prejeli smo niz zaporednih binarnih števil, od katerih je vsako pridobljeno iz prejšnjega z dodajanjem ena. To lahko preverite. Z uporabo tega opaženega vzorca lahko sestavimo naslednji algoritem za pridobivanje vzorcev.

Vhodni podatki algoritma

Podan niz predmetov N - kosov. V nadaljevanju bomo to množico imenovali množica začetnih elementov. Oštevilčimo vse elemente prvotne množice od 1 do N. Sestavimo binarno število iz N nepomembnih ničel. 0000… 0 N To ničelno binarno število bo označevalo ničelni vzorec, s katerim se bo začel postopek vzorčenja. Števke števila se štejejo od desne proti levi, kar pomeni, da je skrajna leva številka najpomembnejša.

Dogovorimo se, da to binarno število označimo z velikimi črkami BINARNA

Algoritem

Če je BINARNA številka v celoti sestavljena iz enic

Nato ustavimo algoritem

• BINARNEMU številu dodamo ena po pravilih binarne aritmetike.
• Iz dobljenega BINARNEGA števila naredimo naslednji vzorec, kot je opisano zgoraj.

Problem 2: Iskanje velikih praštevil

Za začetek si zapomnimo, da je praštevilo naravno število, ki je deljivo le z 1 in samim seboj. Primeri praštevil: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

Iskanje velikih praštevil je zelo pomemben matematični problem. Velika praštevila so potrebna za nekatere algoritme šifriranja za varno šifriranje sporočil. Poleg tega niso potrebna le velika števila, ampak zelo velika. Večje kot je število, bolj zanesljiva je šifra, zgrajena na tem številu.

Opomba. Močna šifra je šifra, katere dešifriranje traja zelo dolgo.

Zakaj? Praštevilo deluje kot ključ za šifriranje in dešifriranje. Poleg tega vemo, da se praštevila pojavljajo v seriji naravna števila ne prepogosto. Med prvimi tisoč jih je precej, nato pa njihovo število začne hitro upadati. Če torej za ključ vzamemo ne zelo veliko število, dešifrer s pomočjo niti ne zelo velikega hiter računalnik bo lahko prišel do njega (tako da bo preizkusil vse preproste kot ključ enega za drugim) v omejenem času.

Precej zanesljivo kodo lahko dobite, če vzamete preprosto, na primer 150 znakov. Vendar najti tako preprostega ni tako enostavno. Recimo, da je treba za določeno število A (zelo veliko) preveriti primalnost. To je enako, kot če bi iskali njegove delitelje. Če lahko najdemo delitelje v območju od 2 do kvadratnega korena iz A, potem ni praštevilo. Ocenimo število števil, ki jih je treba preizkusiti za sposobnost deljenja števila A.

Recimo, da ima številka A 150 števk. Njegov kvadratni koren bo vseboval vsaj 75 znakov. Za naštevanje takšnega števila možnih deliteljev bomo potrebovali zelo močan računalnik in ogromno časa, kar pomeni, da je problem praktično nerešljiv.

Kako ravnati s tem.

Prvič, lahko se naučite hitro preveriti deljivost enega števila z drugim, in drugič, lahko poskusite izbrati število A tako, da je praštevilo z visoko stopnjo verjetnosti. Izkazalo se je, da je to mogoče. Matematik Mersen je odkril, da so števila naslednje oblike

So enostavni z visoko stopnjo verjetnosti.

Da bi razumeli zgoraj napisano besedno zvezo, preštejmo, koliko praštevil je v prvi tisočici in koliko Mersenovih praštevil je v isti tisočici. Mersenove številke v prvih tisoč so torej naslednje:

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;

Praštevila so označena s krepkim tiskom. Obstaja 5 praštevil za 9 Mersenovih števil. V odstotkih je to 5/9*100 = 55,6 %. Hkrati je na vsakih 1000 prvih naravnih števil samo 169 praštevil. V odstotkih je to 169/1000*100 = 16,9 %. To pomeni, da so praštevila med Mersenovimi števili v odstotkih v prvih tisočih skoraj 4-krat pogostejša kot med preprostimi naravnimi števili.

___________________________________________________________

Zdaj pa vzemimo specifično Mersenovo število, na primer 2 4 - 1. Zapišimo ga kot binarno število.

2 4 - 1 = 10000 - 1 = 1111

Vzemimo naslednje Mersenovo število 2 5 -1 in ga zapišimo kot binarno število. Dobimo naslednje:

2 5 -1 = 100000 - 1 = 11111

Jasno je že, da so vsa Mersenova števila zaporedje enic in to samo po sebi daje velik dobiček. Prvič, v dvojiškem številskem sistemu je zelo preprosto dobiti naslednje Mersenovo število, samo dodajte eno naslednjemu številu, in drugič, iskanje deliteljev v dvojiškem sistemu je veliko lažje kot v decimalnem sistemu.

Hitra decimalna pretvorba v dvojiško

Ena glavnih težav pri uporabi binarnega številskega sistema je težava pri pretvorbi decimalnih števil v dvojiške. To je precej delovno intenzivna naloga. Seveda ni težko prevesti majhnih tri- ali štirimestnih številk, toda za decimalna števila s 5 ali več števkami je to že težko. To pomeni, da potrebujemo način za hitro pretvorbo velikih decimalnih števil v dvojiška.

To metodo je izumil francoski matematik Legendre. Naj nam bo na primer dano število 11183445. Delimo ga s 64, dobimo ostanek 21 in količnik je 174741. To število ponovno delimo s 64, dobimo ostanek 21 in količnik 2730. Končno , 2730 deljeno s 64 daje ostanek 42 in količnik 42. Vendar je 64 v binarnem sistemu 1000000, 21 v binarnem sistemu je 10101 in 42 je 101010. Zato je prvotno število zapisano v binarnem sistemu, kot sledi:

101010 101010 010101 010101

Da bo bolj jasno, je tukaj še en primer z manjšo številko. Pretvorimo dvojiško predstavitev števila 235. 235 delimo s 64 z ostankom. Dobimo:

QUANTIATE = 3, binarno 11 ali 000011

REMAINDER = 43, binarno 101011

Potem je 235 = 11101011. Preverimo ta rezultat:

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

Opombe:

1. Preprosto je videti, da končno binarno število vključuje vse ostanke in na zadnjem koraku tako ostanek kot količnik.
2. Količnik je zapisan pred ostankom.
3. Če ima dobljeni količnik ali ostanek manj kot 6 števk v binarni predstavitvi (6 ničel vsebuje binarno predstavitev števila 64 = 1000000), se mu dodajo nepomembne ničle.

In še en bolj zapleten primer. Številka je 25678425.

1. korak: 25678425 deljeno s 64

Zasebno = 401225

Preostalo = 25 = 011001

2. korak: 401225 deljeno s 64

Kvocient = 6269

Ostanek = 9 = 001001

3. korak: 6269 deljeno s 64

Kvocient = 97

Preostalo = 61 = 111101

4. korak: 97 deljeno s 64

Kvocient = 1 = 000001

Preostalo = 33 = 100001

Rezultat števila = 1,100001,111101,001001,011001

V tej številki so vanjo vključeni vmesni rezultati ločeni s piko.

Pretvori števila v binarno predstavitev:

PRILOGA: TABELA 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

Izvajanje aritmetičnih operacij v katerem koli pozicijskem številskem sistemu se izvaja po enakih pravilih, ki se uporabljajo v decimalnem številskem sistemu.

Tako kot v decimalnem številskem sistemu morate za izvajanje aritmetičnih operacij poznati tabelo seštevanja (odštevanja) in množenja.

Tabela seštevanja, odštevanja in množenja za dvojiški številski sistem

Seštevanje binarnih števil

Seštevanje v dvojiškem številskem sistemu poteka po enakih pravilih kot v decimalnem številskem sistemu. Dve števili sta zapisani v stolpcu poravnani z ločilom celega in ulomka in po potrebi dopolnjeni na desni strani z nepomembnimi ničlami. Seštevanje se začne od skrajne desne števke. Dve enoti nižjega reda sta združeni v enoto višjega reda.

primer: 1011,1 2 + 1010,11 2

Zanimiva je tudi situacija, ko seštejemo več kot dve števili. V tem primeru je možen prenos preko več števk.
primer: 111,1 2 + 111 2 + 101,1 2

Pri seštevanju na mestu enic (bit 0) so 4 enice, ki, če jih združimo, dajo 100 2 . Zato se iz ničelne števke prenese na prvo števko 0 , v drugem pa - 1 .
Podobno se pojavi pri drugi števki, kjer ob upoštevanju dveh prenesenih enot dobimo številko 5 = 101 2 . 1 ostaja v drugi kategoriji, 0 prenesel v tretje in 1 prenese v četrto.

Odštevanje binarnih števil

V primerih, ko je angažirana enota starejše kategorije, daje dve enoti mlajše kategorije. Če se enota preučuje po več kategorijah, potem daje eno enoto v vseh vmesnih ničelnih kategorijah in dve enoti v kategoriji, za katero se preučuje.
primer: 10110,01 2 — 1001,1 2

Aritmetične operacije v vseh pozicijskih številskih sistemih se izvajajo po istih pravilih, ki so vam dobro znana.

Dodatek. Razmislimo o seštevanju števil v dvojiškem številskem sistemu. Temelji na tabeli za seštevanje enomestnih binarnih števil :

Pomembno je biti pozoren na dejstvo, da se pri seštevanju dveh enic števka prelije in prenese na najpomembnejšo cifro. Do presežka številk pride, ko vrednost števila v njem postane enaka ali večja od osnove.

Seštevanje večbitnih binarnih števil poteka v skladu z zgornjo tabelo seštevanja, pri čemer se upoštevajo možni prenosi iz nižjih v višje številke.

Na primer, dodajmo binarni števili 110 2 in 11 2 v stolpec :

Preverimo pravilnost izračunov s seštevanjem v decimalnem številskem sistemu. Pretvorimo binarna števila v decimalni številski sistem in jih nato seštejmo:

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 .

Zdaj pa pretvorimo rezultat binarnega seštevanja v decimalno število:

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

Primerjajmo rezultate – seštevanje je bilo izvedeno pravilno.

Odštevanje. Poglejmo odštevanje binarnih števil. Temelji na tabeli za odštevanje enomestnih binarnih števil. Pri odštevanju večjega števila (1) od manjšega števila (0) se izposoja iz najvišje števke. Posojilo je v tabeli označeno s črto 1 s črto:

Odštevanje večbitnih binarnih števil poteka v skladu z zgornjo tabelo odštevanja, ob upoštevanju možnih izposoj iz najpomembnejših bitov. Kot primer odštejmo dvojiški števili 110 2 in 11 2:

Množenje. Množenje temelji na tabeli množenja za enomestna binarna števila:

Množenje večmestnih binarnih števil poteka v skladu z zgornjo tabelo množenja po običajni shemi, ki se uporablja v decimalnem številskem sistemu z zaporednim množenjem množitelja s števkami množitelja. Na primer, pomnožimo binarna števila in:

Delitev. Operacija deljenja poteka po algoritmu, podobnem algoritmu za izvedbo operacije deljenja v decimalnem številskem sistemu. Na primer, razdelimo binarno število 110 2 in 11 2: