Login lub e-mail Hasło   

Operacje logiczne na bitach

Odnośnik do oryginalnej publikacji: http://www.i-lo.tarnow.pl/edu/inf/alg/nu(...)ex.html
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 reg...
Wyświetlenia: 16.201 Zamieszczono 30/10/2006

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

  • negacja (zaprzeczenie logiczne - NOT)
  • alternatywa (suma logiczna - OR)
  • koniunkcja (iloczyn logiczny - AND)

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 operacją jednoargumentową, 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.

NOT    1110111100100011001001001001010100100111
  0001000011011100110110110110101011011000

Operacja alternatywy (sumy logicznej) jest operacją dwuargumentową, tzn. rezultat zależy od obu argumentów.

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.

  11000101001011
OR    10101011011000
  11101111011011

Operacja koniunkcji (iloczynu logicznego) jest również dwuargumentowa.

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.

  11000101001011
AND    10101011011000
  10000001001000

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

Suma symetryczna
a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

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

Jeśli wykonamy operację sumy 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.

  11000101001011
XOR    10101011011000
  01101110010011


DLA
GENIUSZA

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.

 

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.

 

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ę sumy symetrycznej.

 

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.

 

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:

 

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.

 

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

Podobne artykuły


16
komentarze: 5 | wyświetlenia: 9005
9
komentarze: 0 | wyświetlenia: 2782
49
komentarze: 18 | wyświetlenia: 64974
37
komentarze: 9 | wyświetlenia: 28515
17
komentarze: 4 | wyświetlenia: 14171
15
komentarze: 5 | wyświetlenia: 32760
13
komentarze: 2 | wyświetlenia: 22958
12
komentarze: 3 | wyświetlenia: 29779
12
komentarze: 2 | wyświetlenia: 18504
11
komentarze: 2 | wyświetlenia: 33151
11
komentarze: 1 | wyświetlenia: 86404
11
komentarze: 1 | wyświetlenia: 10470
10
komentarze: 1 | wyświetlenia: 34969
10
komentarze: 5 | wyświetlenia: 20413
 
Autor
Artykuł

Powiązane tematy






Brak wiadomości


Dodaj swoją opinię
W trosce o jakość komentarzy wymagamy od użytkowników, aby zalogowali się przed dodaniem komentarza. Jeżeli nie posiadasz jeszcze swojego konta, zarejestruj się. To tylko chwila, a uzyskasz dostęp do dodatkowych możliwości!
 

© 2005-2018 grupa EIOBA. Wrocław, Polska