Binær aritmetikk

Parameternavn	Betydning
Artikkel emne:	Binær aritmetikk
Rubrikk (tematisk kategori)	Datavitenskap

Binært tallsystem

Nummersystemer som brukes når du arbeider med datamaskiner

Base P = 2. Alfabetet inkluderer to binære sifre: 0, 1. Ethvert tall C = C n C n-1 ...C 1 C 0 C -1 C -m er summen av potensene til tallet 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

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

Vektene til sifrene i det binære tallsystemet er 1, 4, 8,16,... til venstre for desimaltegnet og 0,5; 0,25; 0,125; 0,625;... til høyre for desimaltegn.

Noen ganger brukt i programmering heksadesimal notasjon. For å representere tall større enn 9 i det heksadesimale tallsystemet, brukes de latinske bokstavene A, B, C, D, E, F. Bilder av de første seksten tallene i desimale, binære og heksadesimale tallsystemene er gitt i Tabell. 2.

Kodetabell i ulike systemer død regning

tabell 2

Desimalsystem	Binært system	Heksadesimalt system	Desimalsystem	Binært system	Heksadesimalt system
					EN
					B
					C
					D
					E
					F

Binær desimal Tallsystemet har blitt utbredt i moderne datamaskiner på grunn av den enkle konverteringen til desimalsystemet og omvendt. Den brukes der hovedoppmerksomheten ikke rettes mot enkelheten i den tekniske konstruksjonen av maskinen, men til brukerens bekvemmelighet. I dette tallsystemet er alle desimalsiffere kodet separat med fire binære sifre.

Eksempel 3.7.

Desimaltallet 9703 i BCD ser slik ut: 1001 0111 0000 0011.

Fordelen med det binære tallsystemet fremfor desimaltallsystemet fra en digital datamaskins synspunkt er følgende:

• elementer med to stabile tilstander kreves;
• aritmetiske operasjoner er betydelig forenklet;
• 1,5 ganger mindre utstyr kreves;
• lar deg bruke apparatet til matematisk logikk for analyse og syntese av kretser.

Ulempene med det binære tallsystemet er som følger:

• stort antall opptakslengde;
• Når du legger inn og skriver ut informasjon, kreves konvertering til desimaltallsystemet.

La oss se på hvordan grunnleggende operasjoner utføres i binær aritmetikk.

Regnereglene i alle posisjonstallsystemer er de samme, ᴛ.ᴇ. addisjon, multiplikasjon og subtraksjon begynner fra de laveste sifrene, divisjon - fra de høyeste.

Når du legger til, legges bæreenheten til sifrene til det tilstøtende mest signifikante sifferet. Når det trekkes fra, gir en låneenhet i det høyeste sifferet to enheter i det laveste tilstøtende sifferet.

Eksempel 3.8

Å multiplisere binære tall ligner på å multiplisere desimaltall, men... Hvis vi multipliserer bare med 0 og 1, reduseres multiplikasjonen til operasjonen av skift og addisjon.

Eksempel 3.9

Binær aritmetikk - konsept og typer. Klassifisering og funksjoner i kategorien "Binær aritmetikk" 2017, 2018.

- Binær aritmetikk

Fordi informasjonsprosesser V digitale systemer ta verdiene bare 0 og 1, deretter utføres datarepresentasjon ved hjelp av binære tall. Addisjon og subtraksjon av binære tall, samt alle andre aritmetiske operasjoner, utføres etter samme regler som... .

- Binært tallsystem og binær aritmetikk

I det binære tallsystemet kan du utføre de samme operasjonene med tall som i desimaltallsystemet. Addisjon utføres på samme prinsipp som i desimaltallsystemet: bare hvis et gitt siffer produserer et beløp som ikke passer inn i det, så...

, Konkurransen "Presentasjon for leksjonen"

Presentasjon for leksjonen

Tilbake fremover

Merk følgende! Forhåndsvisning Lysbildene er kun til informasjonsformål og representerer kanskje ikke alle funksjonene i presentasjonen. Hvis du er interessert denne jobben, last ned fullversjonen.

Leksjonens mål: (lysbilde 2)

1. Introduser elevene til det binære tallsystemet.
2. Utvikle ferdigheter i å utføre aritmetiske operasjoner med binære tall

I løpet av timene

I. Start på leksjonen

Lærer: For å mestre det binære tallsystemet bedre, må du mestre å utføre aritmetiske operasjoner på binære tall.

Alle posisjonelle tallsystemer er "like", nemlig i alle av dem utføres aritmetiske operasjoner i henhold til de samme reglene:

• de samme aritmetikkens lover er gyldige: kommutativ, assosiativ, distributiv;
• reglene for addisjon, subtraksjon, multiplikasjon og divisjon er gyldige;
• Reglene for å utføre aritmetiske operasjoner er basert på addisjons- og multiplikasjonstabeller.

La oss se på reglene for å utføre aritmetiske operasjoner

