{"id":819,"date":"2012-04-05T14:27:16","date_gmt":"2012-04-05T13:27:16","guid":{"rendered":"http:\/\/www.venco.com.pl\/~cozy\/blog\/?p=819"},"modified":"2012-04-05T14:27:16","modified_gmt":"2012-04-05T13:27:16","slug":"operacje-bitowe","status":"publish","type":"post","link":"http:\/\/u239160.webh.me\/jakisproblem.pl\/index.php\/2012\/04\/05\/operacje-bitowe\/","title":{"rendered":"Operacje bitowe"},"content":{"rendered":"<div>Poni\u017cej zdefiniujemy operacje bitowe oraz przyk\u0142ady ich zastosowania podczas programowania.<\/p>\n<ul>\n<li><strong>Operacja bitowa &#8222;i&#8221;<\/strong> (<em>ang. bitwise and<\/em>)Jest to operacja dwuargumentowa. W j\u0119zykach programowania b\u0105d\u017a w pseudokodzie zapisywana jest z regu\u0142y jako:a <strong>and<\/strong> b\n<p>a <strong>&amp;<\/strong> b<!--more--><\/p>\n<p>Wynikowy bit jest ustawiany na 1 tylko w\u00f3wczas gdy obydwa bity argument\u00f3w ustawione s\u0105 na 1. Mo\u017cemy zatem powiedzie\u0107, \u017ce wynikiem jest 1 gdy bit a <strong>i<\/strong> bit b s\u0105 ustawione na 1. Tabela wynik\u00f3w dla tego dzia\u0142ania jest nast\u0119puj\u0105ca:<\/p>\n<table border=\"1\" cellspacing=\"0\" cellpadding=\"3\" width=\"15%\" align=\"center\">\n<tbody>\n<tr>\n<td>a AND b<\/td>\n<td><strong>b=0<\/strong><\/td>\n<td><strong>b=1<\/strong><\/td>\n<\/tr>\n<tr>\n<td><strong>a=0<\/strong><\/td>\n<td>0<\/td>\n<td>0<\/td>\n<\/tr>\n<tr>\n<td><strong>a=1<\/strong><\/td>\n<td>0<\/td>\n<td>1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><em>Przyk\u0142ad<\/em>:<\/p>\n<p>0101 and 1100 = 0100<\/li>\n<li><strong>Operacja bitowa &#8222;lub&#8221;<\/strong> (<em>ang. bitwise or<\/em>)Jest to operacja dwuargumentowa. W j\u0119zykach programowania b\u0105d\u017a w pseudokodzie zapisywana jest z regu\u0142y jako:a <strong>or<\/strong> ba <strong>|<\/strong> b\n<p>Wynikowy bit jest ustawiany na 1 tylko w\u00f3wczas gdy przynajmniej jeden bit, kt\u00f3rego\u015b z argument\u00f3w ustawiony jest na 1. Mo\u017cemy zatem powiedzie\u0107, \u017ce wynikiem jest 1 gdy bit a <strong>lub<\/strong> bit b jest ustawiony na 1. Tabela wynik\u00f3w dla tego dzia\u0142ania jest nast\u0119puj\u0105ca:<\/p>\n<table border=\"1\" cellspacing=\"0\" cellpadding=\"3\" width=\"15%\" align=\"center\">\n<tbody>\n<tr>\n<td>a OR b<\/td>\n<td><strong>b=0<\/strong><\/td>\n<td><strong>b=1<\/strong><\/td>\n<\/tr>\n<tr>\n<td><strong>a=0<\/strong><\/td>\n<td>0<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td><strong>a=1<\/strong><\/td>\n<td>1<\/td>\n<td>1<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><em>Przyk\u0142ad<\/em>:<\/p>\n<p>0101 and 1100 = 1101<\/li>\n<li><strong>Operacja bitowa &#8222;albo&#8221;<\/strong> (<em>ang. bitwise xor<\/em>)Jest to operacja dwuargumentowa, zwana te\u017c alternatyw\u0105 wykluczaj\u0105c\u0105. W j\u0119zykach programowania b\u0105d\u017a w pseudokodzie zapisywana jest z regu\u0142y jako:a <strong>xor<\/strong> ba <strong>^<\/strong> b\n<p>Wynikowy bit jest ustawiany na 1 tylko w\u00f3wczas gdy dok\u0142adnie jeden bit, kt\u00f3rego\u015b z argument\u00f3w ustawiony jest na 1. Mo\u017cemy zatem powiedzie\u0107, \u017ce wynikiem jest 1 gdy bit a <strong>albo<\/strong> bit b jest ustawiony na 1. Tabela wynik\u00f3w dla tego dzia\u0142ania jest nast\u0119puj\u0105ca:<\/p>\n<table border=\"1\" cellspacing=\"0\" cellpadding=\"3\" width=\"15%\" align=\"center\">\n<tbody>\n<tr>\n<td>a XOR b<\/td>\n<td><strong>b=0<\/strong><\/td>\n<td><strong>b=1<\/strong><\/td>\n<\/tr>\n<tr>\n<td><strong>a=0<\/strong><\/td>\n<td>0<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td><strong>a=1<\/strong><\/td>\n<td>1<\/td>\n<td>0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><em>Przyk\u0142ad<\/em>:<\/p>\n<p>0101 and 1100 = 1001<\/li>\n<li><strong>Zaprzeczenie bitowe, dope\u0142nienie bitowe<\/strong> (<em>ang. bitwise not, complement<\/em>)Jest to operacja jednoargumentowa. W j\u0119zykach programowania b\u0105d\u017a w pseudokodzie zapisywana jest z regu\u0142y jako:<strong>not<\/strong> a<strong>~<\/strong> b\n<p>Wynikowy bit jest ustawiany na 1 tylko w\u00f3wczas gdy bit argumentu jest ustawiony na 0. Mo\u017cemy zatem powiedzie\u0107, \u017ce wynikiem jest 1 gdy bit a <strong>nie jest<\/strong> ustawiony na 1. Tabela wynik\u00f3w dla tego dzia\u0142ania jest nast\u0119puj\u0105ca:<\/p>\n<table border=\"1\" cellspacing=\"0\" cellpadding=\"3\" width=\"10%\" align=\"center\">\n<tbody>\n<tr>\n<td><strong>a<\/strong><\/td>\n<td><strong>NOT a<\/strong><\/td>\n<\/tr>\n<tr>\n<td>0<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td>0<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><em>Przyk\u0142ad<\/em>:<\/p>\n<p>not 0101 = 1010<\/li>\n<li><strong>Przesuni\u0119cie bitowe w lewo<\/strong> (<em>ang. shift left<\/em>)Jest to operacja dwuargumentowa. W j\u0119zykach programowania b\u0105d\u017a w pseudokodzie zapisywana jest z regu\u0142y jako:a <strong>shl<\/strong> ba <strong>&lt;&lt;<\/strong> b\n<p>Operacja polega na przesuni\u0119ciu <em>a<\/em> o <em>b<\/em> bit\u00f3w w lewo. Przy czym bity pojawiaj\u0105ce si\u0119 z prawej strony (uzupe\u0142niaj\u0105ce przesuni\u0119cie) s\u0105 ustawiane na 0. Operacja ta jest r\u00f3wnowa\u017cna mno\u017ceniu przez 2. Przesuni\u0119cie o 1 bit to przemno\u017cenie <em>a<\/em> przez 2, przesuni\u0119cie o 2 bity to dwukrotne pomno\u017cenie <em>a<\/em> przez 2, itd.<\/p>\n<p><em>Przyk\u0142ad<\/em>:<\/p>\n<p>0101 shl 3 = 0101000<\/li>\n<li><strong>Przesuni\u0119cie bitowe w prawo<\/strong> (<em>ang. shift right<\/em>)Jest to operacja dwuargumentowa. W j\u0119zykach programowania b\u0105d\u017a w pseudokodzie zapisywana jest z regu\u0142y jako:a <strong>shr<\/strong> ba <strong>&gt;&gt;<\/strong> b\n<p>Operacja polega na przesuni\u0119ciu <em>a<\/em> o <em>b<\/em> bit\u00f3w w prawo. Operacja ta jest r\u00f3wnowa\u017cna dzieleniu ca\u0142kowitemu przez 2. Przesuni\u0119cie o 1 bit to podzielenie <em>a<\/em> przez 2, przesuni\u0119cie o 2 bity to dwukrotne podzielenie <em>a<\/em> przez 2, itd.<\/p>\n<p><em>Przyk\u0142ad<\/em>:<\/p>\n<p>010110 shr 3 = 010<\/li>\n<\/ul>\n<p>Przyk\u0142ady zastosowania:<\/p>\n<ul>\n<li><strong>Operacje na pojedynczym bicie<\/strong>Za\u0142\u00f3\u017cmy, \u017ce mamy dany <em>rejestr<\/em>, w kt\u00f3rym poszczeg\u00f3lne bity odpowiadaj\u0105 za w\u0142\u0105czanie i wy\u0142\u0105czanie poszczeg\u00f3lnych funkcjonalno\u015bci. Chcemy w prosty spos\u00f3b operowa\u0107 na pojedynczym bicie nie zmieniaj\u0105c stanu pozosta\u0142ych. W tym celu zdefiniujemy sobie <em>bit<\/em>, kt\u00f3ry b\u0119dzie reprezentowa\u0142 bit, na kt\u00f3rym dokonujemy operacji. Wszystkie jego bity ustawione s\u0105 na zero, z wyj\u0105tkiem bitu na kt\u00f3rym b\u0119dziemy operowa\u0107. Operacje zdefiniujemy nast\u0119puj\u0105co:\n<ul>\n<li>w\u0142\u0105czenie bitu: <em>rejestr = rejestr or bit<\/em><\/li>\n<li>wy\u0142\u0105czenie bitu: <em>rejestr = rejestr and not(bit)<\/em><\/li>\n<li>prze\u0142\u0105czenie bitu w stan przeciwny: <em>rejestr = rejestr xor bit<\/em><\/li>\n<\/ul>\n<p><em>Przyk\u0142ad<\/em><\/p>\n<p>Niech <em>bit = 0100<\/em><\/p>\n<p>W\u0142\u0105czenie bitu dla <em>rejestr = 1001<\/em>: 1001 or 0100 = 1101<\/p>\n<p>Wy\u0142\u0105czenie bitu dla <em>rejestr = 1101<\/em>: 1101 and not(0100) = 1101 and 1011 = 1001<\/p>\n<p>Prze\u0142\u0105czenie bitu dla <em>rejestr = 1001<\/em>: 1001 xor 0100 = 1101<\/p>\n<p>Prze\u0142\u0105czenie bitu dla <em>rejestr = 1101<\/em>: 1101 xor 0100 = 1001<\/li>\n<li><strong>Maskowanie<\/strong>Jest to operacja wybierania z wi\u0119kszej liczby bit\u00f3w tylko, tych, kt\u00f3re faktycznie nas interesuj\u0105. W tym przypadku pos\u0142u\u017cymy si\u0119 operacj\u0105 <strong>i<\/strong>. <em>Maska<\/em> b\u0119dzie wybiera\u0107 nam, kt\u00f3re bity przy por\u00f3wnaniu s\u0105 dla nas wa\u017cne (ustawione w masce na 1). W\u00f3wczas je\u017celi chcemy por\u00f3wna\u0107 dwie dane: <em>dane_1<\/em> oraz <em>dane_2<\/em> u\u017cyjemy nast\u0119puj\u0105cej konstrukcji:<em><strong>if<\/strong> dane_1 and maska = dane_2 and maska <strong>then<\/strong>&#8230;<\/em>Doskona\u0142ym przyk\u0142adem s\u0105 tutaj sieci komputerowe i spos\u00f3b ich adresacji. W protokole IP wyr\u00f3\u017cniamy cz\u0119\u015b\u0107 adresu m\u00f3wi\u0105c\u0105 o sieci, w kt\u00f3rej znajduje si\u0119 dany komputer, oraz cz\u0119\u015b\u0107 adresu m\u00f3wi\u0105c\u0105 o numerze komputera w danej sieci. By zdecydowa\u0107 czy dany pakiet przes\u0142a\u0107 dalej czy znajduje si\u0119 on w naszej sieci musimy sprawdzi\u0107 czy cze\u015b\u0107 adresu, w kt\u00f3rej zawarty jest adres sieci jest zgodny z nasz\u0105 sieci\u0105. Wykonuje si\u0119 to za pomoc\u0105 operacji and na adresie sieci oraz masce sieci. Zatem taka decyzja wygl\u0105da w\u00f3wczas nast\u0119puj\u0105co:\n<p><em><strong>if<\/strong> adres_pakietu and maska_sieci = adres_moj and maska_sieci <strong>then<\/strong>&#8230;<\/em><\/p>\n<p><em>Przyk\u0142ad<\/em><\/p>\n<p>Za\u0142\u00f3\u017cmy, \u017ce:<\/p>\n<p><em>adres_pakietu=11000000101010110000000100100101<\/em><\/p>\n<p><em>adres_moj=11000000101010110001000000010111<\/em><\/p>\n<p><em>maska_sieci=11111111111111110000000000000000<\/em><\/p>\n<p>Sprawd\u017amy czy dany pakiet adresowany jest do naszej sieci:<\/p>\n<p><em>adres_pakietu and maska_sieci = adres_moj and maska_sieci<\/em><\/p>\n<p>11000000101010110000000100100101 and 11111111111111110000000000000000 = 11000000101010110001000000010111 and 11111111111111110000000000000000<\/p>\n<p>11000000101010110000000000000000 = 11000000101010110000000000000000<\/p>\n<p>R\u00f3wno\u015b\u0107 jest spe\u0142niona zatem ten pakiet adresowany jest do naszej sieci.<\/li>\n<li><strong>Upakowywanie danych<\/strong>Czasem zachodzi potrzeba u\u017cycia danych o niestandardowym rozmiarze. Na przyk\u0142ad chcemy zapisywa\u0107 bardzo wiele razy liczb\u0119, kt\u00f3rej warto\u015b\u0107 mie\u015bci si\u0119 w zakresie 0-3. Do zapisania takiego zakresu wystarcz\u0105 nam dwa bity. Najmniejsza jednostka jak\u0105 mo\u017cemy zapisa\u0107 na dyku to bajt, kt\u00f3ry ma 8 bit\u00f3w. Dlatego te\u017c, 4 takie dwubitowe warto\u015bci mo\u017cemy upakowa\u0107 jednym bajcie. Zapis takich upakowanych warto\u015bci mo\u017cemy zapisa\u0107 nast\u0119puj\u0105co:\n<ul>\n<li>odczyt upakowanej danej:<em>odpakowana = (upakowana and maska) shr start_bit<\/em><\/li>\n<li>zapis upakowanej danej b\u0119dzie przebiega\u0142 dwuetapowo, najpierw wyczyszczenie miejsca na dan\u0105, a nast\u0119pnie jej zapis:<em>upakowana = upakowana and not(maska)<\/em><em>upakowana = upakowana or (odpakowana shl start_bit)<\/em><\/li>\n<\/ul>\n<p><em>Maska<\/em> wskazuje nam miejsce gdzie nale\u017cy upakowa\u0107 dane, natomiast <em>start_bit<\/em> jest numerem bitu (licz\u0105c od 0 od prawej), pod kt\u00f3rym zaczyna si\u0119 dana.<\/p>\n<p><em>Przyk\u0142ad<\/em><\/p>\n<p>Za\u0142\u00f3\u017cmy, \u017ce mam 4 warto\u015bci: 01 11 10 01 wpisa\u0107 do jednego bajta.<\/p>\n<p>Kolejne maski dla tych danych zdefiniujemy nast\u0119puj\u0105co: 00000011, 00001100, 00110000, 11000000.<\/p>\n<p>Kolejne bity startowe dla tych danych zdefiniujemy nast\u0119puj\u0105co: 0, 2, 4, 6.<\/p>\n<p>Zapiszmy zatem drug\u0105 warto\u015b\u0107 do zmiennej <em>bajt = 0110<strong>10<\/strong>10<\/em>, miejsce, gdzie zostanie zapisana dana pogrubiono. A wi\u0119c najpierw czyszczenie miejsca pod nasze dane:<\/p>\n<p><em>bajt = bajt and not(maska)<\/em> = 01101010 and not(00001100) = 01101010 and 11110011 = 01100010.<\/p>\n<p>Teraz zapiszemy dane:<\/p>\n<p><em>bajt = bajt or (dane shl start_bit)<\/em> = 01100010 or (11 shl 2) = 01100010 or 1100 = 01101110.<\/p>\n<p>Spr\u00f3bujmy teraz odczyta\u0107 te dane:<br \/>\n<em>dane = (bajt and maska) shr start_bit)<\/em> = (01101110 and 00001100) shr 2 = 00001100 shr 2 = 11.<\/li>\n<\/ul>\n<p>\u0179r\u00f3d\u0142o: http:\/\/www.algorytm.org\/kurs-algorytmiki\/operacje-bitowe.html<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"<p class=\"excerpt\">Poni\u017cej zdefiniujemy operacje bitowe oraz przyk\u0142ady ich zastosowania podczas programowania. Operacja bitowa &#8222;i&#8221; (ang. bitwise and)Jest to operacja dwuargumentowa. W j\u0119zykach programowania b\u0105d\u017a w pseudokodzie zapisywana jest z regu\u0142y jako:a and b a &amp; b<\/p>\n<p class=\"more-link-p\"><a class=\"more-link\" href=\"http:\/\/u239160.webh.me\/jakisproblem.pl\/index.php\/2012\/04\/05\/operacje-bitowe\/\">Read more &rarr;<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[9],"class_list":["post-819","post","type-post","status-publish","format-standard","hentry","category-bez-kategorii","tag-rozne"],"_links":{"self":[{"href":"http:\/\/u239160.webh.me\/jakisproblem.pl\/index.php\/wp-json\/wp\/v2\/posts\/819","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/u239160.webh.me\/jakisproblem.pl\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/u239160.webh.me\/jakisproblem.pl\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/u239160.webh.me\/jakisproblem.pl\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/u239160.webh.me\/jakisproblem.pl\/index.php\/wp-json\/wp\/v2\/comments?post=819"}],"version-history":[{"count":0,"href":"http:\/\/u239160.webh.me\/jakisproblem.pl\/index.php\/wp-json\/wp\/v2\/posts\/819\/revisions"}],"wp:attachment":[{"href":"http:\/\/u239160.webh.me\/jakisproblem.pl\/index.php\/wp-json\/wp\/v2\/media?parent=819"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/u239160.webh.me\/jakisproblem.pl\/index.php\/wp-json\/wp\/v2\/categories?post=819"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/u239160.webh.me\/jakisproblem.pl\/index.php\/wp-json\/wp\/v2\/tags?post=819"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}