Operatory bitowe

Niedziela, 14 Lutego 2010, 16:36
Czas czytania 5 minut, 19 sekund
Zgodne z GM: gm5 gm6 gm7 gm8 gms1 gms2
Poza zwykłymi operatorami arytmetycznymi takimi jak + i -, GM oferuje nam również operatory operujące na zapisach binarnych liczb. Ten artykuł przybliży wam ich działanie.
W komputerze każda informacja zapisywana jest przy pomocy kodu binarnego (dwójkowego) składającego się jedynie z zer i jedynek. Przykładowo liczba 2 reprezentowana jest przez następujący ciąg: 10, a liczba 5 przez: 101. Jest to dość intuicyjne, po prostu wyobraźmy sobie, że istnieją jedynie te dwie cyfry. Wtedy bo 1 następuje 10. Kolejne pierwsze liczby w zapisie binarnym wyglądają więc tak:
1: 1
2: 10
3: 11
4: 100
5: 101
6: 110
7: 111
8: 1000
itd.
Mam nadzieję, że jest to zrozumiałe. Nie będę się zagłębiał w temat zapisu binarnego, bo nie o tym ma być ten artykuł.

GameMaker poza zwykłymi operatorami arytmetycznymi takimi jak +, -, * lub / oferuje nam również operatory działające na zapisie binarnym liczb. Należą do nich:
kod
| - OR bitowa suma logiczna (alternatywa)
& - AND bitowy iloczyn logiczny (koniunkcja)
^ - XOR bitowa różnica symetryczna
<< - przesunięcie w lewo
>> - przesunięcie w prawo
~ - negacja bitowa

Poniższe tabelki przedstawiają jakie wyniki zwracają poszczególne operatory dla danych argumentów. Za moment każdy z nich zostanie dokładniej omówiony.
Grafika: upload/screens/articles/tabele_bool.PNG

| - bitowa suma logiczna (alternatywa)
Działa analogicznie do operatora logicznego ||. Operator ten przyjmuje jako argumenty 2 liczby. Następnie sprawdza wartości ich kolejnych bitów. Jeśli chociaż jeden z nich jest równy 1 to odpowiedni bit liczby wynikowej będzie miał wartość 1.
kod
Przykład:
105 1101001
45 0101101
105 | 45 1101101


Jak widzimy jedynie 2 bity pozostały zerowe ponieważ tylko na 2 pozycjach obie liczby miały zerowy bit. Powstała w wyniku tej operacji liczba to 109.

& - bitowy iloczyn logiczny (koniunkcja)
Ten operator jest bitowym odpowiednikiem operatora logicznego &&. Działa bardzo podobnie jak omówiony przed chwilą operator |. Różnicą jest to, że wynikowy bit ma wartość 1 jedynie wtedy gdy odpowiednie bity obydwu liczb podanych jako argument są równe 1.
kod
Przykład:
105 1101001
45 0101101
105 & 45 0101001


Powstała liczba to 41. Operator ten, może posłużyć nam do obliczenia reszty z dzielenia przez 2. Jeśli dowolną liczbę potraktujemy tym operatorem jako drugi argument podając liczbę 1 to uzyskamy właśnie resztę z dzielenia przez 2.
kod
Przykład:
105 1101001
1 0000001
105 & 1 0000001

Na pierwszy rzut oka widać, że wszystkie bity poza ostatnim muszą zostać wyzerowane. Dzieje się tak dlatego, że liczba 1 ma tylko jeden bit równy 1. Wiadomo, że liczba jest podzielna przez 2 jeśli jej ostatni bit jest równy zero. Trudno się z tym nie zgodzić. Jeśli więc będzie podzielna przez 2 ostatni bit wynikowej liczby będzie równy 0, a więc cała liczba również będzie równa 0. W przeciwnym wypadku wynikiem będzie 1. Taka operacja jest znacznie szybsza od zwykłego dzielenia modulo.

^ - bitowa różnica symetryczna
Ten operator działa podobnie do dwóch poprzednich. Tutaj jednak wynikiem jest 1 gdy dokładnie jeden z argumentów ma wartość 1. Jest to równoważne temu, że odpowiednie bity się od siebie różnią.
kod
Przykład:
105 1101001
45 0101101
105 ^ 45 1000100

Powstała liczba to 68. Operator ten ma ciekawą własność. Mianowicie operacja ta jest odwracalna. Gdybyśmy teraz liczbę 68 potraktowali operatorem ^ i jako drugi argument podali 45 to otrzymali byśmy z powrotem 105. Można wykorzystać tę własność do prostego szyfrowania danych. Wystarczy każdy bajt XORować z jakimś kluczem. By odszyfrować dane wystarczy je przeXORować z tym samym kluczem.

