algorytm.org

Operacje bitowe

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Operacje bitowe
Ocena użytkowników:***** / 63
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 01 października 2008 17:42

Poniżej zdefiniujemy operacje bitowe oraz przykłady ich zastosowania podczas programowania.

  • Operacja bitowa "i" (ang. bitwise and)

    Jest to operacja dwuargumentowa. W językach programowania bądź w pseudokodzie zapisywana jest z reguły jako:
    a and b
    a & b
    Wynikowy bit jest ustawiany na 1 tylko wówczas gdy obydwa bity argumentów ustawione są na 1. Możemy zatem powiedzieć, że wynikiem jest 1 gdy bit a i bit b są ustawione na 1. Tabela wyników dla tego działania jest następująca:

    a AND bb=0b=1
    a=000
    a=101
    Przykład:

    0101 and 1100 = 0100


  • Operacja bitowa "lub" (ang. bitwise or)

    Jest to operacja dwuargumentowa. W językach programowania bądź w pseudokodzie zapisywana jest z reguły jako:
    a or b
    a | b
    Wynikowy bit jest ustawiany na 1 tylko wówczas gdy przynajmniej jeden bit, któregoś z argumentów ustawiony jest na 1. Możemy zatem powiedzieć, że wynikiem jest 1 gdy bit a lub bit b jest ustawiony na 1. Tabela wyników dla tego działania jest następująca:

    a OR bb=0b=1
    a=001
    a=111
    Przykład:

    0101 and 1100 = 1101


  • Operacja bitowa "albo" (ang. bitwise xor)

    Jest to operacja dwuargumentowa, zwana też alternatywą wykluczającą. W językach programowania bądź w pseudokodzie zapisywana jest z reguły jako:
    a xor b
    a ^ b
    Wynikowy bit jest ustawiany na 1 tylko wówczas gdy dokładnie jeden bit, któregoś z argumentów ustawiony jest na 1. Możemy zatem powiedzieć, że wynikiem jest 1 gdy bit a albo bit b jest ustawiony na 1. Tabela wyników dla tego działania jest następująca:

    a XOR bb=0b=1
    a=001
    a=110
    Przykład:

    0101 and 1100 = 1001


  • Zaprzeczenie bitowe, dopełnienie bitowe (ang. bitwise not, complement)

    Jest to operacja jednoargumentowa. W językach programowania bądź w pseudokodzie zapisywana jest z reguły jako:
    not a
    ~ b
    Wynikowy bit jest ustawiany na 1 tylko wówczas gdy bit argumentu jest ustawiony na 0. Możemy zatem powiedzieć, że wynikiem jest 1 gdy bit a nie jest ustawiony na 1. Tabela wyników dla tego działania jest następująca:

    aNOT a
    01
    10
    Przykład:

    not 0101 = 1010


  • Przesunięcie bitowe w lewo (ang. shift left)

    Jest to operacja dwuargumentowa. W językach programowania bądź w pseudokodzie zapisywana jest z reguły jako:
    a shl b
    a << b
    Operacja polega na przesunięciu a o b bitów w lewo. Przy czym bity pojawiające się z prawej strony (uzupełniające przesunięcie) są ustawiane na 0. Operacja ta jest równoważna mnożeniu przez 2. Przesunięcie o 1 bit to przemnożenie a przez 2, przesunięcie o 2 bity to dwukrotne pomnożenie a przez 2, itd.

    Przykład:

    0101 shl 3 = 0101000


  • Przesunięcie bitowe w prawo (ang. shift right)

    Jest to operacja dwuargumentowa. W językach programowania bądź w pseudokodzie zapisywana jest z reguły jako:
    a shr b
    a >> b
    Operacja polega na przesunięciu a o b bitów w prawo. Operacja ta jest równoważna dzieleniu całkowitemu przez 2. Przesunięcie o 1 bit to podzielenie a przez 2, przesunięcie o 2 bity to dwukrotne podzielenie a przez 2, itd.

    Przykład:

    010110 shr 3 = 010


