17 odpowiedzi w tym temacie

[R3X]

Operacje bitowe

Co to jest?
Działania na grupach bitów. Z powodu sposobu przedstawienia w pamięci sens ma dla liczb całkowitych (w tym znaków).
Dane są przechowywane w pamięci w systemie dwójkowym. Przykłady wprowadzające:

0010
1001
0110

Dalej będę się opierał tylko na 4 bitach. W pamięci komputera bajty składają się z 8. W pawnie wszystkie zmienne są 4 lub 8 bajtowe (32 lub 64 bity), zależnie od serwera.
Ilość dostępnych bitów określa definicja cellbits

1. Przesunięcia
Zmienia kolejność bitów przenosząc na miejsce sąsiednie.
a) w lewo
Operator: <<

1<<3

Bity liczby jeden (0001) przesuwa w lewo o trzy pozycje. W brakujące miejsca dopisywane są zera, bity wykraczające poza zakres są tracone.

0001 - początkowo
0010 - po przesunięciu o 1
0100 - po przesunięciu o 2
1000 - po przesunięciu o 3

Zatem 1<<3 = '1000' co po przeliczeniu na system dziesiętny daje liczbę 8.

Efekt: przesunięcie w lewo o n pozycji równoznaczne jest z mnożeniem przez (2 do potęgi n).

b)w prawo arytmetycznie
Operator: >>

7>>1

Bity liczby siedem (0111) przesuwa w prawo o jedną pozycje. W brakujące miejsca dopisywane bity o wartości najstarszego bitu pierwotnej liczby, bity wykraczające poza zakres są tracone.

0111 - początkowo
0011 - po przesunięciu o 1

Zatem 7>>1 = '0011' co po przeliczeniu na system dziesiętny daje liczbę 3.

Braki są uzupełniane bitem znaku.

15>>1

1111 - początkowo
1111 - po przesunięciu o 1

Efekt: przesunięcie w prawo o n pozycji równoznaczne jest z dzieleniem całkowitym przez (2 do potęgi n).

b)w prawo logicznie
Operator: >>>

15>>>1

Bity liczby piętnaście(1111) przesuwa w prawo o jedną pozycje. W brakujące miejsca dopisywane są zera, bity wykraczające poza zakres są tracone.

1111 - początkowo
0111 - po przesunięciu o 1

Zatem 15>>>1 = '0111' co po przeliczeniu na system dziesiętny daje liczbę 7.

Braki są uzupełniane zerami.


2. Operacje logiczne
Działania logiczne wykonywane między odpowiednimi bitami obu liczb.
a) koniunkcja inaczej iloczyn
Operator: &

8&2

Zapis dziesiętny na binarny:

1000 //8
0010 //2

Teraz bierzemy kolejne bity, wyznaczając ich iloczyn. Rozpiska:

1&1=1
1&0=0
0&1=0
0&0=0

1000
0010
Wykonujemy działanie 1&0 =0 zatem od lewej strony pierwszy bit wyniku=0
1000
0010
Wykonujemy działanie 0&0 = 0 zatem od lewej strony drugi bit wyniku=0
1000
0010
Wykonujemy działanie 0&1 = 0 zatem od lewej strony trzeci bit wyniku=0
1000
0010
I wykonujemy działanie 0&0 = 0 zatem od lewej strony czwarty bit wyniku=0

Zatem 8&2= '0000' co po przeliczeniu na system dziesiętny daje liczbę 0.

alternatywa inaczej suma
Operator: |

5|3

Zapis dziesiętny na binarny:

0101 //5
0011 //3

Teraz bierzemy kolejne bity, wyznaczając ich sumę. Rozpiska:

1|1=1
1|0=1
0|1=1
0|0=0

0101
0011
Wykonujemy działanie 0|0 = 0 zatem od lewej strony pierwszy bit wyniku=0
0101
0011
Wykonujemy działanie 1|0 = 1 zatem od lewej strony drugi bit wyniku=1
0101
0011
Wykonujemy działanie 0|1 = 1 zatem od lewej strony trzeci bit wyniku=1
0101
0011
I wykonujemy działanie 1&1 = 1 zatem od lewej strony czwarty bit wyniku=1

Zatem 5|3 = '0111' co po przeliczeniu na system dziesiętny daje liczbę 7.

c) różnica symetryczna inaczej XOR
Operator: ^

3^1

Zapis dziesiętny na binarny:

0011 //3
0001 //1

Teraz bierzemy kolejne bity, wyznaczając ich różnicę symetryczną. Rozpiska:

1^1=0
1^0=1
0^1=1
0^0=0

0011
0001
Wykonujemy działanie 0^0 = 0 zatem od lewej strony pierwszy bit wyniku=0
0011
0001
Wykonujemy działanie 0^0 = 0 zatem od lewej strony drugi bit wyniku=1
0011
0001
Wykonujemy działanie 1^0 = 1 zatem od lewej strony trzeci bit wyniku=1
0011
0001
I wykonujemy działanie 1^1 = 0 zatem od lewej strony czwarty bit wyniku=1

Zatem 3^1 = '0010' co po przeliczeniu na system dziesiętny daje liczbę 2.

d) negacja
Operator: ~

~1

Zapis dziesiętny na binarny:

0001 //1

Operacja jednoargumentowa - nie porównujemy bitów ze wzorcem, a jedynie zamieniamy każde 0 na 1 i odwrotnie. Stąd:

~0001
1110

Przykład ukazuję ideę - nie ma sensu przeliczać na system dziesiętny, bo w Pawnie nie spotkamy 4bitowego typu int.

3. Używanie:
Gdy na liczbę w pamięci komputera spojrzymy jak na zbiór wartości logicznych (1 lub 0) to w prosty sposób wykorzystać możemy operacje bitowe do przechowywania i sprawdzania zawartości składowej w całości.
Dokładniej chodzi o to, że każdej wartości 0 lub 1 przypisana jest jakaś funkcja (znaczenie). Mamy ciąg

0101

Możemy przeliczyć to na system dziesiętny, ale łatwiej pracować w takiej postaci. Każda liczba to informacja czy dana funkcja składowa jest aktywna (1) lub nie (0).

Przykład:

Do zaprezentowania możliwego użycia wybrałem prawa dostępu - chmod.
Określa jakie operacje wykonać można na danych pliku/katalogu. Składa się z 3 wartości. Każda z operacja ma swój odpowiednik literowy i liczbowy.

"wykonywanie" "x" 1
"zapis" "w" 2
"odczyt" "r" 4

Ograniczam zagadnienie do 1 grupy (zwykle określa się chmod dla 3 grup) pokażę jak zamienić zapis literowy na liczbowy i odwrotnie.

Pierwsze co musimy zrobić to zdecydować, które bity za co odpowiadają:

#define CHNONE 	001>>1	//000=0
#define CHEXEC 	001	//001=1
#define CHWRITE 001<<1	//010=2
#define CHREAD 	001<<2	//100=4

W tym wypadku kolejność ma znaczenie. Gdy będziemy tworzyć własne zestawy już nie będzie to takie ważne.

Napiszmy teraz funkcję, która przeliczy liczbę na skrót literowy. Pomijam sprawdzanie poprawności danych wejściowych, bo nie to jest tutaj istotne.
Funkcja strcat() dodaję podany ciąg na koniec wskazanego tekstu.

#include <amxmodx>
#include <amxmisc>

#define PLUGIN "Chmod"
#define VERSION "1.0"
#define AUTHOR "R3X"

#define CHNONE 	001>>1	//000=0
#define CHEXEC 	001	//001=1
#define CHWRITE 001<<1	//010=2
#define CHREAD 	001<<2	//100=4

public plugin_init()
{
register_plugin(PLUGIN, VERSION, AUTHOR)
register_concmd("chmod_num2str","chmod_num2str",-1,"<chmod num>");
}
public chmod_num2str(id,level,cid)
{
	//sprawdzenie prawa dostępu komendy i liczby argumentów
	if (!cmd_access(id,level,cid,2))
		return PLUGIN_HANDLED; 
	//deklaracja zmiennych
	new chmod_num,tekst[2],chmod_str[4]="";
	//pobranie argumentu
	read_argv(1, tekst, 1); 
	//konwersja na liczbę
	chmod_num=str_to_num(tekst); 
	//sprawdzenie bitu odpowiadającego za odczyt
	if(chmod_num & CHREAD)
	{
		//dodaje 'r'
		strcat(chmod_str,"r",3);
	}
	//sprawdzenie bitu odpowiadającego za zapis
	if(chmod_num & CHWRITE)
	{
		//dodaje 'w'
		strcat(chmod_str,"w",3);
	}
	//sprawdzenie bitu odpowiadającego za wykonywanie
	if(chmod_num & CHEXEC)
	{
		//dodaje 'x'
		strcat(chmod_str,"x",3);
	}	
	console_print(id,"chmod[%d] -> ^"%s^"",chmod_num,chmod_str);
	return PLUGIN_HANDLED;
}

Dlaczego używamy tutaj iloczynu?
Wyzerują się wszystkie nieistotne w danym przypadku bity i zostanie do porównania ten, o który nam chodzi.

chmod_num2str 6

Przejdźmy fragment drogi chmod_num.

Przypisanie wartości z argumentu. Przyjmijmy, że będzie to 6 (110).
Pierwsze sprawdzenie:

chmod_num & CHREAD

(szukamy więc iloczynu takich liczb:)

110
100

Kolejno od lewej:

1&1=1

1&0=0

0&0=0

Ostatecznie wynik = 100 - nie jest równy 0 i przejdzie pozytywnie test logiczny if().

Spróbuj samodzielnie wykonać test logiczny nr 2 i 3.

[mgr inż. Pavulon]

Standardowa informatyka ale niektórym może się przyda (część i tak nie zrozumie ). GJ

[Miczu]

Ja bym dodal, ze:
1< pracuje jako 2 do potegi x

x>>1
pracuje jako dzielenie liczby x przez 2 z zaokragleniem w dol.


Ciekawe czy mam gdzies zapisane moje prace z operacjami bitowymi

[R3X]

Efekt: przesunięcie w lewo o n pozycji równoznaczne jest z mnożeniem przez (2 do potęgi n).

Efekt: przesunięcie w prawo o n pozycji równoznaczne jest z dzieleniem całkowitym przez (2 do potęgi n).

Przygotowuję przykład wyznaczania chmod - konwersja rwx -> 7 itd.

[Miczu]

Hmm nie widze bys edytowal wiec chyba to ja jestem slepy

[silversurfer]

Hm, a da się to wytłumaczyć na przykładzie, ponieważ chciałbym to w pełni zrozumieć.

[Miczu]

R3X, a nie powinna istniec jakas operacja bitowa pozwalajaca na odjecie/wyzerowanie konkretnego bita?

Jesli tak to mozna by dac przyklad na zapisywaniu w 1 zmiennej new (int) informacji o posiadaniu bonusu/umiejetnosci (true/false).

PS. Sa jeszcze 2 i jeden z powyzszych mozna uzyc tak jak napisalem

[R3X]

Miczu, racja uzupełnione. Nigdy w praktyce nie używałem tych, które pominąłem (nieopatrznie).

Wyzerowanie:

7&(~(1<<2))

koniunkcja
0111
~0100

koniunkcja
0111
1011

0011

[R3X]

Aktualizacja:
doprecyzowane przesunięcia w prawo

[mierzwi]

nie wiem czy dobrze zkumałem, ale to działa na zasadzie

1<<0 - to chyba 1 nie ? D:
1<<1 - 2 do potęgi 1 = 2
1<<2 - 2 do potęgi 2 = 4
1<<3 - 2 do potęgi 3 = 8
1<<4 - 2 do potęgi 4 = 16

i tak dalej ?

Użytkownik funfel edytował ten post 07.07.2011 16:21

[G[o]Q]

x<<y = x*2^y

warto dodac ze

1>>x = x/2

i sprawdzenie czy liczba jest parzysta zamiast % mozna wykonac tak

public czy_parzysta(liczba){
      if((liczba>>1)*2==liczba)
           return 1;
      return 0;
}

[R3X]

to wszystko jest zawarte w pierwszy poście

Efekt: przesunięcie w lewo o n pozycji równoznaczne jest z mnożeniem przez (2 do potęgi n).

czyli 1<<0 to jeden razy 2 do potegi 0 czyli 1*1 = 1
i podobny komentarz dla reszty przesunięć

a parzystość liczby można najszybciej sprawdza się najmłodszym bitem

bool:czy_parzysta(liczba){
	return !(liczba&1);
}

Edit.
GoQ chyba myślałeś o takim przesunięciu

public czy_parzysta(liczba){
      if((liczba>>1)*2==liczba)
           return 1;
      return 0;
}

[Fili:P]

niedługo będę o tym czytał w symfonii c++ ;d

[zryty]

Zawsze mam problem z tymi operacjami bitowymi, wielkie dzięki. Mam też bity stałych broni, może komuś się przydadzą:

CSW_P228			1   000001

CSW_SCOUT			3   000011

CSW_HEGRENADE			4   000100

CSW_XM1014			5   000101

CSW_C4				6   000110

CSW_MAC10			7   000111

CSW_AUG				8   001000

CSW_SMOKEGRENADE		9   001001

CSW_ELITE			10  001010

CSW_FIVESEVEN			11  001011

CSW_UMP45			12  001100

CSW_SG550			13  001101

CSW_GALI			14  001110

CSW_FAMAS			15  001111

CSW_USP				16  010000

CSW_GLOCK18			17  010001

CSW_AWP				18  010010

CSW_MP5NAVY			19  010011

CSW_M249			20  010100

CSW_M3				21  010101

CSW_M4A1			22  010110

CSW_TMP				23  010111

CSW_G3SG1			24  011000

CSW_FLASHBANG			25  011001

CSW_DEAGLE			26  011010

CSW_SG552			27  011011

CSW_AK47			28  011100

CSW_KNIFE			29  011101

CSW_P90				30  011110

CSW_VEST			31  011111

CSW_VESTHELM			32  100000

[zryty]

Przykład z flagami specjalnymi:

if(get_user_flags(id) & (ADMIN_LEVEL_H|ADMIN_LEVEL_G|ADMIN_LEVEL_F))

 

{

    //VIP

} else {

    //zwykly zjadacz chleba

}

[grankee]

Dlaczego nie przełożyć tego na bardziej ludzki język? Nie każdy potrafi zrozumieć jak to działa "po komputerowemu"...

 

Postaram się sprostać. ZAZNACZAM, ŻE:

PRZEDSTAWIONE PONIŻEJ SPOSOBY ZROZUMIENIA MOGĄ MIJAĆ SIĘ Z PRAWDĄ POD WZGLĘDEM DZIAŁANIA OD STRONY TECHNICZNEJ.

NIE JEST TO ZOBRAZOWANIE DOKŁADNEGO DZIAŁANIA A JEDYNIE PRÓBA PRZEDSTAWIENIA SPRAWY "PO LUDZKU" W SPOSÓB DLA CZŁOWIEKA ZROZUMIAŁY

 

Tak więc operacji bitowych możemy użyć do przechowania jakby kilku wartości logicznych (tzn coś jest albo nie jest, prawda albo fałsz) w jednej zmiennej typu int.

 

Załóżmy, że mamy obiekt - jabłko.

Jabłko ma kilka właściwości:

może być słodkie albo kwaśne

może być twarde albo miękkie

może być duże albo małe

Jak widać jest albo - albo, więc zamiast sprawdzać oba sprawdźmy jedno, jak jest prawdą to wiadomo, że drugie nie jest, jak nie jest prawdą to uznajemy, że drugie jest.

 

Wystarczy określi czy jest słodkie, jak jest to nie jest kwaśne itd

 

 

Tworzymy więc listę właściwości:

#define JABLKO_SLODKIE (1<<0) //ma wartość 1 
#define JABLKO_TWARDE (1<<1) //ma wartość 2
#define JABLKO_DUZE (1<<2) // ma wartość 4
//kolejna miałaby 8, kolejna 16 itd

Każda taka kolejna właściwość ma wartość 2 razy większą od poprzedniej, po co? o tym za chwilę.

Teraz gdybyśmy chcieli przekazać informacje o tym jabłku do funkcji, bez użycia operacji bitowych, to musimy użyć co najmniej trzech zmiennych typu bool aby określić jego 3 właściwości. Dzięki operacjom bitowym możemy przekazać to w jednej zmiennej. Ta zmienna będzie miała w systemie dziesiętnym wartość równą sumie poszczególnych właściwości z listy.

 

Zakładamy, że jabłko jest słodkie,twarde i duze:

new jablko=(JABLKO_SLODKIE | JABLKO_TWARDE | JABLKO_DUZE)

operator | dodaje (suma)

tak więc teraz zmienna jablko ma wartość 7 (suma 1,2 oraz 4)

Minęło kilka dni, jabłko wyraźnie stało się miękkie, więc zabieramy mu właściwość TWARDE:

jablko ^= JABLKO_TWARDE //albo jablko = jablko^JABLKO_TWARDE 

zabraliśmy mu wartość 2 więc teraz będzie miało 5 (suma składowa licz 1 oraz 4 przypisanych odpowiednio to właściwości JABLKO_SLODKIE oraz JABLKO_DUZE)

Teraz aby sprawdzić czy dana wartość zawarta jest w naszym jabłku:

if(jablko & JABLKO_SLODKIE) //zwróci true
if(jablko & JABLKO_TWARDE) //zwróci false, bo zabralismy mu ta wlasciwosc
if(jablko & JABLKO_DUZE) //zwróci true

Operacje jakie można wykonać:

jablko ^= JABLKO_DUZE //zabieramy wlasciwosc DUZE
jablko |= JABLKO_DUZE //dodajemy wlasciwosc DUZE
if (jablko & JABLKO_DUZE)// zwroci true jesli jest ta wlasciwosc lub false jesli nie ma
//mozemy nadac kilka wlasciwosci na raz:
jablko |= (JABLKO_DUZE | JABLKO_TWARDE) //doda obie wlasciwosci
//analogicznie mozna usunac dowolna ilosc razem
jablko ^= (JABLKO_DUZE | JABLKO_TWARDE) //usunie obie wlasciwosci
// oraz sprawdzic czy kilka wlasciwosci jablko ma:
if (jablko & (JABLKO_DUZE | JABLKO_TWARDE))// zwroci true jesli jablko ma WSZYSTKIE wlasciwosci lub false jesli nie ma conajmniej jednej z nich
// albo czy ma chociaz jedną z podanych
if (jablko & (JABLKO_DUZE ^ JABLKO_TWARDE))// zwroci true jesli jablko ma jedną z podanych wlasciwosci lub false jesli nie ma zadnej z nich (nie jestem pewny, poprawcie jak sie myle) 

Dlaczego każda liczba jest dwa razy wieksza od poprzedniej? Jest tak z prostej przyczyny - nie da się uzyskać dowolnej z nich sumując którekolwiek z pozostałych.

Gdyby te wartości były kolejne tzn: 1, 2,3,4 to nadając właściwość 4 nie wiedzielibyśmy nadal co to jest, bo 4 moze oznaczac ze obiekt ma wlasciwosc 4, a moze wcale nie ma 4 tylko 1 oraz 3...a przy takie numeracji wszystko jest jasne:

ma wartosc 1 to znaczy, ze ma wlasciwosc pierwsza (1)=1

2 oznacza ze ma tylko wlasciwosc druga(2)=2

3 oznacza ze ma pierwsza i druga (1+2)=3

4 oznacza ze ma tylko wlasciwosc trzecia (4)=4

5 oznacza ze ma pierwsza i trzecia (1+4)=5

6 oznacza ze ma druga i trzecia (2+4)=6

7 oznacza ze ma pierwsza ddruga i trzecia (1+2+4)=7

 

W ten sposób każda kolejna liczba oznacza kombinację konkretnych właściwości, dlatego zawsze jesteśmy w stanie szybko sprawdzic ktore z nich sa a ktorych nie ma.

 

Dodaje nam to sporo mozliwosci, czasu i nie zmusza do tworzenia wielu zmiennych.

 

 

////////

Jaki maksymalny rozmiar to moze miec?

tzn jak duzy pakiet moze byc, wiadomo ze z kazda kolejna definicja (1<<0) (1<<1) itd rozmiar liczby rosnie o wartosci 1 wykladnika potegi...