Operacje logiczne na bitach


Podrozdziały Tematy pokrewne

 

Operacje logiczneGeorge Boole

Rozwój komputerów i techniki cyfrowej nie byłby możliwy bez podstawowego wynalazku, którym niewątpliwie jest algebra Boole'a. Jest to zbiór reguł wykonywania operacji na wartościach logicznych, czyli takich które mogą przyjmować wartość prawdy (true) lub fałszu (false). Algebrę tę po raz pierwszy opisał i systematyzował matematyk angielski George Boole.

W algebrze Boole'a (podobnie jak w zwykłej algebrze) istnieją operacje elementarne które można wykonywać nad wartościami logicznymi. Są to:

Bity są idealne do reprezentowania wartości logicznych. Umówmy się, iż wartość logiczną fałszu będziemy reprezentować stanem bitu 0, a wartość prawdy stanem 1.

 

Negacja - zaprzeczenie logiczne

Jest to operacja jednoargumentowa, tzn. rezultat zależy tylko od jednego argumentu. Wynikiem jest wartość logiczna przeciwna do tej, którą ma argument negacji.

 

Negacja
a NOT a
0 1
1 0

 

Jeśli operację negacji wykonamy nad słowem binarnym, to w wyniku otrzymamy słowo, w którym wszystkie bity mają wartości przeciwne do słowa wyjściowego.

 

Przykład:

NOT    1110111100100011001001001001010100100111
  0001000011011100110110110110101011011000

 

Alternatywa - suma logiczna

 

Alternatywa
a b a OR b
0 0 0
0 1 1
1 0 1
1 1 1

 

Jeśli porównasz tabelkę alternatywy z tabliczką dodawania w systemie binarnym, to na pewno zauważysz duże podobieństwo. Różnica jest w ostatnim wierszu - dla obu argumentów równych 1 alternatywa daje 1, a suma binarna 10. Oczywiście jest to spowodowane faktem, iż operatory logiczne dają w wyniku zawsze wartości logiczne, czyli 0 lub 1. Mnemotechnicznie zapamiętajmy, iż alternatywa daje tylko wtedy 0, gdy wszystkie argumenty mają wartość 0 i 1 w przypadku przeciwnym.

Jeśli wykonamy operację alternatywy nad dwoma słowami binarnymi, to w wyniku otrzymamy słowo binarne, którego bity są wynikami operacji alternatywy nad odpowiadającymi im bitami argumentów.

 

Przykład:

  11000101001011
OR    10101011011000
  11101111011011

 

Koniunkcja - iloczyn logiczny

 

Koniunkcja
a b a AND b
0 0 0
0 1 0
1 0 0
1 1 1

 

Porównaj tabelkę koniunkcji z tabliczką mnożenia w systemie dwójkowym. Mnemotechnicznie zapamiętajmy, iż koniunkcja przyjmuje wartość 1, gdy wszystkie jej argumenty mają wartość 1 i 0 w przeciwnym wypadku.

Jeśli wykonamy operację koniunkcji nad dwoma słowami binarnymi, to w wyniku otrzymamy słowo binarne, którego bity są wynikami operacji koniunkcji nad odpowiadającymi im bitami argumentów.

 

Przykład:

  11000101001011
AND    10101011011000
  10000001001000

 

Różnica symetryczna - suma modulo dwa

Operacja różnicy symetrycznej nie jest operacją elementarną, jednakże często przydaje się przy wielu okazjach. Jest to operacja dwuargumentowa.

 

Różnica symetryczna
a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

 

Mnemotechnicznie zapamiętajmy, iż wynikiem różnicy symetrycznej jest 1 tylko wtedy, gdy dokładnie jeden z argumentów ma wartość 1 i 0 w przeciwnym przypadku.

Jeśli wykonamy operację różnicy symetrycznej nad dwoma słowami binarnymi, to w wyniku otrzymamy słowo binarne, którego bity są wynikami tej operacji nad odpowiadającymi im bitami argumentów.

 

Przykład:

  11000101001011
XOR    10101011011000
  01101110010011

 


DLA
GENIUSZA

Zastosowania operacji logicznych

Ustawianie zadanego bitu

W słowie binarnym chcemy ustawić n-ty bit na 1. W tym celu przygotowujemy maskę o długości słowa binarnego, w której wszystkie bity są wyzerowane z wyjątkiem bitu n-tego. Następnie wykonujemy operację alternatywy nad słowem binarnym i maską. W wyniku n-ty bit słowa zostanie ustawiony na 1.

 

Przykład:

Ustawiamy trzeci (uwaga - bity numerujemy od 0!) bit w słowie binarnym 110001010011.

 

  110001010011  zmieniane słowo
OR    000000001000  maska bitowa
  110001011011  wynik operacji

 

Zerowanie zadanego bitu

Operacją odwrotną do ustawiania bitu jest oczywiście jego zerowanie. W tym celu tworzymy maskę, w której wszystkie bity są ustawione na 1 z wyjątkiem bitu na pozycji do wyzerowania. Następnie wykonujemy operację koniunkcji nad słowem zawierającym bit oraz maską. W wyniku otrzymujemy słowo z wyzerowanym bitem na zadanej pozycji.

 

Przykład:

Zerujemy trzeci (uwaga - bity numerujemy od 0!) bit w słowie binarnym 110001011111.

 

  110001011111  zmieniane słowo
AND    111111110111  maska bitowa
  110001010111  wynik operacji

 

Negacja zadanego bitu

Operacja ta polega na zmianie stanu wybranego bitu na przeciwny. W tym celu przygotowujemy maskę z wyzerowanymi bitami za wyjątkiem pozycji do zamiany stanu. Nad słowem i maską wykonujemy operację różnicy symetrycznej.

 

Przykład:

Zmieniamy stan trzeciego (uwaga - bity numerujemy od 0!) bitu w słowie binarnym 110001010111.

 

  110001010111  zmieniane słowo
XOR    000000001000  maska bitowa
  110001011111  wynik operacji

 

Zastępowanie bitu/bitów

W tym przypadku mamy dwa słowa binarne. W drugim słowie chcemy zastąpić wybrany bit bitem ze słowa pierwszego. Operacja ta jest złożona i wymaga ciągu działań logicznych. Najpierw przygotowujemy maskę z ustawionym bitem na pozycji wymiany bitów. Nad pierwszym słowem i maską wykonujemy operację koniunkcji. W wyniku otrzymujemy nową maskę, w której bity niezmienione mają wartość 0, a bit na pozycji wymiany ma wartość taką jak w słowie pierwszym. Pierwszą maskę negujemy. W efekcie bity na pozycjach niezmienionych otrzymają wartość 1, a na pozycji wymiany bit będzie miał wartość 0. Maskę tę wykorzystujemy do wyzerowania bitu w drugim słowie operacją koniunkcji. Teraz łączymy za pomocą alternatywy maskę otrzymaną po pierwszej operacji z drugim słowem. W efekcie w drugim słowie na pozycji wymiany otrzymamy bit ze słowa pierwszego.

 

Przykład:

Mamy dane dwa 8-bitowe słowa binarne: 10110111 i 11101101. W drugim słowie chcemy zastąpić cztery najmłodsze bity odpowiadającymi im bitami ze słowa pierwszego. Najpierw wycinamy bity z pierwszego słowa:

 

  10110111  pierwsze słowo
AND    00001111  maska
  00000111  maska z wyciętymi bitami

 

Teraz w drugim słowie zerujemy bity, które mają być zastąpione:

 

  11101101  drugie słowo
AND    11110000  maska
  11100000  drugie słowo z wyzerowanymi bitami

 

Łączymy maskę z wyciętymi bitami z drugim słowem z wyzerowanymi bitami:

 

  11100000  drugie słowo z wyzerowanymi bitami
OR    00000111  maska z wyciętymi bitami
  11100111  wynik operacji

 

W efekcie w drugim słowie cztery najmłodsze bity pochodzą ze słowa pierwszego:

 

10110111 – pierwsze słowo
11101101 – drugie słowo
11100111 – wynik

 

Prawa DeMorgana

Przy przekształcaniu wyrażeń logicznych korzysta się często z dwóch prostych praw zwanych prawami DeMorgana. Ich zapis słowny brzmi następująco:

  1. Negacja alternatywy jest równa koniunkcji negacji: NOT(a OR b) = (NOT a) AND (NOT b).
  2. Negacja koniunkcji jest równa alternatywie negacji: NOT(a AND b) = (NOT a) OR (NOT b).

Prawa De Morgana udowadniamy za pomocą tabelek, w których konstruujemy wyniki wyrażenia po lewej i po prawej stronie równości i sprawdzamy, czy otrzymaliśmy to samo. Jeśli tak, to prawo zostaje udowodnione:

 

NOT(a OR b) = (NOT a) AND (NOT b)
a b a OR b NOT(a OR b) NOT a NOT b NOT(a) AND NOT(b)
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0


NOT(a AND b) = (NOT a) OR (NOT b)
a b a AND b NOT(a AND b) NOT a NOT b NOT(a) OR NOT(b)
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

 

Prawa De Morgana pokazują nam, iż tak naprawdę potrzebne są tylko dwie operacje pierwotne (negacja i koniunkcja) lub (negacja i alternatywa). Drugą operację zawsze możemy wyprowadzić z pierwszej za pomocą odpowiednich przekształceń logicznych:

 

Przykład:

Koniunkcja:  a AND b =  NOT(NOT(a AND b)) =  NOT(NOT(a) OR NOT(b))
Alternatywa:  a OR b = NOT(NOT(a OR b)) =  NOT(NOT(a) AND NOT(b))

 

Więcej na ten temat znajdziesz w instrukcji do Przykładowej Maszyny Cyfrowej.

 

Zadania

Zadanie 1 (łatwe)

Wykonaj podane niżej operacje logiczne:
1001 OR 0101  =   

.

1110 AND 0101 =   

.

NOT 10111010 =   

.

11011001 XOR 11111111  =   

.

1101 AND 0111 XOR 1111 =   

.

 

Zadanie 2 (średnie)

Wyprowadź wzór na operację XOR wykorzystując tylko operację NOT oraz AND.

 

Zadanie 3 (średnie)

Jak sprawdzisz, czy n-ty bit danego słowa binarnego jest ustawiony na 1 lub na 0? Podaj odpowiedni przykład.

 

Zadanie 4 (średnie)

Jak sprawdzić za pomocą operacji logicznych, czy dana liczba binarna jest nieparzysta?

 


Zobacz dalej...

Kody binarne | Naturalny system dwójkowy | Dwójkowy system stałoprzecinkowy | Operacje arytmetyczne w systemie dwójkowym | Konwersje dwójkowo ósemkowe i szesnastkowe



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.