Przykłady zastosowania:

  • Operacje na pojedynczym bicie

    Załóżmy, że mamy dany rejestr, w którym poszczególne bity odpowiadają za włączanie i wyłączanie poszczególnych funkcjonalności. Chcemy w prosty sposób operować na pojedynczym bicie nie zmieniając stanu pozostałych. W tym celu zdefiniujemy sobie bit, który będzie reprezentował bit, na którym dokonujemy operacji. Wszystkie jego bity ustawione są na zero, z wyjątkiem bitu na którym będziemy operować. Operacje zdefiniujemy następująco:
    • włączenie bitu: rejestr = rejestr or bit
    • wyłączenie bitu: rejestr = rejestr and not(bit)
    • przełączenie bitu w stan przeciwny: rejestr = rejestr xor bit

    Przykład:

    Niech bit = 0100
    Włączenie bitu dla rejestr = 1001: 1001 or 0100 = 1101
    Wyłączenie bitu dla rejestr = 1101: 1101 and not(0100) = 1101 and 1011 = 1001
    Przełączenie bitu dla rejestr = 1001: 1001 xor 0100 = 1101
    Przełączenie bitu dla rejestr = 1101: 1101 xor 0100 = 1001

  • Maskowanie

    Jest to operacja wybierania z większej liczby bitów tylko, tych, które faktycznie nas interesują. W tym przypadku posłużymy się operacją i. Maska będzie wybierać nam, które bity przy porównaniu są dla nas ważne (ustawione w masce na 1). Wówczas jeżeli chcemy porównać dwie dane: dane_1 oraz dane_2 użyjemy następującej konstrukcji:
    if dane_1 and maska = dane_2 and maska then...
    Doskonałym przykładem są tutaj sieci komputerowe i sposób ich adresacji. W protokole IP wyróżniamy część adresu mówiącą o sieci, w której znajduje się dany komputer, oraz część adresu mówiącą o numerze komputera w danej sieci. By zdecydować czy dany pakiet przesłać dalej czy znajduje się on w naszej sieci musimy sprawdzić czy cześć adresu, w której zawarty jest adres sieci jest zgodny z naszą siecią. Wykonuje się to za pomocą operacji and na adresie sieci oraz masce sieci. Zatem taka decyzja wygląda wówczas następująco:
    if adres_pakietu and maska_sieci = adres_moj and maska_sieci then...

    Przykład:

    Załóżmy, że:
    adres_pakietu=11000000101010110000000100100101
    adres_moj=11000000101010110001000000010111
    maska_sieci=11111111111111110000000000000000
    Sprawdźmy czy dany pakiet adresowany jest do naszej sieci:
    adres_pakietu and maska_sieci = adres_moj and maska_sieci
    11000000101010110000000100100101 and 11111111111111110000000000000000 = 11000000101010110001000000010111 and 11111111111111110000000000000000
    11000000101010110000000000000000 = 11000000101010110000000000000000
    Równość jest spełniona zatem ten pakiet adresowany jest do naszej sieci.

  • Upakowywanie danych

    Czasem zachodzi potrzeba użycia danych o niestandardowym rozmiarze. Na przykład chcemy zapisywać bardzo wiele razy liczbę, której wartość mieści się w zakresie 0-3. Do zapisania takiego zakresu wystarczą nam dwa bity. Najmniejsza jednostka jaką możemy zapisać na dyku to bajt, który ma 8 bitów. Dlatego też, 4 takie dwubitowe wartości możemy upakować jednym bajcie. Zapis takich upakowanych wartości możemy zapisać następująco:
    • odczyt upakowanej danej:
      odpakowana = (upakowana and maska) shr start_bit
    • zapis upakowanej danej będzie przebiegał dwuetapowo, najpierw wyczyszczenie miejsca na daną, a następnie jej zapis:
      upakowana = upakowana and not(maska)
      upakowana = upakowana or (odpakowana shl start_bit)

    Maska wskazuje nam miejsce gdzie należy upakować dane, natomiast start_bit jest numerem bitu (licząc od 0 od prawej), pod którym zaczyna się dana.

    Przykład:

    Załóżmy, że mam 4 wartości: 01 11 10 01 wpisać do jednego bajta.
    Kolejne maski dla tych danych zdefiniujemy następująco: 00000011, 00001100, 00110000, 11000000.
    Kolejne bity startowe dla tych danych zdefiniujemy następująco: 0, 2, 4, 6.
    Zapiszmy zatem drugą wartość do zmiennej bajt = 01101010, miejsce, gdzie zostanie zapisana dana pogrubiono. A więc najpierw czyszczenie miejsca pod nasze dane:
    bajt = bajt and not(maska) = 01101010 and not(00001100) = 01101010 and 11110011 = 01100010.
    Teraz zapiszemy dane:
    bajt = bajt or (dane shl start_bit) = 01100010 or (11 shl 2) = 01100010 or 1100 = 01101110.
    Spróbujmy teraz odczytać te dane: dane = (bajt and maska) shr start_bit) = (01101110 and 00001100) shr 2 = 00001100 shr 2 = 11.

Poprawiony: 28 października 2012 15:37
Komentarze
photo
+2 # ARGORYTMY 2010-03-15 12:04
SUPER PODOBBAŁO MI SIĘ
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # klima7 2013-03-31 09:49
Bardzo przydatny. Tylko tak dalej!
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # Flashback 2014-04-18 00:17
Lepiej niż na ASK :)

przełknąłem tą pigułkę w mgnieniu oka i nie żałuję :)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-4 # Coder78 2014-07-22 16:37
Operacje na pojedyńczym bicie - fatalnie wytłumaczone niestety. Tak zwane tłumacznie dla siebie samego :) A szkoda.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz