Binarna aritmetika

Naziv parametra	Značenje
Tema članka:	Binarna aritmetika
Rubrika (tematska kategorija)	Računarska nauka

Binarni sistem brojeva

Sistemi brojeva koji se koriste pri radu sa računarima

Baza P = 2. Abeceda uključuje dvije binarne cifre: 0, 1. Bilo koji broj C = C n C n-1 ...C 1 C 0 C -1 C -m je zbir stepena broja 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

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

Težine cifara u binarnom brojevnom sistemu su 1, 4, 8,16,... lijevo od decimalnog zareza i 0,5; 0,25; 0,125; 0,625;... desno od decimalnog zareza.

Ponekad se koristi u programiranju heksadecimalni notacija. Za predstavljanje brojeva većih od 9 u heksadecimalnom brojevnom sistemu koriste se latinična slova A, B, C, D, E, F. Slike prvih šesnaest brojeva u decimalnom, binarnom i heksadecimalnom sistemu brojeva date su u tabeli. 2.

Tabela kodova u razni sistemi mrtvo računanje

tabela 2

Decimalni sistem	Binarni sistem	Heksadecimalni sistem	Decimalni sistem	Binarni sistem	Heksadecimalni sistem
					A
					B
					C
					D
					E
					F

Binarni decimalni Brojevni sistem je postao široko rasprostranjen u modernim računarima zbog lakoće konverzije u decimalni sistem i obrnuto. Koristi se tamo gdje se glavna pažnja posvećuje ne jednostavnosti tehničke konstrukcije stroja, već praktičnosti korisnika. U ovom brojevnom sistemu, sve decimalne cifre su zasebno kodirane sa četiri binarne cifre.

Primjer 3.7.

Decimalni broj 9703 u BCD-u izgleda ovako: 1001 0111 0000 0011.

Prednost binarnog sistema brojeva u odnosu na decimalni brojevni sistem sa stanovišta digitalnog računara je sledeća:

• potrebni su elementi sa dva stabilna stanja;
• aritmetičke operacije su značajno pojednostavljene;
• potrebno je 1,5 puta manje opreme;
• omogućava vam korištenje aparata matematičke logike za analizu i sintezu sklopova.

Nedostaci binarnog sistema brojeva su sljedeći:

• dužina snimanja velikog broja;
• Prilikom unosa i izlaza informacija potrebna je konverzija u decimalni brojevni sistem.

Pogledajmo kako se osnovne operacije izvode u binarnoj aritmetici.

Pravila aritmetike u svim pozicionim brojevnim sistemima su ista, ᴛ.ᴇ. sabiranje, množenje i oduzimanje počinju od najnižih cifara, dijeljenje - od najviših.

Prilikom sabiranja, jedinica za nošenje se dodaje ciframa susjedne najznačajnije cifre. Kada se oduzme, jedinica posudbe u najvišoj znamenki daje dvije jedinice u najnižoj susjednoj cifri.

Primjer 3.8

Množenje binarnih brojeva je slično množenju decimalnih brojeva, ali... Ako pomnožimo samo sa 0 i 1, tada se množenje svodi na operaciju pomaka i sabiranja.

Primjer 3.9

Binarna aritmetika - pojam i vrste. Klasifikacija i karakteristike kategorije "Binarna aritmetika" 2017, 2018.

- Binarna aritmetika

Jer informacionim procesima V digitalni sistemi uzimaju vrijednosti samo 0 i 1, a zatim se predstavljanje podataka vrši pomoću binarnih brojeva. Sabiranje i oduzimanje binarnih brojeva, kao i sve ostale računske operacije, izvode se po istim pravilima kao... .

- Binarni brojevni sistem i binarna aritmetika

U binarnom brojevnom sistemu možete izvršiti iste operacije sa brojevima kao i u decimalnom brojevnom sistemu. Sabiranje se vrši po istom principu kao u decimalnom brojevnom sistemu: samo ako data cifra daje iznos koji se u njega ne uklapa, onda...

, Takmičenje "Prezentacija za čas"

Prezentacija za lekciju

Nazad napred

Pažnja! Pregled Slajdovi su samo u informativne svrhe i možda ne predstavljaju sve karakteristike prezentacije. Ako si zainteresovan ovo djelo, preuzmite punu verziju.

Ciljevi lekcije: (slajd 2)

1. Upoznati učenike sa binarnim brojevnim sistemom.
2. Razvijati vještine izvođenja aritmetičkih operacija s binarnim brojevima

Tokom nastave

I. Početak časa

Nastavnik: Da biste bolje savladali binarni brojevni sistem, potrebno je savladati izvođenje aritmetičkih operacija nad binarnim brojevima.

Svi pozicioni brojevni sistemi su „isti“, naime, u svima se aritmetičke operacije izvode po istim pravilima:

• važe isti zakoni aritmetike: komutativni, asocijativni, distributivni;
• važe pravila sabiranja, oduzimanja, množenja i dijeljenja;
• Pravila za izvođenje aritmetičkih operacija zasnivaju se na tablicama sabiranja i množenja.

Pogledajmo pravila za izvođenje aritmetičkih operacija

II. Učenje novog gradiva