II. Lære nytt stoff

Når du deler på en kolonne, må du utføre multiplikasjon og subtraksjon som mellomresultat. Men i det binære tallsystemet reduseres mellommultiplikasjoner til å multiplisere divisor med enten 0 eller 1, så den vanskeligste operasjonen forblir subtraksjon, som du må lære deg å gjøre nøyaktig.

III. Konsolidering av det som er lært. (lysbilde 12)

Gutta gjør jobben på egenhånd. Åpne deretter lysbildet med svarene.

Svar. (lysbilde 13)

IV. Lekser (lysbilde 14)

1. Lær reglene for å utføre aritmetiske operasjoner i det binære tallsystemet.

2. Følg disse trinnene:

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

hjem \ Dokumentasjon \ For lærer i informatikk

Når du bruker materialer fra dette nettstedet - og å plassere et banner er OBLIGATORISK!!!

Binær aritmetikk

Tallene vi er vant til å bruke kalles desimal og aritmetikken vi bruker kalles også desimal. Dette er fordi hvert tall kan være sammensatt av et sett med tall som inneholder 10 tegn - tall - "0123456789".

Matematikken utviklet seg på en slik måte at akkurat dette settet ble det viktigste, men desimalregning er ikke den eneste. Hvis vi bare tar fem sifre, kan vi på grunnlag av dem konstruere femsifret aritmetikk, og fra syv sifre - syvsifret aritmetikk. På kunnskapsområder knyttet til data utstyr aritmetikk brukes ofte der tall består av seksten sifre; følgelig kalles denne aritmetikken heksadesimal. For å forstå hva et tall er i ikke-desimal aritmetikk, finner vi først ut hva et tall er i desimalregning.

Ta for eksempel tallet 246. Denne notasjonen betyr at det er to hundre, fire tiere og seks enere i tallet. Derfor kan vi skrive følgende likhet:

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

Her skiller likhetstegn tre måter å skrive samme tall på. Den tredje formen for notasjon er mest interessant for oss nå: 2 * 10 2 + 4 * 10 1 + 6 * 10 0 . Den er strukturert som følger:

Nummeret vårt har tre sifre. Det ledende sifferet "2" er nummer 3. Så det multipliseres med 10 til andre potens. Det neste sifferet "4" har et serienummer på 2 og multipliseres med 10 i det første. Det er allerede klart at sifre multipliseres med ti i potens av én mindre enn serienummeret til sifferet. Etter å ha forstått ovenstående, kan vi skrive ned den generelle formelen for å representere et desimaltall. La oss få et tall med N sifre. Vi vil betegne i-te siffer gjennom en i. Deretter kan tallet skrives på følgende form: a n a n-1 ....a 2 a 1 . Dette er det første skjemaet, og det tredje påmeldingsskjemaet vil se slik ut:

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

der a i er et tegn fra settet "0123456789"

Tierens rolle er veldig tydelig synlig i denne innspillingen. Ti er grunnlaget for dannelsen av tall. Og forresten, det kalles "grunnlaget for tallsystemet", og selve tallsystemet er grunnen til at det kalles "desimaltall." Tallet ti har selvfølgelig ingen spesielle egenskaper. Vi kan enkelt erstatte ti med et hvilket som helst annet tall. For eksempel kan et tall i det femsifrede tallsystemet skrives slik:

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

der a i er et tegn fra settet "01234"

Generelt sett erstatter vi 10 med et hvilket som helst annet tall og får et helt annet tallsystem og annen aritmetikk. Den enkleste aritmetikken oppnås hvis 10 erstattes med 2. Det resulterende tallsystemet kalles binært og tallet i det er definert som følger:

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

der a i er et tegn fra settet "01"

Dette systemet er det enkleste av alle mulige, siden et hvilket som helst tall i det bare dannes av to sifre 0 og 1. Det er klart at det ikke kunne vært enklere. Eksempler på binære tall: 10, 111, 101.

Veldig viktig spørsmål. Er det mulig å representere et binært tall som et desimaltall og omvendt? desimaltall representere det i binær form.

Binær til desimal. Det er veldig enkelt. Metoden for slik oversettelse er gitt av vår måte å skrive tall på. La oss ta for eksempel følgende binære tall 1011. La oss utvide det til to potenser. Vi får følgende:

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

La oss utføre alle de registrerte handlingene og få:

1 * 2 3 + 0 * 2 2 + 1 * 2 1 + 1 * 2 0 = 8 + 0+ 2 + 1 = 11. Dermed får vi at 1011 (binær) = 11 (desimal). En liten ulempe med det binære systemet er umiddelbart synlig. Det samme tallet, som er skrevet i desimalsystemet med ett siffer i det binære systemet, krever fire sifre for registreringen. Men dette er prisen for enkelhet (ingenting kommer gratis). Men det binære systemet gir en enorm gevinst i aritmetiske operasjoner. Og dette får vi se senere.

