Przypadki użycia operatorów bitowych w świecie rzeczywistym [zamknięte]

Jakie są przykłady rzeczywistych zastosowań następujących operatorów bitowych?

• I
• XOR
• NIE
• LUB
• Przesunięcie w lewo / w prawo

• 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))

Używam ich na przykład do uzyskiwania wartości RGB (A) z upakowanych wartości kolorów.

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.

& = 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

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;

Właśnie użyłem bitowego XOR ( ^) około trzy minuty temu, aby obliczyć sumę kontrolną dla komunikacji szeregowej ze sterownikiem PLC ...

Bitowe & służy do maskowania / wydobywania określonej części bajtu.

1 bajtowa zmienna

 01110010
&00001111 Bitmask of 0x0F to find out the lower nibble
 --------
 00000010

Zwłaszcza operator zmiany biegów (<< >>) jest często używany do obliczeń.

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.

http://www.topwebhosts.org/tools/netmask.php

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 xjest 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 1bitów jest liczbą całkowitą x? (Pomaga znaleźć liczbę razy podzielną przez 2.)

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 117 111, 15 to 1111i 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 numjest mniejsze lub równe 7, wynik będzie taki, numże każdy bit &z 1 ma swoją wartość. Jeśli numjest 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 & 7binarnego 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.

Używam ich do opcji wielokrotnego wyboru, w ten sposób przechowuję tylko jedną wartość zamiast 10 lub więcej

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?

Widziałem je stosowane w systemach kontroli dostępu opartych na rolach.

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)

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 differencei 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