Prilikom dijeljenja kolonom, morate izvršiti množenje i oduzimanje kao međurezultate. Ali u binarnom brojevnom sistemu, posredna množenja se svode na množenje djelitelja sa 0 ili 1, tako da najteža operacija ostaje oduzimanje, koje morate naučiti da radite tačno.

III. Konsolidacija naučenog. (slajd 12)

Momci sami rade posao. Zatim otvorite slajd sa odgovorima.

Odgovori. (Slajd 13)

IV. Domaći (slajd 14)

1. Naučite pravila za izvođenje aritmetičkih operacija u binarnom brojevnom sistemu.

2. Slijedite ove korake:

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

Dom \ Dokumentacija \ Za nastavnika informatike

Kada koristite materijale sa ove stranice - a postavljanje banera OBAVEZNO!!!

Binarna aritmetika

Brojevi koje smo navikli koristiti se nazivaju decimalni, a aritmetika koju koristimo se također naziva decimalna. To je zato što se svaki broj može sastaviti od skupa brojeva koji sadrže 10 znakova - brojeva - "0123456789".

Matematika se razvila na način da je upravo ovaj skup postao glavni, ali decimalna aritmetika nije jedina. Ako uzmemo samo pet cifara, onda na osnovu njih možemo konstruisati petocifrenu aritmetiku, a od sedam cifara - sedmocifrenu. U oblastima znanja vezanih za kompjuterska opremaČesto se koristi aritmetika u kojoj se brojevi sastoje od šesnaest cifara; u skladu s tim, ova aritmetika se naziva heksadecimalna. Da bismo razumjeli šta je broj u nedecimalnoj aritmetici, prvo saznamo šta je broj u decimalnoj aritmetici.

Uzmimo, na primjer, broj 246. Ovaj zapis znači da u broju ima dvije stotine, četiri desetice i šest jedinica. Stoga možemo napisati sljedeću jednakost:

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

Ovdje znakovi jednakosti razdvajaju tri načina pisanja istog broja. Treći oblik notacije nam je sada najzanimljiviji: 2 * 10 2 + 4 * 10 1 + 6 * 10 0 . Strukturiran je na sljedeći način:

Naš broj ima tri cifre. Vodeća znamenka "2" je broj 3. Dakle, množi se sa 10 na drugi stepen. Sljedeća cifra "4" ima serijski broj 2 i u prvoj se množi sa 10. Već je jasno da se cifre množe sa deset na stepen jedan manji od serijskog broja cifre. Pošto smo razumjeli gore navedeno, možemo zapisati opću formulu za predstavljanje decimalnog broja. Neka nam je zadan broj sa N cifara. Mi ćemo označiti i-ta cifra kroz i. Tada se broj može napisati u sljedećem obliku: a n a n-1 ....a 2 a 1 . Ovo je prvi obrazac, a treći obrazac za prijavu će izgledati ovako:

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

gdje je a i znak iz skupa "0123456789"

Uloga desetorice je vrlo jasno vidljiva na ovom snimku. Deset je osnova za formiranje brojeva. Uzgred, zove se „baza brojevnog sistema“, a sam sistem brojeva je razlog zašto se zove „decimalni“. Naravno, broj deset nema nikakva posebna svojstva. Lako možemo zamijeniti deset bilo kojim drugim brojem. Na primjer, broj u petocifrenom brojevnom sistemu može se napisati ovako:

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

gdje je a i znak iz skupa "01234"

Općenito, zamjenjujemo 10 bilo kojim drugim brojem i dobijamo potpuno drugačiji brojevni sistem i drugačiju aritmetiku. Najjednostavnija aritmetika se dobija ako se 10 zameni sa 2. Rezultujući sistem brojeva naziva se binarni i broj u njemu je definisan na sledeći način:

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

gdje je a i znak iz skupa "01"

Ovaj sistem je najjednostavniji od svih mogućih, jer se u njemu svaki broj formira samo od dvije cifre 0 i 1. Jasno je da jednostavniji ne može biti. Primjeri binarnih brojeva: 10, 111, 101.

Veoma važno pitanje. Da li je moguće predstaviti binarni broj kao decimalni broj i obrnuto? decimalni broj predstavljaju ga u binarnom obliku.

Binarno u decimalno. Vrlo je jednostavno. Način ovakvog prevođenja je dat našim načinom pisanja brojeva. Uzmimo, na primjer, sljedeći binarni broj 1011. Proširimo ga na stepen dvojke. Dobijamo sljedeće:

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

Izvršimo sve snimljene radnje i dobijemo:

1 * 2 3 + 0 * 2 2 + 1 * 2 1 + 1 * 2 0 = 8 + 0+ 2 + 1 = 11. Dakle, dobijamo da je 1011 (binarni) = 11 (decimalno). Odmah je vidljiva mala neugodnost binarnog sistema. Isti broj, koji je zapisan u decimalnom sistemu sa jednom cifrom u binarnom sistemu, zahteva četiri cifre za svoj zapis. Ali ovo je cijena za jednostavnost (ništa nije besplatno). Ali binarni sistem daje ogroman dobitak u aritmetičkim operacijama. A to ćemo vidjeti kasnije.

Izrazite sljedeće binarne brojeve kao decimalu.

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

Sabiranje binarnih brojeva.

Metoda sabiranja stupaca je općenito ista kao i za decimalni broj. To jest, sabiranje se vrši po bitovima, počevši od najmanje značajnog znamenka. Ako je pri sabiranju dvije cifre ZBIR veći od devet, tada se upisuje cifra = ZBIR - 10, a CIJELI DIO (SUM / 10) se dodaje u najznačajnijoj cifri. (Dodajte nekoliko brojeva u kolonu, zapamtite kako se to radi.) Isto i sa binarnim brojem. Dodajte jedno po jedno, počevši od najniže znamenke. Ako je rezultat veći od 1, tada se zapisuje 1 i 1 se dodaje najznačajnijoj cifri (kažu „iz glave“).

Uradimo primjer: 10011 + 10001.

prva kategorija: 1+1 = 2. Pišemo 0 i 1 kako vam padne na pamet.

Druga kategorija: 1+0+1(memorisana jedinica) =2. Zapišemo 0 i 1, palo nam je na pamet.

Treća kategorija: 0+0+1 (zapamćena jedinica) = 1. Upišite 1.

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

Peta kategorija 1+1=2. Zapisujemo 0 i dodajemo 1 šestoj cifri.

Pretvorimo sva tri broja u decimalni sistem i provjerimo ispravnost sabiranja.

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 tačna jednakost

Primjeri za nezavisna rješenja:

a) 11001 +101 =

b) 11001 +11001 =

c) 1001 + 111 =

e) 10011 + 101 =

e) 11011 + 1111 =

e) 11111 + 10011 =

Kako pretvoriti decimalni broj u binarni. Sljedeća operacija je oduzimanje. Ali ovom operacijom ćemo se pozabaviti malo kasnije, a sada ćemo razmotriti metodu pretvaranja decimalnog broja u binarni.

Da bi se decimalni broj pretvorio u binarni, on se mora proširiti na stepen dvojke. Ali ako se ekspanzija u stepenu deset dobije odmah, onda je potrebno malo razmisliti o tome kako proširiti po stepenima dva. Prvo, pogledajmo kako to učiniti pomoću metode odabira. Uzmimo decimalni broj 12.

Prvi korak. 2 2 = 4, ovo nije dovoljno. Takođe 2 3 = 8 nije dovoljno, ali 2 4 = 16 je već mnogo. Dakle, ostavljamo 2 3 =8. 12 - 8 = 4. Sada ga trebate predstaviti kao stepen dva 4.

Drugi korak. 4 = 2 2 .

Tada je naš broj 12 = 2 3 + 2 2. Najviša cifra ima broj 4, najviši stepen = 3, dakle, moraju postojati članovi sa stepenom dva 1 i 0. Ali oni nam nisu potrebni, pa da bismo se riješili nepotrebnih stupnjeva i ostavili potrebne , broj pišemo ovako: 1*2 3 + 1* 2 2 +0*2 1 + 0*2 0 = 1100 - ovo je binarni prikaz broja 12. Lako je primijetiti da je svaka uzastopna potencija najveći stepen dvojke, što je manje od razloženog broja. Da bismo konsolidirali metodu, pogledajmo još jedan primjer. Broj 23.

Korak 1. Najbliži stepen dvojke je 2 4 = 16. 23 -16 = 7.

Korak 2. Najbliži stepen dva 2 2 = 4. 7 - 4 = 3

Korak 3. Najbliži stepen dva 2 1 = 2. 3 - 2 = 1

Korak 4. Najbliži stepen dva 2 0 =1 1 - 1 =0

Dobijamo sljedeće proširenje: 1*2 4 + 0*2 3 +1*2 2 +1*2 1 +1*2 0

A naš željeni binarni broj je 10111

Metoda o kojoj smo gore govorili dobro rješava problem koji joj je dodijeljen, ali postoji metoda koja je mnogo bolje algoritmizirana. Algoritam za ovu metodu je napisan u nastavku:

Sve dok je BROJ veći od nule, učinite

SLJEDEĆA cifra = ostatak BROJA podijeljen sa 2

BROJ = cijeli dio BROJA podijeljen sa 2

Kada ovaj algoritam završi svoj rad, sekvenca izračunatih SLJEDEĆIH CIFRATA će predstavljati binarni broj. Na primjer, poradimo s brojem 19.

Početak algoritma BROJ = 19

SLJEDEĆA cifra = 1

SLJEDEĆA cifra = 1

SLJEDEĆA CIfra = 0

SLJEDEĆA CIfra = 0

SLJEDEĆA cifra = 1

Dakle, kao rezultat, imamo sljedeći broj 10011. Imajte na umu da se dvije razmatrane metode razlikuju po redoslijedu kojim se dobivaju sljedeće cifre. U prvoj metodi, prva primljena znamenka je najznačajnija cifra binarnog broja, a u drugoj metodi, prva primljena znamenka je, naprotiv, najmanje značajna.

Pretvorite decimalne brojeve u binarne na dva načina

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

Kako pretvoriti razlomak u decimalni broj.