Uttrykk følgende binære tall som en desimal.

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

Addisjon av binære tall.

Metoden for kolonneaddisjon er vanligvis den samme som for et desimaltall. Det vil si at addisjon utføres bitvis, og starter med det minst signifikante sifferet. Hvis, når du legger til to sifre, er SUMMEN større enn ni, skrives sifferet = SUM - 10, og HELE DELEN (SUM / 10) legges til i det mest signifikante sifferet. (Legg til et par tall i en kolonne, husk hvordan dette gjøres.) Det samme med et binært tall. Legg til en etter en, start med det laveste sifferet. Hvis resultatet er mer enn 1, skrives 1 ned og 1 legges til det mest signifikante sifferet (de sier "av toppen av hodet mitt").

La oss ta eksempelet: 10011 + 10001.

Første kategori: 1+1 = 2. Vi skriver 0 og 1 etter hvert som det kommer til tankene.

Andre kategori: 1+0+1 (memorert enhet) =2. Vi skriver ned 0 og 1, kom det til tankene.

Tredje kategori: 0+0+1(memorert enhet) = 1. Skriv 1.

Fjerde kategori 0+0=0. Vi skriver 0.

Femte kategori 1+1=2. Vi skriver ned 0 og legger til 1 til det sjette sifferet.

La oss konvertere alle tre tallene til desimalsystemet og sjekke riktigheten av addisjonen.

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 riktig likestilling

Eksempler på uavhengige løsninger:

a) 11001 +101 =

b) 11001 +11001 =

c) 1001 + 111 =

e) 10011 + 101 =

e) 11011 + 1111 =

e) 11111 + 10011 =

Hvordan konvertere et desimaltall til binært. Den neste operasjonen er subtraksjon. Men vi skal behandle denne operasjonen litt senere, og nå vil vi vurdere metoden for å konvertere et desimaltall til binært.

For å konvertere et desimaltall til binært, må det utvides til to potenser. Men hvis utvidelsen i potenser av ti oppnås umiddelbart, krever det litt omtanke om hvordan man utvider i potenser av to. Først, la oss se på hvordan du gjør dette ved å bruke valgmetoden. La oss ta desimaltallet 12.

Steg en. 2 2 = 4, dette er ikke nok. Også 2 3 = 8 er ikke nok, men 2 4 = 16 er allerede mye. Derfor lar vi 2 3 =8. 12 - 8 = 4. Nå må du representere det som en potens av to 4.

Trinn to. 4 = 2 2.

Da er tallet vårt 12 = 2 3 + 2 2. Det høyeste sifferet har tallet 4, den høyeste graden = 3, derfor må det være ledd med potensene 1 og 0. Men vi trenger dem ikke, så for å bli kvitt unødvendige grader og la de nødvendige , skriver vi tallet slik: 1*2 3 + 1* 2 2 +0*2 1 + 0*2 0 = 1100 - dette er den binære representasjonen av tallet 12. Det er lett å legge merke til at hver suksessiv potens er den største potensen av to, som er mindre enn det dekomponerte tallet. For å konsolidere metoden, la oss se på et annet eksempel. Nummer 23.

Trinn 1. Den nærmeste potensen av to er 2 4 = 16. 23 -16 = 7.

Trinn 2. Nærmeste potens av to 2 2 = 4. 7 - 4 = 3

Trinn 3. Nærmeste potens av to 2 1 = 2. 3 - 2 = 1

Trinn 4. Nærmeste potens av to 2 0 =1 1 - 1 =0

Vi får følgende utvidelse: 1*2 4 + 0*2 3 +1*2 2 +1*2 1 +1*2 0

Og vårt ønskede binære nummer er 10111

Metoden diskutert ovenfor løser problemet som er tildelt den godt, men det er en metode som er mye bedre algoritmert. Algoritmen for denne metoden er skrevet nedenfor:

Så lenge ANTALLET er større enn null, gjør du det

NESTE SIFFER = resten av NUMMER delt på 2

NUMBER = heltallsdel av NUMBER delt på 2

Når denne algoritmen fullfører arbeidet, vil sekvensen av beregnede NESTE SIFFRE representere et binært tall. La oss for eksempel jobbe med tallet 19.

AlgoritmestartNUMMER = 19

NESTE SIFFER = 1

NESTE SIFFER = 1

NESTE SIFFER = 0

NESTE SIFFER = 0

NESTE SIFFER = 1

Så, som et resultat, har vi følgende nummer 10011. Merk at de to metodene som er diskutert er forskjellige i rekkefølgen som de neste sifrene oppnås. I den første metoden er det første mottatte sifferet det mest signifikante sifferet i det binære tallet, og i den andre metoden er det første mottatte sifferet tvert imot det minst signifikante.

Konverter desimaltall til binære tall på to måter

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

Hvordan konvertere en brøk til et desimaltall.

Det er kjent at ethvert rasjonelt tall kan representeres som en desimal og en vanlig brøk. En vanlig brøk, det vil si en brøk av formen A/B, kan være regelmessig og upassende. En brøk kalles egentlig hvis A<В и неправильной если А>I.

Hvis et rasjonelt tall er representert med en uekte brøk, og telleren til brøken er delt med nevneren med en hel, så er dette rasjonelle tallet et heltall; i alle andre tilfeller vises en brøkdel. Brøkdelen er ofte et veldig langt tall og til og med uendelig (en uendelig periodisk brøk, for eksempel 20/6), så i tilfellet med brøkdelen har vi ikke bare oppgaven med å oversette en representasjon til en annen, men å oversette med en viss nøyaktighet.

Regel for nøyaktighet. Anta at du får et desimaltall som kan representeres som en desimalbrøk med en nøyaktighet på N sifre. For at det tilsvarende binære tallet skal ha samme presisjon, er det nødvendig å skrive M - tegn i det, slik at

La oss nå prøve å få oversettelsesregelen, og la oss først se på eksempel 5401

Løsning:

Vi vil få heltallsdelen i henhold til reglene som allerede er kjent for oss, og den er lik det binære tallet 101. Og vi vil utvide brøkdelen i potenser av 2.

Trinn 1: 2-2 = 0,25; 0,401 - 0,25 = 0,151. - dette er resten.

Steg 2: Nå må vi representere 0,151 som en potens av to. La oss gjøre dette: 2 -3 = 0,125; 0,151 - 0,125 = 0,026

Dermed kan den opprinnelige brøkdelen representeres som 2 -2 +2 -3. Det samme kan skrives i dette binære tallet: 0,011. Det første brøksifferet er null, dette er fordi i utvidelsen vår er det ingen potens på 2 -1.

Fra første og andre trinn er det klart at denne fremstillingen ikke er nøyaktig og det kan være ønskelig å fortsette utvidelsen. La oss se på regelen. Det står at vi trenger så mange tegn på M at 10 3 er mindre enn 2 M. Det vil si 1000<2 M . То есть в двоичном разложении у нас должно быть не менее десяти знаков, так как 2 9 = 512 и только 2 10 = 1024. Продолжим процесс.

Trinn 3: Nå jobber vi med tallet 0,026. Den nærmeste potensen av to til dette tallet er 2 -6 = 0,015625; 0,026 - 0,015625 = 0,010375 Nå er vårt mer nøyaktige binære tall: 0,011001. Det er allerede seks plasser etter desimaltegnet, men dette er ikke nok ennå, så vi utfører ett trinn til.

Trinn 4: Nå jobber vi med tallet 0,010375. Den nærmeste potensen av to til dette tallet er 2 -7 = 0,0078125;

0,010375 - 0,0078125 = 0,0025625

Trinn 5: Nå jobber vi med tallet 0,0025625. Den nærmeste potensen av to til dette tallet er 2 -9 = 0,001953125;

0,0025625 - 0,001953125 = 0,000609375

Den siste resulterende resten er mindre enn 2 -10, og hvis vi ville fortsette å tilnærme det opprinnelige tallet, ville vi trenge 2 -11, men dette overskrider allerede den nødvendige nøyaktigheten, og derfor kan beregningene stoppes og den endelige binære representasjonen av brøkdel kan skrives ned.

0,401 = 0,011001101

Som du kan se, er det litt mer komplisert å konvertere brøkdelen av et desimaltall til binært enn å konvertere heltallsdelen. Tabell over makter av to på slutten av forelesningen.

La oss nå skrive ned konverteringsalgoritmen:

Innledende data for algoritmen: Gjennom A vil vi betegne den opprinnelige riktige desimalbrøken skrevet i desimalform. La denne brøken inneholde N tegn.

Algoritme

Handling 1. Bestem antall nødvendige binære sifre M fra ulikheten 10 N< 2 M

Handling 2: Syklus for å beregne sifrene i den binære representasjonen (siffer etter null). Siffernummeret vil bli merket med symbolet K.

1. Siffernummer = 1
2. Hvis 2 -K > A

Så legger vi null til det binære tallet

• legg til 1 til det binære tallet
• A = A - 2 -K

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

• da er algoritmen fullført
• Ellers gå til punkt 2.

Konverter desimaltall til binære

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

Subtrahere binære tall. Vi vil også trekke fra tall i en kolonne og den generelle regelen er den samme som for desimaltall, subtraksjon utføres bit for bit og hvis det ikke er nok en på plassen, så gjøres det i den høyeste. La oss løse følgende eksempel:

Første kategori. 1 - 0 = 1. Vi skriver ned 1.

Andre kategori 0 -1. En mangler. Vi opptar det i seniorkategorien. En enhet fra et seniorsiffer går inn i en junior, som to enheter (fordi seniorsifferet er representert med en to av høyere grad) 2-1 = 1. Vi skriver ned 1.

Tredje kategori. Vi okkuperte en enhet av denne rangeringen, så nå i rang 0 er det behov for å okkupere en enhet av høyeste rang. 2-1 = 1. Vi skriver ned 1.

La oss sjekke resultatet i desimalsystemet

1101 - 110 = 13 - 6 = 7 (111) Riktig likestilling.

En annen interessant måte å utføre subtraksjon på involverer konseptet med tos komplementkode, som lar deg redusere subtraksjon til addisjon. Resultatet av et tall i tos komplementkode er ekstremt enkelt: vi tar tallet, erstatter nullene med enere, tvert imot, erstatter de med nuller og legger en til det minst signifikante sifferet. For eksempel, 10010, tilleggskoden vil være 011011.

Regelen om subtraksjon gjennom tos komplement sier at subtraksjon kan erstattes med addisjon hvis subtrahenden erstattes med et tall i tos komplement.

Eksempel: 34 - 22 = 12

La oss skrive dette eksemplet i binær form. 100010 - 10110 = 1100

Tilleggskoden til nummeret 10110 vil være slik

01001 + 00001 = 01010. Da kan det opprinnelige eksemplet erstattes med addisjon slik: 100010 + 01010 = 101100 Deretter må du forkaste én enhet i det mest signifikante sifferet. Hvis vi gjør dette, får vi 001100. La oss forkaste ubetydelige nuller og få 1100, det vil si at eksemplet ble løst riktig

Utfør subtraksjoner. På vanlig måte og i tilleggskode, etter å ha konvertert desimaltall til binære tidligere:

Sjekk ved å konvertere det binære resultatet til desimaltallsystemet.

Multiplikasjon i det binære tallsystemet.

Tenk først på følgende interessante faktum. For å multiplisere et binært tall med 2 (desimal to er 10 i det binære systemet), er det nok å legge til en null til venstre for tallet som multipliseres.

Eksempel. 10101 * 10 = 101010

Undersøkelse.

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

Hvis vi husker at et hvilket som helst binært tall kan utvides til potenser av to, så blir det klart at multiplikasjon i det binære tallsystemet reduseres til multiplikasjon med 10 (det vil si med desimal 2), og derfor er multiplikasjon en serie av suksessive skifter. Den generelle regelen er at, som med desimaltall, utføres binær multiplikasjon bitvis. Og for hvert siffer i den andre multiplikatoren legges en null til høyre for den første multiplikatoren. Eksempel (ikke i en kolonne ennå):

1011 * 101 Denne multiplikasjonen kan reduseres til summen av tresifrede multiplikasjoner:

1011 * 1 + 1011 * 0 + 1011 * 100 = 1011 +101100 = 110111 Det samme kan skrives i en kolonne slik:

Undersøkelse:

101 = 5 (desimal)

1011 = 11 (desimal)

110111 = 55 (desimal)

5*11 = 55 riktig likhet

Bestem selv

a) 1101 * 1110 =

b) 1010 * 110 =

e) 101011 * 1101 =

e) 10010 * 1001 =

Merk: Forresten, multiplikasjonstabellen i det binære systemet består av bare ett element 1 * 1 = 1

Divisjon i det binære tallsystemet.

Vi har allerede sett på tre handlinger og jeg tror det allerede er klart at generelt sett skiller handlinger på binære tall seg lite fra handlinger på desimaltall. Den eneste forskjellen er at det er to tall og ikke ti, men dette forenkler bare aritmetiske operasjoner. Situasjonen er den samme med divisjon, men for en bedre forståelse vil vi analysere divisjonsalgoritmen mer detaljert. Anta at vi må dele to desimaltall, for eksempel 234 delt på 7. Hvordan gjør vi dette.

Vi velger til høyre (fra det mest signifikante sifferet) et slikt antall sifre at det resulterende tallet er så lite som mulig og samtidig større enn divisoren. 2 er mindre enn divisor, derfor er tallet vi trenger 23. Deretter deler vi det resulterende tallet på divisor med en rest. Vi får følgende resultat:

Vi gjentar den beskrevne operasjonen til den resulterende resten er mindre enn divisoren. Når dette skjer, er tallet oppnådd under linjen kvotienten, og den siste resten er resten av operasjonen. Så operasjonen med å dele et binært tall utføres på nøyaktig samme måte. La oss prøve

Eksempel: 10010111 / 101

Vi ser etter et tall hvis første siffer er større enn divisor. Dette er det firesifrede tallet 1001. Det er uthevet med fet skrift. Nå må du finne en divisor for det valgte tallet. Og her vinner vi igjen i sammenligning med desimalsystemet. Faktum er at den valgte divisoren nødvendigvis er et tall, og vi har bare to tall. Siden 1001 er klart større enn 101, så er alt klart med divisoren: 1. La oss utføre operasjonstrinnet.

Så, resten av den fullførte operasjonen er 100. Dette er mindre enn 101, så for å utføre det andre divisjonstrinnet, må du legge til neste siffer til 100, dette er sifferet 0. Nå har vi følgende tall:

1000 er større enn 101, så i det andre trinnet vil vi igjen legge til tallet 1 til kvotienten og få følgende resultat (for å spare plass vil vi umiddelbart utelate neste siffer).

Tredje trinn. Det resulterende tallet 110 er større enn 101, så på dette trinnet vil vi skrive 1 inn i kvotienten. Det vil vise seg slik:

Det resulterende tallet 11 er mindre enn 101, så vi skriver tallet 0 i kvotienten og senker det neste tallet ned. Det blir slik:

Det resulterende tallet er større enn 101, så vi skriver tallet 1 inn i kvotienten og utfører handlingene på nytt. Det viser seg dette bildet:

1

0

Den resulterende resten 10 er mindre enn 101, men vi har gått tom for sifre i utbyttet, så 10 er den siste resten, og 1110 er den nødvendige kvotienten.

La oss sjekke inn desimaltall

Dette avslutter beskrivelsen av de enkleste aritmetiske operasjonene du trenger å vite for å bruke binær aritmetikk, og nå vil vi prøve å svare på spørsmålet "Hvorfor er binær aritmetikk nødvendig?" Selvfølgelig er det allerede vist ovenfor at å skrive et tall i det binære systemet betydelig forenkler aritmetiske operasjoner, men samtidig blir selve registreringen mye lengre, noe som reduserer verdien av den resulterende forenklingen, så det er nødvendig å se etter problemer hvis løsning er mye enklere i binære tall.

Oppgave 1: Hente alle prøver

Svært ofte er det problemer der du må kunne konstruere alle mulige kombinasjoner fra et gitt sett med objekter. For eksempel denne oppgaven:

Gitt en stor haug med steiner, ordne steinene i to hauger slik at massen av de to haugene er så lik som mulig.

Denne oppgaven kan formuleres som følger:

Finn et utvalg steiner fra en stor haug slik at dens totale masse avviker minst mulig fra halvparten av massen til den store haugen.

Det er ganske mange oppgaver av denne typen. Og de koker alle ned, som allerede sagt, til evnen til å oppnå alle mulige kombinasjoner (heretter vil vi kalle dem prøver) fra et gitt sett med elementer. Og nå skal vi se på den generelle metoden for å få alle mulige prøver ved å bruke den binære addisjonsoperasjonen. La oss starte med et eksempel. La det være et sett med tre objekter. La oss konstruere alle mulige prøver. Vi vil betegne objekter med serienummer. Det vil si at det er følgende elementer: 1, 2, 3.

Prøver: (0, 0, 1); (0, 1, 0); (0, 1, 1); (100); (1, 0, 1); (1, 1, 0); (1, 1, 1);

Hvis posisjonen med det neste tallet er ett, betyr dette at et element med et tall lik denne posisjonen er tilstede i utvalget, og hvis det er en null, er elementet ikke til stede. For eksempel, sample (0, 1, 0); består av ett element med nummer 2, og utvalget er (1, 1, 0); består av to elementer med tallene 1 og 2.

Dette eksemplet viser tydelig at en prøve kan representeres som et binært tall. I tillegg er det lett å se at alle mulige ett-, to- og tresifrede binære tall er skrevet over. La oss omskrive dem som følger:

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

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

Vi har mottatt en serie påfølgende binære tall, som hver er hentet fra det forrige ved å legge til ett. Du kan sjekke dette. Ved å bruke dette observerte mønsteret kan vi konstruere følgende algoritme for å få prøver.

Algoritmeinndata

Gitt et sett med objekter N - stykker. I det følgende vil vi kalle dette settet med innledende elementer. La oss nummerere alle elementene i det opprinnelige settet fra 1 til N. La oss lage et binært tall fra N ubetydelige nuller. 0000… 0 N Dette binære nulltallet vil angi nullprøven som samplingsprosessen vil begynne med. Sifrene i et tall telles fra høyre til venstre, det vil si at sifferet lengst til venstre er det mest signifikante.

La oss bli enige om å angi dette binære tallet med store bokstaver BINÆR

Algoritme

Hvis et BINÆRT tall utelukkende består av enere

Da stopper vi algoritmen

• Vi legger en til et BINÆRT tall i henhold til reglene for binær aritmetikk.
• Fra det resulterende BINÆRE tallet lager vi neste prøve, som beskrevet ovenfor.

Oppgave 2: Finne store primtall

Til å begynne med, la oss huske at et primtall er et naturlig tall som bare er delelig med 1 og seg selv. Eksempler på primtall: 1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31

Å finne store primtall er et svært viktig matematisk problem. Store primtall er nødvendige for at enkelte krypteringsalgoritmer skal kryptere meldinger på en sikker måte. Dessuten er det ikke bare behov for store tall, men svært store. Jo større tallet er, desto mer pålitelig bygde chifferen på dette tallet.

Merk. Et sterkt chiffer er et chiffer som tar veldig lang tid å tyde.

Hvorfor? Et primtall fungerer som en nøkkel for kryptering og dekryptering. I tillegg vet vi at primtall forekommer i rekken naturlige tall ikke for ofte. Det er ganske mange av dem blant de første tusen, så begynner antallet raskt å synke. Derfor, hvis vi tar et ikke veldig stort tall som en nøkkel, vil dechiffrøren, ved hjelp av ikke engang et veldig stort tall, rask datamaskin vil kunne komme til det (ved å prøve ut alle de enkle som en nøkkel etter hverandre) på en begrenset tid.

En ganske pålitelig kode kan fås hvis du tar en enkel, for eksempel 150 tegn. Men å finne en så enkel en er ikke så lett. Anta at et visst tall A (veldig stort) må sjekkes for primalitet. Dette er det samme som å lete etter divisorene. Hvis vi kan finne divisorer i området fra 2 til kvadratroten av A, så er det ikke primtall. La oss anslå antall tall som må testes for evnen til å dele tallet A.

La oss si at nummer A har 150 sifre. Kvadratroten av den vil inneholde minst 75 tegn. For å telle opp et slikt antall mulige divisorer vil vi trenge veldig kraftig datamaskin og en enorm mengde tid, noe som betyr at problemet er praktisk talt uløselig.

Hvordan håndtere dette.

For det første kan du lære deg å raskt sjekke for delbarheten av ett tall med et annet, og for det andre kan du prøve å velge tallet A på en slik måte at det er primtall med høy grad av sannsynlighet. Det viser seg at dette er mulig. Matematikeren Mersen oppdaget at tall av følgende form

De er enkle med høy grad av sannsynlighet.

For å forstå setningen skrevet ovenfor, la oss telle hvor mange primtall som er i de første tusen og hvor mange Mersen-tall som er primtall i samme tusen. Så Mersen-tallene i de første tusen er som følger:

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;

Primtall er markert med fet skrift. Det er 5 primtall for 9 Mersen-tall. I prosent er dette 5/9*100 = 55,6 %. Samtidig, for hver 1000 første naturlige tall, er det bare 169 primtall. I prosent er dette 169/1000*100 = 16,9 %. Det vil si at i de første tusen, prosentvis, finnes primtall blant Mersen-tall nesten 4 ganger oftere enn blant enkle naturlige tall

___________________________________________________________

La oss nå ta et spesifikt Mersen-tall, for eksempel 2 4 - 1. La oss skrive det som et binært tall.

2 4 - 1 = 10000 - 1 = 1111

La oss ta følgende Mersen-tall 2 5 -1 og skrive det som et binært tall. Vi får følgende:

2 5 -1 = 100000 - 1 = 11111

Det er allerede klart at alle Mersen-numre er en sekvens av enere og dette faktum i seg selv gir en stor gevinst. For det første, i det binære tallsystemet er det veldig enkelt å få det neste Mersen-tallet, bare legg til ett til det neste tallet, og for det andre er det mye lettere å se etter divisorer i det binære systemet enn i desimalsystemet.

Rask desimal til binær konvertering

Et av hovedproblemene med å bruke det binære tallsystemet er vanskeligheten med å konvertere et desimaltall til binært. Dette er en ganske arbeidskrevende oppgave. Selvfølgelig er det ikke så vanskelig å oversette små tall på tre eller fire sifre, men for desimaltall med 5 eller flere sifre er dette allerede vanskelig. Det vil si at vi trenger en måte å raskt konvertere store desimaltall til binære tall.

Denne metoden ble oppfunnet av den franske matematikeren Legendre. La for eksempel gi tallet 11183445. Vi deler det på 64, vi får en rest av 21 og kvotienten er 174741. Vi deler dette tallet igjen med 64, vi får en rest på 21 og en kvotient på 2730. Til slutt , 2730 delt på 64 gir en rest på 42 og en kvotient på 42, ​​men 64 i binær er 1000000, 21 i binær er 10101, og 42 er 101010. Derfor skrives det opprinnelige tallet i binært som følger:

101010 101010 010101 010101

For å gjøre det mer tydelig, her er et annet eksempel med et mindre tall. La oss konvertere den binære representasjonen av tallet 235. Del 235 med 64 med en rest. Vi får:

KVANTIER = 3, binær 11 eller 000011

RESTEN = 43, binær 101011

Så 235 = 11101011. La oss sjekke dette resultatet:

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

Merknader:

1. Det er lett å se at det endelige binære tallet inkluderer alle rester og, på siste trinn, både resten og kvotienten.
2. Kvoten skrives før resten.
3. Hvis den resulterende kvotienten eller resten har mindre enn 6 sifre i binær representasjon (6 nuller inneholder den binære representasjonen av tallet 64 = 1000000), blir ubetydelige nuller lagt til den.

Og enda et komplekst eksempel. Nummeret er 25678425.

Trinn 1: 25678425 delt på 64

Privat = 401225

Gjenstående = 25 = 011001

Trinn 2: 401225 delt på 64

Kvotient = 6269

Resten = 9 = 001001

Trinn 3: 6269 delt på 64

Kvotient = 97

Gjenstående = 61 = 111101

Trinn 4: 97 delt på 64

Kvotient = 1 = 000001

Gjenstående = 33 = 100 001

Tallresultat = 1.100001.111101.001001.011001

I dette tallet er mellomresultatene som er inkludert i det atskilt med en prikk.

Konverter tall til binær representasjon:

VEDLEGG: TABELL 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

Å utføre aritmetiske operasjoner i et hvilket som helst posisjoneltallsystem utføres i henhold til de samme reglene som brukes i desimaltallsystemet.

Akkurat som i desimaltallsystemet, for å utføre aritmetiske operasjoner må du kjenne addisjons- (subtraksjons-) og multiplikasjonstabellene.

Addisjons-, subtraksjons- og multiplikasjonstabell for det binære tallsystemet

Legge til binære tall

Addisjon i det binære tallsystemet følger de samme reglene som i desimaltallsystemet. To tall er skrevet i en kolonne på linje med separatoren for heltalls- og brøkdelene og, om nødvendig, supplert til høyre med ubetydelige nuller. Addisjon starter fra sifferet lengst til høyre. To lavere-ordens enheter kombineres til en høyere-ordens enhet.

Eksempel: 1011,1 2 + 1010,11 2

Situasjonen er også interessant når mer enn to tall legges til. I dette tilfellet er overføring gjennom flere sifre mulig.
Eksempel: 111,1 2 + 111 2 + 101,1 2

Når du legger til på en-plassen (bit 0), er det 4 ener, som, når de kombineres, gir 100 2 . Derfor, fra null-sifferet til det første sifferet, overføres det 0 , og i den andre - 1 .
En lignende situasjon oppstår i det andre sifferet, der, tatt i betraktning de to overførte enhetene, oppnås nummeret 5 = 101 2 . 1 forblir i den andre kategorien, 0 overført til den tredje og 1 overført til den fjerde.

Subtrahere binære tall

I tilfeller hvor en enhet av seniorkategorien er engasjert, gir den to enheter av juniorkategori. Hvis en enhet studeres etter flere kategorier, gir den én enhet i alle mellomliggende nullkategorier og to enheter i kategorien den ble studert for.
Eksempel: 10110,01 2 — 1001,1 2

Aritmetiske operasjoner i alle posisjonstallsystemer utføres etter de samme reglene som er godt kjent for deg.

Addisjon. La oss vurdere å legge til tall i det binære tallsystemet. Den er basert på en tabell for å legge til ensifrede binære tall :

Det er viktig å ta hensyn til det faktum at når du legger til to, renner sifferet over og overføres til det mest signifikante sifferet. Et sifferoverløp oppstår når verdien av tallet i det blir lik eller større enn grunntallet.

Addisjonen av multi-bit binære tall skjer i samsvar med addisjonstabellen ovenfor, og tar hensyn til mulige overføringer fra lavordens til høyordenssiffer.

Som et eksempel, la oss legge til de binære tallene 110 2 og 11 2 i en kolonne :

La oss sjekke riktigheten av beregningene ved å legge til desimaltallsystemet. La oss konvertere binære tall til desimaltallsystemet og legge dem til:

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 .

La oss nå konvertere resultatet av binær addisjon til et desimaltall:

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

La oss sammenligne resultatene - tillegget ble utført riktig.

Subtraksjon. La oss se på å subtrahere binære tall. Den er basert på en tabell for subtrahering av ensifrede binære tall. Når du trekker et større tall (1) fra et mindre tall (0), lånes det fra det høyeste sifferet. I tabellen er lånet betegnet 1 med en linje:

Subtraksjon av multi-bit binære tall skjer i samsvar med subtraksjonstabellen ovenfor, og tar hensyn til mulige lån fra de mest signifikante bitene. Som et eksempel, la oss trekke fra de binære tallene 110 2 og 11 2:

Multiplikasjon. Multiplikasjon er basert på multiplikasjonstabellen for ensifrede binære tall:

Multiplikasjon av flersifrede binære tall skjer i samsvar med multiplikasjonstabellen ovenfor i henhold til det vanlige skjemaet som brukes i desimaltallsystemet med sekvensiell multiplikasjon av multiplikanden med sifrene til multiplikatoren. Som et eksempel, la oss multiplisere binære tall og:

Inndeling. Delingsoperasjonen utføres ved å bruke en algoritme som ligner på algoritmen for å utføre delingsoperasjonen i desimaltallsystemet. Som et eksempel, la oss dele det binære tallet 110 2 og 11 2: