Jakie są przykłady rzeczywistych zastosowań następujących operatorów bitowych?
- I
- XOR
- NIE
- LUB
- Przesunięcie w lewo / w prawo
Jakie są przykłady rzeczywistych zastosowań następujących operatorów bitowych?
Odpowiedzi:
Pola bitowe (flagi)
To najbardziej efektywny sposób reprezentowania czegoś, którego stan jest zdefiniowany przez kilka właściwości „tak lub nie”. Listy ACL są dobrym przykładem; jeśli powiedzmy 4 dyskretne uprawnienia (odczyt, zapis, wykonywanie, zmiana zasad), lepiej przechowywać to w 1 bajcie zamiast marnować 4. Można je zmapować na typy wyliczeń w wielu językach dla dodatkowej wygody.
Komunikacja przez porty / gniazda
Zawsze obejmuje sumy kontrolne, parzystość, bity stopu, algorytmy sterowania przepływem itp., Które zwykle zależą od wartości logicznych poszczególnych bajtów w przeciwieństwie do wartości liczbowych, ponieważ medium może być w stanie przesłać tylko jeden bit na czas.
Kompresja, szyfrowanie
Oba są silnie zależne od algorytmów bitowych. Spójrz na algorytm deflacji - wszystko jest w bitach, a nie w bajtach.
Maszyny o stanach skończonych
Mówię przede wszystkim o rodzaju wbudowanym w jakiś sprzęt, chociaż można je również znaleźć w oprogramowaniu. Są kombinatoryczne w przyrodzie - mogą one być coraz dosłownie „skompilowany” w dół do kilka bramek logicznych, więc muszą być wyrażone jako AND
, OR
, NOT
, itd.
Grafika
Nie ma tu wystarczająco dużo miejsca, aby dostać się do każdego obszaru, w którym operatorzy są wykorzystywani do programowania grafiki. XOR
(lub ^
) jest tutaj szczególnie interesujące, ponieważ zastosowanie tego samego wejścia po raz drugi spowoduje cofnięcie pierwszego. Starsze GUI polegały na tym przy podświetlaniu wyboru i innych nakładkach, aby wyeliminować potrzebę kosztownych przerysowań. Nadal są przydatne w powolnych protokołach graficznych (np. Zdalny pulpit).
To tylko kilka pierwszych przykładów, które wymyśliłem - nie jest to wyczerpująca lista.
Czy to dziwne?
(value & 0x1) > 0
Czy można go podzielić przez dwa (parzyste)?
(value & 0x1) == 0
Oto kilka typowych idiomów dotyczących flag przechowywanych jako pojedyncze bity.
enum CDRIndicators {
Local = 1 << 0,
External = 1 << 1,
CallerIDMissing = 1 << 2,
Chargeable = 1 << 3
};
unsigned int flags = 0;
Ustaw flagę podlegającą opłacie:
flags |= Chargeable;
Wyczyść flagę CallerIDMissing:
flags &= ~CallerIDMissing;
Sprawdź, czy ustawione są CallerIDMissing i Chargeable:
if((flags & (CallerIDMissing | Chargeable )) == (CallerIDMissing | Chargeable)) {
}
Użyłem operacji bitowych przy wdrażaniu modelu bezpieczeństwa dla CMS. Miał strony, do których użytkownicy mogliby uzyskać dostęp, gdyby byli w odpowiednich grupach. Użytkownik może być w wielu grupach, dlatego musieliśmy sprawdzić, czy istnieje skrzyżowanie między grupami użytkowników i grupami stron. Przypisaliśmy więc każdej grupie unikalny identyfikator potęgi-2, np .:
Group A = 1 --> 00000001
Group B = 2 --> 00000010
Group C = 3 --> 00000100
Mamy LUB te wartości razem i przechowujemy wartość (jako pojedynczy int) ze stroną. Np. Jeśli dostęp do strony mogą uzyskać grupy A i B, przechowujemy wartość 3 (która w postaci binarnej to 00000011) jako kontrolę dostępu do stron. W podobny sposób przechowujemy wartość identyfikatorów grup ORed z użytkownikiem, aby reprezentować, w których grupach się znajdują.
Aby więc sprawdzić, czy dany użytkownik może uzyskać dostęp do danej strony, wystarczy ORAZ wartości razem i sprawdzić, czy wartość nie jest zerem. Jest to bardzo szybkie, ponieważ ta kontrola jest realizowana w jednej instrukcji, bez zapętlania, bez rund bazy danych.
Dobrym przykładem jest programowanie na niskim poziomie. Może być na przykład konieczne zapisanie określonego bitu w rejestrze odwzorowanym w pamięci, aby jakiś sprzęt zrobił to, co chcesz:
volatile uint32_t *register = (volatile uint32_t *)0x87000000;
uint32_t value;
uint32_t set_bit = 0x00010000;
uint32_t clear_bit = 0x00001000;
value = *register; // get current value from the register
value = value & ~clear_bit; // clear a bit
value = value | set_bit; // set a bit
*register = value; // write it back to the register
Również htonl()
i htons()
są realizowane przy użyciu &
i |
operatorów (na maszynach, których kolejność bajtów (kolejność bajtów) nie zgadza się kolejność sieci):
#define htons(a) ((((a) & 0xff00) >> 8) | \
(((a) & 0x00ff) << 8))
#define htonl(a) ((((a) & 0xff000000) >> 24) | \
(((a) & 0x00ff0000) >> 8) | \
(((a) & 0x0000ff00) << 8) | \
(((a) & 0x000000ff) << 24))
htons()
i htonl()
są funkcjami POSIX do zamiany a short
lub a long
z h
endianness hosta ( ) na n
kolejność bajtów w sieci ( ).
htonl()
dotyczy wartości 32-bitowej int
? long
oznacza 64-bitowe w wielu językach.
Używam ich na przykład do uzyskiwania wartości RGB (A) z upakowanych wartości kolorów.
(a & b) >> c
jest ponad 5 razy szybszy niż a % d / e
(oba sposoby na wyodrębnienie jednej wartości koloru z int reprezentującej ARGB). Odpowiednio, 6,7s i 35,2s dla 1 miliarda iteracji.
%
nie jest operatorem Modulus, lecz operatorem Remainder. Są równoważne wartościom dodatnim, ale różnią się wartościami ujemnymi. Jeśli podasz odpowiednie ograniczenia (przekazując uint
zamiast zamiast int
na przykład), wówczas dwa przykłady powinny być tej samej prędkości.
Kiedy mam kilka flag boolowskich, lubię je przechowywać w int.
Wyciągam je za pomocą bitowego AND. Na przykład:
int flags;
if (flags & 0x10) {
// Turn this feature on.
}
if (flags & 0x08) {
// Turn a second feature on.
}
itp.
if (flags.feature_one_is_one) { // turn on feature }
. Jest w standardzie ANSI C, więc przenośność nie powinna stanowić problemu.
& = AND:
maskowanie określonych bitów.
Definiujesz określone bity, które powinny być wyświetlane lub nie. 0x0 i x kasują wszystkie bity w bajcie, a 0xFF nie zmienia x. 0x0F wyświetli bity w dolnej części.
Konwersja:
Aby rzutować krótsze zmienne na dłuższe o identyczności bitowej, konieczne jest dostosowanie bitów, ponieważ -1 w int to 0xFFFFFFFF, podczas gdy -1 w długim to 0xFFFFFFFFFFFFFFFF. Aby zachować tożsamość, po konwersji zastosujesz maskę.
| = LUB
Ustaw bity. Bity zostaną ustawione niezależnie, jeśli są już ustawione. Wiele struktur danych (pól bitowych) ma flagi takie jak IS_HSET = 0, IS_VSET = 1, które można ustawić niezależnie. Aby ustawić flagi, zastosuj IS_HSET | IS_VSET (W C i asemblerze bardzo wygodnie to czyta)
^ = XOR
Znajdź bity, które są takie same lub różne.
~ = NIE
Odwróć bity.
Można pokazać, że wszystkie możliwe lokalne operacje bitowe mogą być zaimplementowane przez te operacje. Jeśli chcesz, możesz zaimplementować instrukcję ADD wyłącznie za pomocą operacji bitowych.
Niektóre wspaniałe hacki:
http://www.ugcs.caltech.edu/~wnoise/base2.html
http://www.jjj.de/bitwizardry/bitwizardrypage.html
= ~
, a nie |=
, które jest OR.
& = AND
- Dlaczego miałbym chcieć wyczyścić wszystkie bity, dlaczego miałbym chcieć uzyskać niezmodyfikowaną wersję bajtu i co mam zrobić z dolnym skubaniem?
xor
sam w sobie. Mogę wymyślić kilka powodów, dla których możesz chcieć wyodrębnić niższy kęs. Zwłaszcza jeśli ten niższy skrawek jest częścią struktury danych i chcesz użyć go jako maski lub OR
innej struktury.
Szyfrowanie to wszystkie operacje bitowe.
Możesz użyć ich jako szybkiego i brudnego sposobu na haszowanie danych.
int a = 1230123;
int b = 1234555;
int c = 5865683;
int hash = a ^ b ^ c;
To jest przykład odczytu kolorów z mapy bitowej w formacie bajtowym
byte imagePixel = 0xCCDDEE; /* Image in RRGGBB format R=Red, G=Green, B=Blue */
//To only have red
byte redColour = imagePixel & 0xFF0000; /*Bitmasking with AND operator */
//Now, we only want red colour
redColour = (redColour >> 24) & 0xFF; /* This now returns a red colour between 0x00 and 0xFF.
Mam nadzieję, że te małe przykłady pomogą ...
W abstrakcyjnym świecie współczesnego języka nie ma ich zbyt wiele. File IO jest łatwym, który przychodzi na myśl, chociaż wykonuje on operacje bitowe na czymś już zaimplementowanym i nie implementuje czegoś, co wykorzystuje operacje bitowe. Mimo to, jako prosty przykład, ten kod pokazuje usunięcie atrybutu „tylko do odczytu” dla pliku (aby można go było używać z nowym FileStream określającym FileMode.Create) w c #:
//Hidden files posses some extra attibutes that make the FileStream throw an exception
//even with FileMode.Create (if exists -> overwrite) so delete it and don't worry about it!
if(File.Exists(targetName))
{
FileAttributes attributes = File.GetAttributes(targetName);
if ((attributes & FileAttributes.ReadOnly) == FileAttributes.ReadOnly)
File.SetAttributes(targetName, attributes & (~FileAttributes.ReadOnly));
File.Delete(targetName);
}
Jeśli chodzi o niestandardowe implementacje, oto ostatni przykład: Stworzyłem „centrum wiadomości” do wysyłania bezpiecznych wiadomości z jednej instalacji naszej aplikacji rozproszonej do drugiej. Zasadniczo jest analogiczny do wiadomości e-mail, w komplecie ze skrzynką odbiorczą, skrzynką nadawczą, wysłaną itp., Ale zapewnia także dostawę z potwierdzeniami odczytu, więc istnieją dodatkowe podfoldery poza „skrzynką odbiorczą” i „wysłane”. To, co to oznaczało, wymagało ode mnie ogólnego określenia, co jest „w skrzynce odbiorczej”, a co „w wysłanym folderze”. Z wysłanego folderu muszę wiedzieć, co jest przeczytane, a co nieprzeczytane. O tym, co jest nieprzeczytane, muszę wiedzieć, co otrzymano, a co nie. Używam tych informacji do zbudowania dynamicznej klauzuli where, która filtruje lokalne źródło danych i wyświetla odpowiednie informacje.
Oto jak zestawiony jest wyliczenie:
public enum MemoView :int
{
InboundMemos = 1, // 0000 0001
InboundMemosForMyOrders = 3, // 0000 0011
SentMemosAll = 16, // 0001 0000
SentMemosNotReceived = 48, // 0011
SentMemosReceivedNotRead = 80, // 0101
SentMemosRead = 144, // 1001
Outbox = 272, //0001 0001 0000
OutBoxErrors = 784 //0011 0001 0000
}
Czy widzisz co to robi? Poprzez anding (&) wartością wyliczenia „Skrzynka odbiorcza”, InboundMemos, wiem, że InboundMemosForMyOrders znajduje się w skrzynce odbiorczej.
Oto uproszczona wersja metody, która buduje i zwraca filtr definiujący widok dla aktualnie wybranego folderu:
private string GetFilterForView(MemoView view, DefaultableBoolean readOnly)
{
string filter = string.Empty;
if((view & MemoView.InboundMemos) == MemoView.InboundMemos)
{
filter = "<inbox filter conditions>";
if((view & MemoView.InboundMemosForMyOrders) == MemoView.InboundMemosForMyOrders)
{
filter += "<my memo filter conditions>";
}
}
else if((view & MemoView.SentMemosAll) == MemoView.SentMemosAll)
{
//all sent items have originating system = to local
filter = "<memos leaving current system>";
if((view & MemoView.Outbox) == MemoView.Outbox)
{
...
}
else
{
//sent sub folders
filter += "<all sent items>";
if((view & MemoView.SentMemosNotReceived) == MemoView.SentMemosNotReceived)
{
if((view & MemoView.SentMemosReceivedNotRead) == MemoView.SentMemosReceivedNotRead)
{
filter += "<not received and not read conditions>";
}
else
filter += "<received and not read conditions>";
}
}
}
return filter;
}
Niezwykle prosta, ale zgrabna implementacja na poziomie abstrakcji, która zwykle nie wymaga operacji bitowych.
Przykładem jest kodowanie Base64. Kodowanie Base64 służy do reprezentowania danych binarnych jako drukowalnych znaków do wysyłania przez systemy pocztowe (i inne cele). Kodowanie Base64 przekształca ciąg 8-bitowych bajtów w 6-bitowe indeksy wyszukiwania znaków. Operacje bitowe, przesuwanie i „dodawanie” lub „notowanie” są bardzo przydatne do implementacji operacji bitowych niezbędnych do kodowania i dekodowania Base64.
To oczywiście tylko 1 z niezliczonych przykładów.
Dziwi mnie, że nikt nie wybrał oczywistej odpowiedzi na epokę Internetu. Obliczanie prawidłowych adresów sieciowych dla podsieci.
Zwykle operacje bitowe są szybsze niż mnożenie / dzielenie. Więc jeśli musisz pomnożyć zmienną x przez powiedzmy 9, zrobisz tox<<3 + x
co byłoby kilka cykli szybciej niżx*9
. Jeśli ten kod znajduje się w ISR, zaoszczędzisz na czasie odpowiedzi.
Podobnie, jeśli chcesz użyć tablicy jako kolejki kołowej, szybsze (i bardziej eleganckie) byłoby obsługiwanie kontroli zawijania za pomocą nieco mądrzejszych operacji. (Twój rozmiar tablicy powinien wynosić 2). Np .: możesz użyćtail = ((tail & MASK) + 1)
zamiasttail = ((tail +1) < size) ? tail+1 : 0
, jeśli chcesz wstawić / usunąć.
Również jeśli chcesz, aby flaga błędu zawierała wiele kodów błędów, każdy bit może zawierać osobną wartość. Możesz ORAZ z każdym kodem błędu jako czekiem. Jest to używane w uniksowych kodach błędów.
Również n-bitowa mapa bitowa może być naprawdę fajną i zwartą strukturą danych. Jeśli chcesz przydzielić pulę zasobów o rozmiarze n, możemy użyć n-bitów do przedstawienia bieżącego stanu.
Wydaje się, że nikt nie wspomniał o matematyce stałoprzecinkowej.
(Tak, jestem stary, ok?)
Czy liczba x
jest potęgą 2? (Przydatne na przykład w algorytmach, w których licznik jest zwiększany, a działanie ma być podejmowane tylko logarytmicznie kilka razy)
(x & (x - 1)) == 0
Który z najwyższych bitów jest liczbą całkowitą x
? (To na przykład można wykorzystać do znalezienia minimalnej mocy 2, która jest większa niż x
)
x |= (x >> 1);
x |= (x >> 2);
x |= (x >> 4);
x |= (x >> 8);
x |= (x >> 16);
return x - (x >>> 1); // ">>>" is unsigned right shift
Który z najniższych 1
bitów jest liczbą całkowitą x
? (Pomaga znaleźć liczbę razy podzielną przez 2.)
x & -x
x & -x
.
Operatory bitowe są przydatne do zapętlania tablic o długości równej potędze 2. Jak wspomniano wiele osób, operatory bitowe są niezwykle przydatne i są używane w flagach , grafice , sieci i szyfrowaniu . Nie tylko to, ale są niezwykle szybkie. Moim ulubionym jest użycie pętli tablica bez warunkowych . Załóżmy, że masz tablicę opartą na indeksie zerowym (np. Indeks pierwszego elementu wynosi 0) i musisz zapętlać ją w nieskończoność. Przez nieokreślony mam na myśli przejście od pierwszego elementu do ostatniego i powrót do pierwszego. Jednym ze sposobów realizacji tego jest:
int[] arr = new int[8];
int i = 0;
while (true) {
print(arr[i]);
i = i + 1;
if (i >= arr.length)
i = 0;
}
Jest to najprostsze podejście, jeśli chcesz uniknąć jeśli oświadczenie, można użyć modułu zespolonego podejście tak:
int[] arr = new int[8];
int i = 0;
while (true) {
print(arr[i]);
i = i + 1;
i = i % arr.length;
}
Wadą tych dwóch metod jest to, że operator modułu jest drogi, ponieważ szuka pozostałej części po dzieleniu liczb całkowitych. I pierwsza metoda uruchamia instrukcję if na każdej iteracji. Jeśli operator bitowy ma długość 2, możesz łatwo wygenerować sekwencję 0 .. length - 1
, używając &
operatora (bitowego i) i & length
. Wiedząc o tym, kod z góry staje się
int[] arr = new int[8];
int i = 0;
while (true){
print(arr[i]);
i = i + 1;
i = i & (arr.length - 1);
}
Oto jak to działa. W formacie binarnym każda liczba, która jest potęgą 2 odejmowana przez 1, jest wyrażana tylko z jedynkami. Na przykład 3 w systemie binarnym to 11
7 111
, 15 to 1111
i tak dalej, masz pomysł. A co się stanie, jeśli &
dowolna liczba w stosunku do liczby składającej się tylko z liczb binarnych? Powiedzmy, że robimy to:
num & 7;
Jeśli num
jest mniejsze lub równe 7, wynik będzie taki, num
że każdy bit &
z 1 ma swoją wartość. Jeśli num
jest większy niż 7, podczas &
operacji komputer weźmie pod uwagę zera 7, które oczywiście pozostaną jako zera po &
operacji, pozostanie tylko część końcowa. Tak jak w przypadku 9 & 7
binarnego będzie to wyglądać
1001 & 0111
wynikiem będzie 0001, który ma wartość 1 w systemie dziesiętnym i adresuje drugi element w tablicy.
może być również przydatny w modelu relacyjnym sql, powiedzmy, że masz następujące tabele: BlogEntry, BlogCategory
tradycyjnie możesz utworzyć relację nn między nimi za pomocą tabeli BlogEntryCategory lub gdy nie ma zbyt wielu rekordów BlogCategory, możesz użyć jednej wartości w BlogEntry, aby połączyć się z wieloma rekordami BlogCategory, tak jak zrobiłbyś to z oznaczonymi wyliczeniami, w większości RDBMS są również bardzo szybcy operatorzy do wyboru w tej kolumnie „oflagowanej” ...
Jeśli chcesz zmienić tylko niektóre bity wyjść mikrokontrolera, ale rejestr, w którym chcesz zapisać, to bajt, robisz coś takiego (pseudokod):
char newOut = OutRegister & 0b00011111 //clear 3 msb's
newOut = newOut | 0b10100000 //write '101' to the 3 msb's
OutRegister = newOut //Update Outputs
Oczywiście wiele mikrokontrolerów pozwala zmieniać każdy bit indywidualnie ...
Jeśli kiedykolwiek chcesz obliczyć swój mod liczbowy (%) pewną potęgę 2, możesz użyć yourNumber & 2^N-1
, która w tym przypadku jest taka sama jak yourNumber % 2^N
.
number % 16 = number & 15;
number % 128 = number & 127;
Prawdopodobnie jest to przydatne tylko jako alternatywa dla operacji modułu z bardzo dużą dywidendą, która wynosi 2 ^ N ... Ale nawet wtedy jego wzrost prędkości w stosunku do operacji modułu jest pomijalny w moim teście na .NET 2.0. Podejrzewam, że nowoczesne kompilatory już wykonują takie optymalizacje. Czy ktoś wie o tym więcej?
%
operacja Remainder, traktuje negatywnie inaczej. Jednak jeśli przejdziesz uint
do %
, kompilator C # faktycznie wygeneruje kod maszynowy przy użyciu bitowego AND, gdy drugi argument jest znaną potęgą dwóch.
W moim pytaniu istnieje rzeczywiste zastosowanie w świecie -
Odpowiadasz tylko na pierwsze powiadomienie WM_KEYDOWN?
Podczas korzystania z komunikatu WM_KEYDOWN w Windows C bit 30 interfejsu API określa poprzedni stan klucza. Wartość wynosi 1, jeśli klucz jest wciśnięty przed wysłaniem wiadomości, lub zero, jeśli klucz jest podniesiony
Są one najczęściej używane do operacji bitowych (niespodzianka). Oto kilka rzeczywistych przykładów znalezionych w bazie kodu PHP.
Kodowanie znaków:
if (s <= 0 && (c & ~MBFL_WCSPLANE_MASK) == MBFL_WCSPLANE_KOI8R) {
Struktury danych:
ar_flags = other->ar_flags & ~SPL_ARRAY_INT_MASK;
Sterowniki bazy danych:
dbh->transaction_flags &= ~(PDO_TRANS_ACCESS_MODE^PDO_TRANS_READONLY);
Implementacja kompilatora:
opline->extended_value = (opline->extended_value & ~ZEND_FETCH_CLASS_MASK) | ZEND_FETCH_CLASS_INTERFACE;
Za każdym razem, gdy zaczynałem programowanie w C, rozumiałem tabele prawdy i tak dalej, ale nie wszystko klikało, jak właściwie z niego korzystać, dopóki nie przeczytałem tego artykułu http://www.gamedev.net/reference/articles/article1563.asp (który podaje przykłady z życia)
x == 1
i y == 2
, to x || y
ocenia na 1, a x | y
ocenia na 0. Nie widzę też, dlaczego x^true
jest !x
w jakikolwiek sposób lepszy . To bardziej pisanie na maszynie, mniej idiomatyczne, a jeśli x
nie, to bool
nie jest wiarygodne.
x^true
przewyższa !x
to, że some->complicated().member->lookup ^= true;
nie ma wersji jednoargumentowych przypisań złożonych.
Nie sądzę, że liczy się to jako bitowe, ale tablica Ruby definiuje operacje ustawiania za pomocą zwykłych liczb całkowitych operatorów bitowych. Tak [1,2,4] & [1,2,3] # => [1,2]
. Podobnie dla a ^ b #=> set difference
i a | b #=> union
.
Rozwiązanie liniowe Tower Of Hanoi wykorzystuje operacje bitowe do rozwiązania problemu.
public static void linear(char start, char temp, char end, int discs)
{
int from,to;
for (int i = 1; i < (1 << discs); i++) {
from = (i & i-1) % 3;
to = ((i | i-1) + 1) % 3;
System.out.println(from+" => "+to);
}
}
Wyjaśnienie tego rozwiązania można znaleźć tutaj