Poznato je da se svaki racionalni broj može predstaviti kao decimalni i obični razlomak. Običan razlomak, odnosno razlomak oblika A/B, može biti pravilan i nepravilan. Razlomak se naziva pravim ako je A<В и неправильной если А>IN.

Ako je racionalni broj predstavljen nepravilnim razlomkom, a brojilac razlomka podijeljen sa nazivnikom cjelinom, onda je ovaj racionalni broj cijeli broj; u svim ostalim slučajevima pojavljuje se razlomak. Razlomak je često vrlo dug broj, pa čak i beskonačan (beskonačan periodični razlomak, na primjer 20/6), tako da u slučaju razlomka nemamo zadatak samo da prevedemo jednu reprezentaciju u drugu, već prevedemo s određenu tačnost.

Pravilo tačnosti. Pretpostavimo da vam je dat decimalni broj koji se može predstaviti kao decimalni razlomak sa tačnošću od N znamenki. Da bi odgovarajući binarni broj bio iste preciznosti, potrebno je u njega upisati M - znakove, tako da

Pokušajmo sada dobiti pravilo prijevoda i prvo pogledajmo primjer 5,401

Rješenje:

Dobit ćemo cijeli broj prema nama već poznatim pravilima, a jednak je binarnom broju 101. A razlomački dio ćemo proširiti na stepen 2.

Korak 1: 2 -2 = 0,25; 0,401 - 0,25 = 0,151. - ovo je ostatak.

2. korak: Sada trebamo predstaviti 0,151 kao stepen dvojke. Uradimo ovo: 2 -3 = 0,125; 0,151 - 0,125 = 0,026

Dakle, originalni razlomak se može predstaviti kao 2 -2 +2 -3. Ista stvar se može napisati u ovom binarnom broju: 0,011. Prva brojka razlomka je nula, to je zato što u našem proširenju nema stepena 2 -1.

Iz prvog i drugog koraka jasno je da ova reprezentacija nije tačna i možda bi bilo poželjno nastaviti proširenje. Pogledajmo pravilo. Kaže da nam treba toliko znakova M da je 10 3 manje od 2 M. To jest, 1000<2 M . То есть в двоичном разложении у нас должно быть не менее десяти знаков, так как 2 9 = 512 и только 2 10 = 1024. Продолжим процесс.

Korak 3: Sada radimo sa brojem 0,026. Najbliži stepen dvojke ovom broju je 2 -6 = 0,015625; 0,026 - 0,015625 = 0,010375 Sada je naš precizniji binarni broj: 0,011001. Već ima šest mjesta iza decimalnog zareza, ali to još nije dovoljno, pa radimo još jedan korak.

4. korak: Sada radimo sa brojem 0,010375. Najbliži stepen dvojke ovom broju je 2 -7 = 0,0078125;

0,010375 - 0,0078125 = 0,0025625

Korak 5: Sada radimo sa brojem 0,0025625. Najbliži stepen dvojke ovom broju je 2 -9 = 0,001953125;

0,0025625 - 0,001953125 = 0,000609375

Poslednji rezultujući ostatak je manji od 2 -10 i ako bismo želeli da nastavimo sa aproksimacijom prvobitnog broja, trebalo bi nam 2 -11, ali to već premašuje traženu tačnost, pa se stoga proračuni mogu zaustaviti i konačni binarni prikaz broja razlomak se može zapisati.

0,401 = 0,011001101

Kao što vidite, pretvaranje razlomka decimalnog broja u binarni je malo komplikovanije od pretvaranja celobrojnog dela. Tabela stepena dvojke na kraju predavanja.

Zapišimo sada algoritam konverzije:

Početni podaci algoritma: Kroz A ćemo označiti originalni pravi decimalni razlomak napisan u decimalnom obliku. Neka ovaj razlomak sadrži N znakova.

Algoritam

Radnja 1. Odredite broj potrebnih binarnih cifara M iz nejednakosti 10 N< 2 M

Akcija 2: Ciklus za izračunavanje znamenki binarnog prikaza (cifre iza nule). Broj cifre će biti označen simbolom K.

1. Broj cifara = 1
2. Ako je 2 -K > A

Zatim dodamo nulu binarnom broju

• dodaj 1 binarnom broju
• A = A - 2 -K

1. K = K + 1
2. Ako je K > M

• tada je algoritam završen
• U suprotnom idite na tačku 2.

Pretvorite decimalne brojeve u binarne

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

Oduzimanje binarnih brojeva. Oduzećemo i brojeve u koloni i opšte pravilo je isto kao i za decimalne brojeve, oduzimanje se vrši malo po bit i ako nema dovoljno jednog na mestu, onda se radi u najvišem. Riješimo sljedeći primjer:

Prva kategorija. 1 - 0 =1. Zapisujemo 1.

Druga kategorija 0 -1. Jedan nedostaje. Zauzimamo ga u kategoriji seniora. Jedinica iz starije cifre prelazi u mlađu, kao dvije jedinice (jer je starija cifra predstavljena dvojkom višeg stepena) 2-1 = 1. Zapisujemo 1.

Treća kategorija. Zauzeli smo jedinicu ovog ranga, tako da sada u rangu 0 postoji potreba da se zauzme jedinica najvišeg ranga. 2-1 =1. Zapisujemo 1.

Provjerimo rezultat u decimalnom sistemu

1101 - 110 = 13 - 6 = 7 (111) Ispravite jednakost.

Još jedan zanimljiv način oduzimanja uključuje koncept koda komplementa dva, koji vam omogućava da smanjite oduzimanje na sabiranje. Rezultat broja u komplementarnom kodu dvojke je krajnje jednostavan: uzimamo broj, zamjenjujemo nule jedinicama, naprotiv, zamjenjujemo one nulama i dodajemo jedan na najmanju cifru. Na primjer, 10010, dodatni kod će biti 011011.

Pravilo oduzimanja kroz komplement dvojke kaže da se oduzimanje može zamijeniti sabiranjem ako se oduzimanje zamijeni brojem u komplementu dvojke.

Primjer: 34 - 22 = 12

Zapišimo ovaj primjer u binarnom obliku. 100010 - 10110 = 1100

Dodatni kod broja 10110 će biti ovakav

01001 + 00001 = 01010. Tada se originalni primjer može zamijeniti sabiranjem ovako: 100010 + 01010 = 101100 Zatim morate odbaciti jednu jedinicu u najznačajnijoj cifri. Ako to učinimo, dobićemo 001100. Odbacimo beznačajne nule i dobijemo 1100, odnosno primjer je točno riješen

Izvršite oduzimanja. Na uobičajen način i u dodatnom kodu, prethodno konvertujući decimalne brojeve u binarne:

Provjerite pretvaranjem binarnog rezultata u decimalni brojevni sistem.

Množenje u binarnom brojevnom sistemu.

Prvo razmotrite sljedeću zanimljivu činjenicu. Da bi se binarni broj pomnožio sa 2 (decimalno dva je 10 u binarnom sistemu), dovoljno je dodati jednu nulu lijevo od broja koji se množi.

Primjer. 10101 * 10 = 101010

Ispitivanje.

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

Ako se prisjetimo da se bilo koji binarni broj može proširiti na stepen dvojke, onda postaje jasno da se množenje u binarnom brojevnom sistemu svodi na množenje sa 10 (odnosno sa decimalom 2), te je stoga množenje niz uzastopnih smjene. Opšte pravilo je da se, kao i kod decimalnih brojeva, binarno množenje izvodi po bitovima. I za svaku znamenku drugog množitelja, jedna nula se dodaje desno od prvog množitelja. Primjer (još nije u koloni):

1011 * 101 Ovo množenje se može svesti na zbir trocifrenih množenja:

1011 * 1 + 1011 * 0 + 1011 * 100 = 1011 +101100 = 110111 Isto se može napisati u koloni ovako:

pregled:

101 = 5 (decimalno)

1011 = 11 (decimalno)

110111 = 55 (decimalno)

5*11 = 55 tačna jednakost

Odlučite sami

a) 1101 * 1110 =

b) 1010 * 110 =

e) 101011 * 1101 =

e) 10010 * 1001 =

Napomena: Usput, tablica množenja u binarnom sistemu sastoji se od samo jedne stavke 1 * 1 = 1

Podjela u binarnom brojevnom sistemu.

Već smo pogledali tri akcije i mislim da je već jasno da se, općenito, akcije na binarne brojeve malo razlikuju od akcija na decimalne brojeve. Jedina razlika je u tome što postoje dva broja, a ne deset, ali to samo pojednostavljuje aritmetičke operacije. Ista je situacija i sa dijeljenjem, ali ćemo za bolje razumijevanje detaljnije analizirati algoritam dijeljenja. Pretpostavimo da trebamo podijeliti dva decimalna broja, na primjer 234 podijeljeno sa 7. Kako to radimo.

Odabiremo desno (od najznačajnije cifre) toliki broj cifara da dobijeni broj bude što manji, a istovremeno veći od djelitelja. 2 je manji od djelitelja, stoga je broj koji nam treba 23. Zatim rezultujući broj podijelimo s djeliteljem s ostatkom. Dobijamo sljedeći rezultat:

Ponavljamo opisanu operaciju sve dok rezultujući ostatak ne bude manji od djelitelja. Kada se to dogodi, broj dobiven ispod linije je količnik, a posljednji ostatak je ostatak operacije. Dakle, operacija dijeljenja binarnog broja se izvodi na potpuno isti način. Pokusajmo

primjer: 10010111 / 101

Tražimo broj čija je prva cifra veća od djelitelja. Ovo je četverocifreni broj 1001. Istaknut je podebljano. Sada morate pronaći djelitelj za odabrani broj. I tu opet pobjeđujemo u poređenju sa decimalnim sistemom. Činjenica je da je odabrani djelitelj nužno broj, a mi imamo samo dva broja. Pošto je 1001 jasno veće od 101, onda je sve jasno sa djeliteljem: 1. Izvršimo korak operacije.

Dakle, ostatak završene operacije je 100. Ovo je manje od 101, tako da da biste izvršili korak drugog dijeljenja, trebate dodati sljedeću cifru na 100, ovo je cifra 0. Sada imamo sljedeći broj:

