17 kwietnia 2021

Operacje na systemie binarnym

System binarny:

Ważnym tematem omawianym na naszym kursie są systemy liczbowe

Informatyka od zawsze bazowała na systemie binarnym.

Jest to dwójkowy system liczbowy – oznacza to, że zapis dowolnej liczby jest tworzony przy użyciu tylko dwóch cyfr – 0 i 1.

system binarny

Podstawowym systemem liczbowym w informatyce jest system binarny - posługujący się jedynie znakami 0 oraz 1.

Powszechnie stosuje się go nie tylko w informatyce ze względu na sposób zapisu liczb – ograniczenie każdej pozycji do dwóch stanów – 1 lub 0 sprawia, że system binarny jest uniwersalny do różnego typu operacji, oraz stworzenia fizycznego urządzenia, które będzie działać na nim.

Owe dwa stany oznaczają – prawdę lub fałsz, włączony lub wyłączony, prąd płynie lub nie płynie.

Operacje na systemie binarnym:

Najprostsze operacje związane na liczbach – dodawanie, odejmowanie, dzielenie, mnożenie, przestają być tak proste w zrozumieniu, gdy nie wykonujemy ich na systemie dziesiątkowym.

W końcu system dziesiątkowy, w przeciwieństwie do innych, jest wykorzystywany w niemal wszystkich dziedzinach życia – ceny w sklepach, informacje zapisane w dowodzie czy wszędzie gdzie chcemy określić ile czegoś jest.

Do ręcznego wykonania operacji na dowolnym systemie liczbowym zazwyczaj można zwyczajnie zamienić liczbę na system dziesiętny, wykonać operację a następnie z powrotem zamienić liczbę z dziesiątkowej, na interesujący nas system.

Co jednak, gdy to nie wystarcza – na przykład kiedy znaczenie ma czas wykonania operacji, lub zamieniona liczba nie zmieści się w typie liczbowym podczas wykonywania programu?

Dodawanie w systemie binarnym:

Operacja sumowania dwóch liczb w systemie dwójkowym odbywa się następująco:

  • począwszy od bitu o najmniejszej znaczności (skrajnie prawego) dodajemy do siebie bity o tych samych pozycjach
  • jeżeli suma bitów jest równa 2, to zapisujemy 1 a następnie do sumy następnych bitów dodajemy 1 (tzw. przeniesienie)

Przykład dla liczb zapisanych na 4 bitach:

1101 + 0011 = ?

system binarny

Przykładowa operacja na systemie dwójkowym.

Uwaga:

W komputerze liczby binarne są przechowywane w konkretnej ilości bitów (8, 16, 32, itd.). Jeżeli nasza suma będzie musiała być zapisana na większej ilości bitów, niż zakładaliśmy nastąpi tzw. overflow (nadmiar lub przepełnienie). W sytuacji wystąpienia overflow, utracona zostaje wartość bitu o największym znaczeniu.

Na przykład gdy miejsce przeznaczone na dodawanie jest ustalone na 4 bity:

1111(2) + 0001(2) = (1)1111 – wartość piątego bitu zostanie utracona.

Można temu zapobiec zawczasu alokując więcej pamięci na sumę, niż potrzebowaliśmy do zapisania.

W skrajnej sytuacji np. 1111 + 1111 = 11110, czyli nawet dla liczb złożonych z samych jedynek, na zapisanie sumy będziemy potrzebować maksymalnie 1 bitu więcej.

Odejmowanie w systemie binarnym:

Operacja odejmowania binarnego odbywa się na podobnych zasadach jak dodawania, z tą różnicą, że zamiast przeniesienia, mamy zapożyczenie:

  • począwszy od bitu o najmniejszej znaczności (skrajnie prawego) odejmujemy od siebie bity o tych samych pozycjach
  • jeżeli różnica bitów jest równa -1, to zapisujemy 0, a następnie od różnicy następnych bitów odejmujemy 1 (tzw. zapożyczenie)
  • jeżeli przy kolejnych odejmowaniach zabraknie znaków, a nadal musimy odejmować przeniesienie, to należy dopisać do liczby zera

Przykład:

1101 – 11 = ?

system dwójkowy

Przykład odejmowania w systemie binarnym.

Uwaga:

Podobnie jak przy operacji dodawania, jeżeli będziemy nieostrożni, to możemy wyjść poza zakres bitowy przeznaczony na zapisanie wyniku odejmowania. Nastąpi wtedy sytuacja przeciwna do „przepełnienia” - czyli underflow (niedomiar). Sytuacja taka wystąpi, gdy od mniejszej liczby odejmiemy mniejszą – naturalny system binarny nie jest przystosowany do kodowania liczb ujemnych. Próba odjęcia zapożyczenia od bitu niebędącego w zakresie sprawi, że zwrócony wynik będzie wartością maksymalną jaką można zapisać na danej ilości bitów.

