Data aktualizacji: 30 stycznia 2023

Operacje na systemie binarnym

System binarny:

Ważnym tematem omawianym na naszym kursie informatyki 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.

Owe dwa stany oznaczają – prawdę lub fałsz, włączony lub wyłączony, prąd płynie lub nie płynie. Bardzo wygodnie można zatem ich używać w operacjach logicznych takich jak koniunkcja czy alternatywa, których używa się z kolei do budowania bardziej skomplikowanych systemów takich jak jednostki arytmetyczno-logiczne, które zajmują się realizowaniem obliczeń i operacji logiczn96ych w procesorach.

Operacje na systemie binarnym:

Najprostsze operacje na liczbach – dodawanie, odejmowanie, dzielenie, mnożenie, przestają być tak proste w zrozumieniu, gdy nie wykonujemy ich na systemie dziesiątkowym, chociaż tak naprawdę rządzą się tymi samymi zasadami.

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 wykonujemy obliczenia bez pomocy komputera, a znaczenie ma czas wykonania operacji? Co więcej, komputery same w sobie wszystkie obliczenia przeprowadzają wewnętrznie na systemie binarnym, więc nie mają one luksusu wykonywania obliczeń na systemie dziesiętnym.

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, wliczając w to bity przeniesione
  • jeżeli suma bitów jest nieparzysta (1 lub 3), wynikiem w tej kolumnie jest 1
  • jeżeli suma bitów jest większa lub równa 2, do następnej kolumny przenosimy 1 (z ang. carry)
  • jeżeli suma bitów jest równa 0, wynikiem w tej kolumnie jest 0

Oznacza to że:

  • 1 + 1 = 10 (1przeniesione, 0 w kolumnie)
  • 1 + 0 lub 0 + 1 = 1
  • 0 + 0 = 0
  • 1 + 1 + 1 = 11 (1 przeniesione, 1 w kolumnie)

Przykład dla liczb zapisanych na 4 bitach (mniejszą liczbą dopełniliśmy z lewej strony zerami):

1101 + 0011 = 10000

Dodawanie w systemie binarnym

Przykładowe dodawanie w systemie binarnym.

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. Co ciekawe dodając analogicznie liczby w systemie dziesiętnym złożone z samych dziewiątek, również będziemy potrzebowali jednej cyfry więcej. Prawidłowość ta występuje dla dowolnych systemów pozycyjnych.

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 bity są sobie równe (różnica wynosi zero), wynikiem w kolumnie również jest 0
  • jeżeli przy kolejnych odejmowaniach zabraknie znaków, a nadal musimy odejmować przeniesienie, to należy dopisać do liczby zera
  • bity przeniesione odejmujemy dodatkowo od różnic liczb w kolumnach

Oznacza to, że:

  • 1 - 1 lub 0 - 0 = 0
  • 1 - 0 = 0
  • 0 - 1 = 1 w kolumnie niżej, -1 przeniesione
  • 1 - 1 - 1 to sytuacja taka sama jak 0 - 1 więc 1 w kolumnie niżej, -1 przeniesione

Przykład:

1101 – 11 = ?

Odejmowanie w systemie binarnym

Przykładowe odejmowanie 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 najmniej znaczącą cyfrę liczby dolnej, następnie przez drugą najmniej znaczącą...
  • 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 = ?

Mnożenie w systemie binarnym

Przykładowe mnożenie 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:
    Dzielenie w systemie binarnym

    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 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 lub 7, to znaczy, że początkowa wartość liczby też była podzielna przez 7
  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 binarne

Kolejne wykonania tego algorytmu.

system binarny działania

Kolejne wykonania tego algorytmu.

system dwójkowy

Kolejne wykonania tego algorytmu.

system dwójkowy działania

Kolejne wykonania tego algorytmu.

binarny na dziesiętny

Uzyskaliśmy wynik niepodzielny.

[ podzielność przez 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ę

Ciekawostka:

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.

Jak oceniasz ten artykuł?

Przykro nam 🙁 , że ten wpis nie był dla Ciebie wystarczająco przydatny!

Będziemy wdzięczni jeżeli napiszesz co moglibyśmy poprawić.

Najnowsze wpisy

Wyszukiwanie Google - wyszukiwanie informacji w Internecie krok po kroku

Przeczytaj >>

Jak sprawdzić komputer przed maturą z informatyki?

Przeczytaj >>

Czy warto zapisać dziecko na programowanie dla przedszkolaków?

Przeczytaj >>

Pierwszy krok ku karierze, czyli jaką wiedzę potrzebuję, aby zacząć pracę w IT jako programista?

Przeczytaj >>

Czy można zostać programistą bez studiów informatycznych?

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Ę KUrSÓW
© Ambitni Szkoła Informatyki 011111100101(2) | jesteś niemal gotowy!
crossmenu