1000 je veće od 101, pa ćemo u drugom koraku ponovo dodati broj 1 količniku i dobiti sljedeći rezultat (da uštedimo prostor, odmah ćemo izostaviti sljedeću cifru).

Treći korak. Dobijeni broj 110 je veći od 101, pa ćemo u ovom koraku u količnik upisati 1. Ispašće ovako:

Rezultirajući broj 11 manji je od 101, tako da upisujemo broj 0 u količnik i spuštamo sljedeći broj prema dolje. Ispada ovako:

Dobijeni broj je veći od 101, pa broj 1 upisujemo u količnik i ponovo izvodimo radnje. Ispada ova slika:

1

0

Rezultirajući ostatak 10 je manji od 101, ali nam je ponestalo cifara u dividendi, tako da je 10 konačni ostatak, a 1110 je traženi količnik.

Provjerimo decimalne brojeve

Ovim je završen opis najjednostavnijih aritmetičkih operacija koje trebate znati da biste koristili binarnu aritmetiku, a sada ćemo pokušati odgovoriti na pitanje „Zašto je binarna aritmetika potrebna?“ Naravno, gore je već pokazano da pisanje broja u binarnom sistemu značajno pojednostavljuje aritmetičke operacije, ali istovremeno i samo snimanje postaje znatno duže, što smanjuje vrijednost rezultirajućeg pojednostavljenja, pa je potrebno tražiti problemi čije je rješenje mnogo jednostavnije u binarnim brojevima.

Zadatak 1: Preuzimanje svih uzoraka

Vrlo često postoje problemi u kojima morate biti u stanju konstruirati sve moguće kombinacije iz datog skupa objekata. Na primjer, ovaj zadatak:

S obzirom na veliku hrpu kamenja, poređajte kamenje u dvije hrpe tako da masa ove dvije gomile bude što jednakija.

Ovaj zadatak se može formulirati na sljedeći način:

Pronađite izbor kamenja iz velike gomile tako da se njegova ukupna masa što je manje moguće razlikuje od polovine mase velike gomile.

Ima dosta zadataka ove vrste. A svi se oni svode, kao što je već rečeno, na mogućnost dobijanja svih mogućih kombinacija (u daljem tekstu ćemo ih zvati uzorci) iz datog skupa elemenata. A sada ćemo pogledati opći metod dobivanja svih mogućih uzoraka koristeći operaciju binarnog sabiranja. Počnimo s primjerom. Neka postoji skup od tri objekta. Konstruirajmo sve moguće uzorke. Predmete ćemo označavati serijskim brojevima. Odnosno, postoje sljedeće stavke: 1, 2, 3.

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

Ako je pozicija sa sljedećim brojem jedan, to znači da je u odabiru prisutan element s brojem jednakim ovoj poziciji, a ako postoji nula, onda element nije prisutan. Na primjer, uzorak (0, 1, 0); sastoji se od jednog elementa sa brojem 2, a izbor je (1, 1, 0); sastoji se od dva elementa sa brojevima 1 i 2.

Ovaj primjer jasno pokazuje da se uzorak može predstaviti kao binarni broj. Osim toga, lako je vidjeti da su svi mogući jednocifreni, dvocifreni i trocifreni binarni brojevi gore napisani. Prepišimo ih na sljedeći način:

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

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

Dobili smo niz uzastopnih binarnih brojeva, od kojih se svaki dobija od prethodnog dodavanjem jednog. Možete provjeriti ovo. Koristeći ovaj posmatrani obrazac, možemo konstruisati sledeći algoritam za dobijanje uzoraka.

Ulazni podaci algoritma

Dat je skup objekata N - komada. U nastavku ćemo ovaj skup zvati skup početnih elemenata. Numerirajmo sve elemente originalnog skupa od 1 do N. Napravimo binarni broj od N beznačajnih nula. 0000… 0 N Ovaj nulti binarni broj će označavati nulti uzorak s kojim će započeti proces uzorkovanja. Cifre broja se broje s desna na lijevo, odnosno krajnja lijeva cifra je najznačajnija.

Hajde da se dogovorimo da ovaj binarni broj označimo velikim slovima BINARY

Algoritam

Ako se BINARNI broj u potpunosti sastoji od jedinica

Zatim zaustavljamo algoritam

• Binarnom broju dodajemo jedan prema pravilima binarne aritmetike.
• Od rezultirajućeg BINARNOG broja pravimo sljedeći uzorak, kao što je gore opisano.

Problem 2: Pronalaženje velikih prostih brojeva

Za početak, sjetimo se da je prost broj prirodan broj koji je djeljiv samo sa 1 i samim sobom. Primjeri prostih brojeva: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

Pronalaženje velikih prostih brojeva je veoma važan matematički problem. Veliki prosti brojevi su neophodni za neke algoritme šifriranja za sigurno šifriranje poruka. Štaviše, nisu potrebni samo veliki brojevi, već vrlo veliki. Što je broj veći, pouzdanija je šifra izgrađena na ovom broju.

Bilješka. Jaka šifra je šifra kojoj je potrebno mnogo vremena da se dešifruje.

Zašto? Prosti broj djeluje kao ključ za šifriranje i dešifriranje. Osim toga, znamo da se prosti brojevi pojavljuju u nizu prirodni brojevi ne prečesto. Ima ih dosta među prvih hiljadu, a onda njihov broj počinje brzo da se smanjuje. Stoga, ako kao ključ uzmemo ne baš veliki broj, dešifrovač, uz pomoć čak i ne baš velikog broja, brz kompjuter moći će doći do toga (isprobavanjem svih jednostavnih kao ključeva jedan za drugim) u ograničenom vremenu.

Prilično pouzdan kod se može dobiti ako uzmete jednostavan, na primjer 150 znakova. Međutim, nije tako lako pronaći tako jednostavan. Pretpostavimo da određeni broj A (veoma veliki) treba provjeriti na primarnost. Ovo je isto kao i traženje njegovih djelitelja. Ako možemo pronaći djelitelje u rasponu od 2 do kvadratnog korijena od A, onda nije prost. Procijenimo broj brojeva koje treba testirati na sposobnost dijeljenja broja A.

Recimo da broj A ima 150 cifara. Njegov kvadratni korijen sadržavat će najmanje 75 znakova. Da nabrojimo toliki broj mogućih djelitelja trebat će nam vrlo moćan kompjuter i ogromna količina vremena, što znači da je problem praktično nerešiv.

Kako se nositi sa ovim.

Prvo, možete naučiti brzo provjeriti djeljivost jednog broja drugim, a drugo, možete pokušati odabrati broj A na takav način da bude prost s visokim stupnjem vjerovatnoće. Ispostavilo se da je to moguće. Matematičar Mersen je otkrio te brojeve sljedećeg oblika

Oni su jednostavni sa visokim stepenom verovatnoće.

Da bismo razumjeli gore napisanu frazu, hajde da izbrojimo koliko je prostih brojeva u prvoj hiljadi, a koliko Mersenovih brojeva je prostih u istoj hiljadi. Dakle, Mersenovi brojevi u prvoj hiljadi su sljedeći:

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;

Prosti brojevi su označeni podebljanim slovima. Postoji 5 prostih brojeva za 9 Mersenovih brojeva. Kao procenat, ovo je 5/9*100 = 55,6%. Istovremeno, na svakih 1000 prvih prirodnih brojeva, postoji samo 169 prostih brojeva. Kao procenat, ovo je 169/1000*100 = 16,9%. Odnosno, u prvih hiljadu, u procentima, prosti brojevi se među Mersenovim brojevima nalaze skoro 4 puta češće nego među prostim prirodnim brojevima

___________________________________________________________

Sada uzmimo određeni Mersenov broj, na primjer 2 4 - 1. Zapišimo ga kao binarni broj.

2 4 - 1 = 10000 - 1 = 1111

Uzmimo sljedeći Mersenov broj 2 5 -1 i zapišemo ga kao binarni broj. Dobijamo sljedeće:

2 5 -1 = 100000 - 1 = 11111

Već je jasno da su svi Mersenovi brojevi niz jedinica i sama ta činjenica daje veliki dobitak. Prvo, u binarnom brojevnom sistemu vrlo je jednostavno dobiti sljedeći Mersenov broj, samo sljedećem broju dodati jedan, a drugo, tražiti djelitelje u binarnom sistemu je mnogo lakše nego u decimalnom sistemu.

Brza konverzija decimalnog u binarnu

Jedan od glavnih problema sa upotrebom binarnog brojevnog sistema je teškoća u pretvaranju decimalnog broja u binarni. Ovo je prilično radno intenzivan zadatak. Naravno, nije previše teško prevesti male brojeve od tri ili četiri znamenke, ali za decimalne brojeve sa 5 ili više znamenki to je već teško. To jest, potreban nam je način da brzo pretvorimo velike decimalne brojeve u binarne.

Ovu metodu je izmislio francuski matematičar Legendre. Neka, na primjer, dobijemo broj 11183445. Podijelimo ga sa 64, dobijemo ostatak od 21, a količnik je 174741. Podijelimo ovaj broj ponovo sa 64, dobijemo ostatak od 21 i količnik od 2730. , 2730 podijeljeno sa 64 daje ostatak od 42 i količnik od 42 Ali 64 u binarnom sistemu je 1000000, 21 u binarnom sistemu je 10101, a 42 je 101010, dakle, originalni broj je napisan u binarnom sistemu na sljedeći način:

101010 101010 010101 010101

Da bi bilo jasnije, evo još jednog primjera s manjim brojem. Pretvorimo binarni prikaz broja 235. Podijelimo 235 sa 64 s ostatkom. Dobijamo:

QUANTIATE = 3, binarno 11 ili 000011

REMAINDER = 43, binarno 101011

Tada je 235 = 11101011. Provjerimo ovaj rezultat:

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

napomene:

1. Lako je vidjeti da konačni binarni broj uključuje sve ostatke i, u posljednjem koraku, i ostatak i količnik.
2. Količnik se piše ispred ostatka.
3. Ako rezultirajući količnik ili ostatak ima manje od 6 znamenki u binarnom prikazu (6 nula sadrži binarni prikaz broja 64 = 1000000), tada mu se dodaju beznačajne nule.