<< - przesunięcie w lewo
Operator ten również przyjmuje 2 argumenty. Jego działanie jednak znacząco różni się od przedstawionych przed chwilą trzech operatorów bitowych. Pierwszy argument to liczba poddawana operacji, drugi to wartość przesunięcia. Operator ten przesuwa wszystkie bity danej liczby o daną wartość w lewo, a w powstałych miejscach po prawej wstawia 0.
kod
Przykład:
5 0000101
5 << 3 0101000
W wyniku tej operacji powstała liczba 40. Nie trudno zauważyć, że jest to nic innego jak mnożenie przez kolejne potęgi dwójki. Oczywiście przesunięcie o 30 bitów w lewo jest znacznie szybsze niż 30-krotne wymnożenie liczby przez 2.

>> - przesunięcie w prawo
Działanie niemal identyczne jak w przypadku poprzedniego operatora. Tutaj jednak wszystkie bity przesuwane są w prawo, a z lewej strony pozostają nam zera.
kod
Przykład:
45 0101101
45 >> 3 0000101
W wyniku powstała liczba 5. Można zauważyć, że w przypadku tego operatora kilka skrajnych bitów po prawej stronie zostaje utraconych. Dzięki temu zjawisku przesunięcie w prawo okazuje się równoważne całkowitoliczbowemu dzieleniu przez potęgi 2! Sprawdźmy to.
kod
45 / 2 = 22.5
22 / 2 = 11
11 / 2 = 5.5

45 / 2^3 = 45 / 8 = 5.625
Zgadza się! Każda utracona w zapisie binarnym jedynka jest to zgubiona część po przecinku.
Dodatkowo teraz wyciągając resztę z dzielenia przez 2 możemy uzyskać wartość konkretnego bitu początkowej liczby.

~ - negacja bitowa
Pozostała nam do omówienia jedynie negacja bitowa. Ten operator jest wyjątkowy ponieważ jest jednoargumentowy. Liczba będąca wynikiem tej operacji jest utworzona przez zamianę wszystkich 1 w zapisie binarnym na 0, a wszystkich 0 na 1.
kod
Przykład:
45 0101101
~45 1010010
Powstała nam liczba -46. Może wam się to wydać nieco dziwne. Jest to spowodowane tym, że aktualnie większość komputerów korzysta z systemu reprezentacji liczb całkowitych U2. Nie będę dokładnie wyjaśniał na czym on polega, bo jest to materiał na nowy artykuł, ale powiem w skrócie. Każda liczba posiada jeden dodatkowy bit znajdujący się na początku i określający czy liczba jest dodatnia (0) czy ujemna (1). Tak więc w rzeczywistości dla komputera 1001 to nie jest 9, a -7. 9 natomiast wyglądałoby tak: 01001. Dzięki takiemu sposobowi zapisu negacja zyskuje pewną ciekawą właściwość. Mianowicie: ~X == (-X-1).
Nietrudno zauważyć, że negacja jest operacją odwracalną, czyli: X == ~(~X).


I to by było na tyle. Możliwe, że wielu uzna operatory bitowe za zbędne, ale w niektórych przypadkach naprawdę się przydają. Przykładowo przy implementowaniu Drzew Potęgowych przy pomocy prostej linijki x-(x&(x-1)) cała skomplikowana struktura sprowadza się do 5 linijek kodu. A nieprawdopodobne jest w jaki sposób to działa :D

Dziękuję za uwagę : )
Komentarze (łącznie 15):
gnysek (Nie., 14 Lut. 10, 19:38)
#1

Warto zauważyć, że np. mnożenie razy 10 to np. (a<<3)+(a<<1). Taka ciekawostka.
Zabrakło tabelki dla AND, OR, XOR, NOT z algebry boola :)

Platyna (Nie., 14 Lut. 10, 19:55)
#2

Słuszna uwaga! Tabelki dodane :)

gnysek (Nie., 14 Lut. 10, 19:56)
#3

Daj je na początku, przed or :)

S
Snake (Wto., 16 Lut. 10, 22:44)
#4

Dobry artykuł. Można by jeszcze wspomnieć o operatorach |=, &=, ^=, braku >>=, <<= i o tym, że GM-owy real ma 64 bity a poprawnie operować można jedynie na tych 32 mniej znaczących :P

Platyna (Wto., 16 Lut. 10, 23:22)
#5

No niestety to jest problematyczne. Mógłbym mój przykład licznika przerobić by używał własnej arytmetyki, bo się wykrzaczał na dużych liczbach, ale to by znowu początkujący nie zrozumieli i by się z celem mijało :P

Co do operatorów to jakoś mi umknęły z pamięci, bo z helpem sprawdzałem czy o niczym nie zapomniałem, a tam ich nie było.

Robert Prus (śro., 17 Lut. 10, 15:33)
#6

A w czym nam może pomóc, zwykłym śmiertelnikom ten art?

S
slash (śro., 17 Lut. 10, 15:35)
#7

W operacji na bitach? Nie jestem pewien, strzelałem..

Easeful (śro., 17 Lut. 10, 17:29)
#8

praktycznie nie jest to potrzebne, ale art jest bardzo dobry i przybliżył mi działanie tych bitów :P 10/10

Platyna (śro., 17 Lut. 10, 17:40)
#9

Może w GMie faktycznie nie są zbyt potrzebne, ale w chociażby w C++ się przydają.

Może jeszcze jakiś przykład zastosowania... O wiem. Możemy w bardzo prosty sposób wygenerować wszystkie podzbiory jakiegoś zbioru. Tworzymy sobie inta w którym kolejne bity odpowiadają kolejnym elementom zbioru. Jeśli dany bit ma wartość 1 to element bierzemy, a jeśli 0 to nie. Zwiększając te liczbę o 1 generujemy kolejne podzbiory od pustego po wykorzystujący wszystkie elementy. To może być przydatne gdy każdemu możliwemu podzbiorowi chcemy przyporządkować jakąś komórkę tablicy na przykład. :)

S
slash (śro., 17 Lut. 10, 17:41)
#10

Każdy zrozumiał, o co chodzi :P ..

gnysek (śro., 17 Lut. 10, 18:22)
#11

No ale jak używasz np. 39dll, to art się bardzo przyda :) tak samo jak operujesz na plikach

p
pablo1517 (Wto., 23 Lut. 10, 06:48)
#12

Ja szczerze mówiąc dalej nie rozumiem jak można by to zastosować w 39dll xD

Dawidds (Wto., 23 Lut. 10, 07:39)
#13

pablo, jak masz do wysłania np. 2 zmienne 0-15 to zamiast je wysyłać osobno możesz je spokojnie upchnąć w jeden bat :)

gnysek (Wto., 23 Lut. 10, 16:26)
#14

Albo jak mam 8 zmiennych true/false :) Nawet jest taka funkcja buildbyte w 39dll :)

p
pablo1517 (Sob., 26 Mar. 11, 12:24)
#15

Ciekawostka, XOR pozwala na zamienienie zmiennych miejscami, tzn. Jeśli mamy a i b, i chcemy by a przybrała wartość b, i b przybrała wartość a, to z reguły ludzie tworzą sobie 3 dodatkową zmienną pomocniczą. XOR pozwala się bez niej obyć.
a=a^b;
b=a^b;
a=a^b;
I już zamienione :D

Najnowsze wersje GameMakera:

Stabilna
2024.2.0.132 • 2024.2.0.163
wydana 15 dni temu
LTS
2022.0.2.51 • 2022.0.2.49
wydana 154 dni temu
Beta
2024.400.0.516 • 2024.400.0.537
wydana  5 dni temu
= IDE, = Runtime
Użytkownicy online
1 użytkownik aktywny:
gości: 1,
(~ostatnie 15 minut)
Discord
Shoutbox
I am Lord (19:15, 17.03.24)
6h mam na to hmmm
I am Lord (19:06, 17.03.24)
Ale temat fajny
gnysek (01:33, 13.03.24)
Powinno działać, jest w kodzie sortowanie wg. najbliższego startu :)
Uzjel (21:59, 11.03.24)
Nie, ale za pierwszym razem zrobiłem fuckup, że było "Tura testowa" X_X
I am Lord (16:58, 11.03.24)
A co Uzjel już masz nawymyślane 100 tematów? 😅
Uzjel (20:08, 10.03.24)
@gnysek a jak bym dodał kilka lig na raz to walnie?
Uzjel (20:08, 10.03.24)
Liga będzie zawsze od piątku 16:00 do poniedziałku 23:59, zawsze w środku miesiąca.
gnysek (08:48, 10.03.24)
Tak, to też jest do poprawy X_X
Adriann (18:22, 09.03.24)
Tylko myślę czy nie leiej gdyby mówiło że zostało tyle i tyle dni i ileś godzin a nie tylko w godzinach ;d Albo konkretna data obok, byłoby czytelniej
I am Lord (15:08, 08.03.24)
o super z tą ligą :)
Starsze wpisy znajdziesz w Archiwum.
Ankieta
Ile zarobiłeś do tej pory na grach stworzonych w GM?