Przykład dla liczb zapisanych na 4 bitach:

0000 (2) – 0001 (2) = 1111

Aby zapobiec takiej sytuacji, należy sprawdzić która liczba jest większa:

  1. Jeżeli liczba od której odejmujemy jest większa od odejmowanej, to odejmowanie przeprowadzamy standardowo
  2. Jeżeli liczba od której odejmujemy jest mniejsza od odejmowanej, to odejmowanie przeprowadzamy odwrotnie – liczba od której mieliśmy odejmować staje się odejmowaną, natomiast odejmowana będzie liczbą od której będziemy odejmować. Następnie wynik należy zapisać ze znakiem ‘’-‘’.

Mnożenie w systemie binarnym:

Ustawiamy obie liczby jedna pod drugą w taki sposób, aby ich bity o tej samej znaczności znalazły się w jednej kolumnie (wygodniej jest dłuższą zapisać nad krótszą).

Następnie stosujemy zwykłe mnożenie „pisemne”:

  • Mnożymy każdą cyfrę liczby górnej przez liczbę dolną
  • Wynik operacji mnożenia cyfry przez liczbę zapisujemy od kolumny w której znajduje się nasz mnożnik
  • Dla ułatwienia puste kolumny można uzupełnić zerami, a następnie sumujemy wszystkie powstałe liczby

Przykład:

101 * 1011 = ?

binarny na dziesiętny

Operacja mnożenia w systemie binarnym.

Dzielenie w systemie binarnym:

Operację dzielenia binarnego można przeprowadzić ręcznie korzystając z metody „pisemnej” tak, jak to robimy w systemie dziesiętnym.

Kiedy jednak chcemy podzielić dwie liczby binarne w programie komputerowym, należy:

  1. Sprawdzamy, czy |dzielna| > |dzielnik|. Jeżeli nie, to ilorazem będzie 0, natomiast resztą z dzielenia będzie dzielna. W przeciwnym wypadku wykonujemy dzielenie.
  2. Dla dzielnika x-cyfrowego, przeprowadzamy następujące operacje na x cyfrach dzielnej licząc od lewej:
  • Jeżeli dzielnik jest większy od x cyfr dzielnej, to dodajemy 0 do listy, która zwróci iloraz. W następnym działaniu sprawdzimy, czy x + 1 (jeżeli sytuacja się powtórzy, to x + 2, x + 3, …, itd.) cyfr dzielnej od lewej jest większe od dzielnika.
  • W przeciwnym wypadku dodajemy do listy 1 a następnie „obcinamy” (na przykład poprzez odjęcie) pierwszą cyfrę dzielnej licząc od lewej.

Przykład:

1010 : 11 = ?

  1. Porównujemy dwie pierwsze liczby dzielnej z dzielnikiem:

    zapis binarny

    Porównanie liczb z dzielnikiem.

  1. Dzielnik jest większy, więc ponawiamy operację na 3 pierwszych liczbach dzielnej:

    dzielenie binarne

    Kontynuujemy operację.

  2. Dzielnik jest mniejszy, więc przeprowadzamy dzielenie:

    konwerter systemów liczbowych

    Przeprowadzamy dzielenie.

  3. Powtarzamy to, aż dzielna będzie mniejsza od dzielnika:

    mnożenie binarne

    Kontynuujemy działanie do czasu, aż liczba będzie mniejsza od dzielnika.

Dzielna „0001” jest mniejsza od dzielnika „11”, więc resztą z dzielenia będzie „0001” a ilorazem liczba, którą zapisaliśmy nad kreską dzielenia – „11”.

Podzielność liczb w systemie binarnym:

[ 2 ] – jeżeli ostatni bit (skrajnie po prawej) jest równy 0, to liczb jest parzysta.

[ 3 ] – zasada wygląda następująco:

  1. Wyznaczamy sumę bitów nieparzystych oraz sumę bitów parzystych.
  2. Odejmujemy od siebie te sumy.
  3. Jeżeli różnica sum jest podzielna przez 3, to cała liczba też dzieli się przez 3 całkowicie.

[ 5 ] – sposób działania:

  1. Wyznaczamy reszty z dzielenia kolejnych bitów przez 5, można tu zauważyć pewien wzór:
  • 1 % 5 = 1
  • 2 % 5 = 2
  • 4 % 5 = 4
  • 8 % 5 = 3
  • 16 % 5 = 1
  • 32 % 5 = 2
  • 64 % 5 = 4
  • 128 % 5 = 3
  • 256 % 5 = 1

czyli możemy kolejne reszty z dzielenia to: 1, 2, 4, 3, 1, 2, 4, 3, 1, …

  1. Każdy bit następnie mnożymy przez jego resztę z dzielenia przez 5.
  2. Jeżeli suma tych iloczynów jest podzielna przez 5, to cała liczba dzieli się przez 5 całkowicie.

[ 7 ] – sposób działania:

  1. „Wyciągamy” bit o najmniejszej znaczności z liczby – tj. zapamiętujemy jego wartość, oraz resztę która została.
  2. Odejmujemy od reszty podwojoną wartość wyciągniętego bitu – tj. dla bitu „1” odejmujemy od reszty „11”.
  3. Jeżeli wynik różnicy jest podzielny przez 7, to znaczy, że początkowa liczba dzieli 7 całkowicie.

Przykład:

Przyjmijmy liczbę – 28 (10) = 11100 (2)

11100 | 111 → ?

1.

Ostatni = 0

Reszta  = 1110

2.

Różnica = 1110 – 00 = {14 – 0 } = 1110 (2) = 14 (10)

3.

(1110 | 111 ⇔ 14 | 7 ) => (11100 | 111 ⇔ 28 | 7)

Jest co ciekawy sposób podejścia, ale czy aby na pewno przydatny? Nie koniecznie możemy znać przecież wartość dziesiętną różnicy. Czy można zmodyfikować ten sposób, aby nie trzeba było zamieniać liczby na system dziesiątkowy?

Sprawdźmy jak algorytm zachowa się dla liczby 7:

111 | 111 → ?

1.

Ostatni = 1

Reszta = 11

2.

Różnica = 11 – 11 = 0

Wiemy już, że dla liczby 7, algorytm zwraca 0. Ponadto z zasady działania wiemy, że jeżeli wynik różnicy jest podzielny przez 7, to liczba też dzieli się przez 7 całkowicie.

Można więc używać algorytmu tak wiele razy, aż napotkamy jedną z dwóch „instrukcji stop”:

  1. Jeżeli wynik = 0, to znaczy, że początkowa wartość liczby też była podzielna przez 0
  2. Jeżeli (wynik < 7) i (wynik != 0), to znaczy, że liczba nie była podzielna

W przeciwnym wypadku powtarzamy działanie algorytmu.

Przykład:

101110 | 7 = ?

Pierwsze wykonanie algorytmu wyglądać będzie następująco:

co to jest system binarny

Pierwsze wykonanie algorytmu.

Następne wykonania algorytmu:

odejmowanie w systemie binarnym

Kolejne wykonania tego algorytmu.

system binarny

Kolejne wykonania tego algorytmu.

system dwójkowy

Kolejne wykonania tego algorytmu.

system dwójkowy

Kolejne wykonania tego algorytmu.

binarny na dziesiętny

Uzyskaliśmy wynik niepodzielny.

[kolejne potęgi liczby 2]

Przyjmijmy n za dowolną potęgę 2.

Jeżeli wszystkie bity o mniejszej znaczności od bitu, którego wartość wynosi n wynoszą 0, to liczba ta jest podzielna przez n.

Przykład:

110101000 (2)

Dla n = 4:

Nasz bit kodujący liczbę n, znajduje się na 3 pozycji licząc od najmniej znaczącego bitu, czyli:

110101000 (2)

Wszystkie bity przed nim są równe 0, więc liczba ta, jest podzielna przez 4.

110101000 (2) = 424 (10)

424 | 4 = Prawda → zgadza się

Dla n = 16:

110101000 (2)

Nie wszystkie bity przed nim są równe 0, więc ta liczba nie jest podzielna przez 16.

424 | 16 = Fałsz → zgadza się

Przypisy:

Korzystając z powyższych zasad, można w prosty sposób sprawdzić podzielność naszej liczby, przez liczby złożone – na przykład aby liczba była podzielna przez 12, musi się ona dzielić przez 4 (potęgę dwójki) oraz 3.

Najnowsze wpisy

Jak pomóc dziecku w nauce programowania? Poradnik dla rodziców

Przeczytaj >>

Dlaczego warto uczyć dzieci programowania? – jakie umiejętności rozwija programowanie?

Przeczytaj >>

Python a C++

Przeczytaj >>

Algorytm Euklidesa w języku Python

Przeczytaj >>

10 podstawowych funkcji Excela, które trzeba znać

Przeczytaj >>

JESTEŚ AMBITNY?

Dołącz do nas jeszcze dziś i rozwijaj się w swojej ulubionej dziedzinie we współpracy z nauczycielami, którzy są autorami artykułów na naszym blogu!
POZNAJ OFERTĘ KUSÓW
© Ambitni Szkoła Informatyki 011111100101(2) | jesteś niemal gotowy!
crossmenu