I još jedan složeniji primjer. Broj je 25678425.

Korak 1: 25678425 podijeljeno sa 64

Privatno = 401225

Preostalo = 25 = 011001

Korak 2: 401225 podijeljeno sa 64

Kvocijent = 6269

Ostatak = 9 = 001001

Korak 3: 6269 podijeljeno sa 64

Količnik = 97

Preostalo = 61 = 111101

Korak 4: 97 podijeljeno sa 64

Kvocijent = 1 = 000001

Preostalo = 33 = 100001

Rezultat broja = 1.100001.111101.001001.011001

U ovom broju, međurezultati uključeni u njega razdvojeni su tačkom.

Pretvorite brojeve u binarni prikaz:

DODATAK: 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

Izvođenje aritmetičkih operacija u bilo kojem pozicijskom brojevnom sistemu vrši se prema istim pravilima koja se koriste u decimalnom brojevnom sistemu.

Kao iu decimalnom brojevnom sistemu, za izvođenje aritmetičkih operacija potrebno je poznavati tablice sabiranja (oduzimanja) i množenja.

Tablica sabiranja, oduzimanja i množenja za binarni brojevni sistem

Dodavanje binarnih brojeva

Sabiranje u binarnom brojevnom sistemu slijedi ista pravila kao u decimalnom brojevnom sistemu. Dva broja se upisuju u kolonu poravnatu sa separatorom cijelog i razlomka i, ako je potrebno, dopunjuju se s desne strane beznačajnim nulama. Sabiranje počinje od krajnje desne cifre. Dvije jedinice nižeg reda se kombiniraju u jedinicu višeg reda.

primjer: 1011,1 2 + 1010,11 2

Zanimljiva je situacija i kada se dodaju više od dva broja. U ovom slučaju moguć je prijenos kroz nekoliko cifara.
primjer: 111,1 2 + 111 2 + 101,1 2

Prilikom sabiranja na mjestu jedinica (bit 0) postoje 4 jedinice koje, kada se spoje, daju 100 2 . Stoga se prenosi sa nulte na prvu cifru 0 , a u drugom - 1 .
Slična situacija se javlja i kod druge znamenke, gdje se, uzimajući u obzir dvije prenesene jedinice, dobije broj 5 = 101 2 . 1 ostaje u drugoj kategoriji, 0 prebačen u treći i 1 prebačen u četvrti.

Oduzimanje binarnih brojeva

U slučajevima kada je angažovana jedinica starije kategorije, daje se dve jedinice mlađe kategorije. Ako se jedinica proučava nakon više kategorija, onda se daje jedna jedinica u svim srednjim nultim kategorijama i dvije jedinice u kategoriji za koju je proučavana.
primjer: 10110,01 2 — 1001,1 2

Aritmetičke operacije u svim pozicionim brojevnim sistemima izvode se po istim pravilima koja su vam dobro poznata.

Dodatak. Razmotrimo sabiranje brojeva u binarnom brojevnom sistemu. Zasnovan je na tabeli za sabiranje jednocifrenih binarnih brojeva :

Važno je obratiti pažnju na činjenicu da se prilikom sabiranja dvije cifra prelijeva i prenosi na najznačajniju cifru. Prelivanje cifara se dešava kada vrednost broja u njemu postane jednaka ili veća od baze.

Dodavanje višebitnih binarnih brojeva odvija se u skladu s gornjom tablicom sabiranja, uzimajući u obzir moguće prijenose cifara nižeg reda u cifre visokog reda.

Kao primjer, dodajmo binarne brojeve 110 2 i 11 2 u kolonu :

Provjerimo ispravnost proračuna dodavanjem decimalnog brojevnog sistema. Pretvorimo binarne brojeve u decimalni brojevni sistem, a zatim ih dodajmo:

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 .

Sada konvertujmo rezultat binarnog sabiranja u decimalni broj:

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

Uporedimo rezultate - dodavanje je izvedeno ispravno.

Oduzimanje. Pogledajmo oduzimanje binarnih brojeva. Zasnovan je na tabeli za oduzimanje jednocifrenih binarnih brojeva. Prilikom oduzimanja većeg broja (1) od manjeg broja (0), kredit se daje od najviše cifre. U tabeli, kredit je označen 1 linijom:

Oduzimanje višebitnih binarnih brojeva odvija se u skladu sa gornjom tablicom oduzimanja, uzimajući u obzir moguća pozajmljivanja od najznačajnijih bitova. Kao primjer, oduzmimo binarne brojeve 110 2 i 11 2:

Množenje. Množenje se zasniva na tablici množenja jednocifrenih binarnih brojeva:

Množenje višecifrenih binarnih brojeva odvija se u skladu sa gornjom tablicom množenja prema uobičajenoj šemi koja se koristi u decimalnom brojevnom sistemu sa sekvencijalnim množenjem množenika ciframa množitelja. Kao primjer, pomnožimo binarne brojeve i:

Division. Operacija dijeljenja se izvodi pomoću algoritma sličnog algoritmu za izvođenje operacije dijeljenja u decimalnom brojevnom sistemu. Kao primjer, podijelimo binarni broj 110 2 i 11 2: