Rzeczywiste przypadki użycia operatorów bitowych [zamknięte]

Czy to dziwne?

(value & 0x1) > 0

Jest podzielna przez dwa (parzyste)?

(value & 0x1) == 0

Dobrym przykładem jest programowanie niskopoziomowe. Można na przykład napisać określony bit do rejestru mapowanego 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

Ponadto, htonl() i htons() są zaimplementowane przy użyciu operatorów & i | (na maszynach, których endianness (kolejność bajtów) nie pasuje do kolejności 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, aby uzyskać wartości RGB(A) Z zapakowanych wartości kolorów, na przykład.

Oto kilka typowych idiomów zajmujących się flagami przechowywanymi jako pojedyncze bity.

enum CDRIndicators {
  Local = 1 << 0,
  External = 1 << 1,
  CallerIDMissing = 1 << 2,
  Chargeable = 1 << 3
};

unsigned int flags = 0;

Ustaw flagę obciążającą:

flags |= Chargeable;

Wyczyść flagę CallerIDMissing:

flags &= ~CallerIDMissing;

Sprawdź, czy CallerIDMissing i Chargeable są ustawione:

if((flags & (CallerIDMissing | Chargeable )) == (CallerIDMissing | Chargeable)) {

}

Wykorzystałem operacje bitowe przy implementacji modelu bezpieczeństwa dla CMS. Miał strony, do których użytkownicy mogli uzyskać dostęp, jeśli byli w odpowiednich grupach. Użytkownik może być w wielu grupach, więc musieliśmy sprawdzić, czy istnieje przecięcie między grupami użytkowników i grupami stron. Przypisaliśmy więc każdej grupie unikalny identyfikator power-of-2, np.:

Group A = 1 --> 00000001
Group B = 2 --> 00000010
Group C = 3 --> 00000100

We lub te wartości razem i zapisać wartość (jako pojedynczą int) ze stroną. Np. jeśli strona może być dostępna przez grupy A i B, zapisujemy wartość 3 (która w binarnym to 00000011) jako kontrolę dostępu do stron. W podobny sposób przechowujemy wartość identyfikatorów grup ORed u użytkownika, aby reprezentować grupy, w których się znajdują.

Więc aby sprawdzić, czy dany użytkownik może uzyskać dostęp do danej strony, wystarczy i wartości razem i sprawdzić, czy wartość jest niezerowa. Jest to bardzo szybkie, ponieważ ta kontrola jest zaimplementowana w jednej instrukcji, bez pętli, bez podróży w obie strony bazy danych.

Kiedy mam kilka flag logicznych, Lubię przechowywać je wszystkie w int.

Wyciągam je za pomocą bitwise-AND. Na przykład:

int flags;
if (flags & 0x10) {
  // Turn this feature on.
}

if (flags & 0x08) {
  // Turn a second feature on.
}

Itd.

Szyfrowanie to wszystkie operacje bitowe.

& = AND:
Zamaskuj konkretne kawałki.
Definiujesz konkretne bity, które powinny być wyświetlane lub nie wyświetlane. 0x0 & x wyczyści wszystkie bity w bajcie, podczas gdy 0xFF nie zmieni x. 0x0F wyświetli bity w dolnej części.

Konwersja:
Aby dodać krótsze zmienne do dłuższych o tożsamości bitowej, konieczne jest dostosowanie bitów, ponieważ -1 W int wynosi 0xffffffffffffffffffffff. Aby zachować tożsamość, po której nakładasz maskę nawrócenie.

/ = LUB
Zestaw bitów. Bity zostaną ustawione niezależnie, jeśli są już ustawione. Wiele struktur danych (bitfieldów) ma flagi takie jak IS_HSET = 0, IS_VSET = 1, które można ustawiać samodzielnie. Aby ustawić flagi, należy zastosować IS_HSET / IS_VSET (w C i assembly jest to bardzo wygodne do odczytu)

^ = XOR
Znajdź bity, które są takie same lub różne.

~= nie
Odwróć bity.

Można wykazać, że wszystkie możliwe lokalne operacje bitowe mogą być zaimplementowane przez tych operacji. Więc jeśli chcesz, możesz zaimplementować instrukcję ADD wyłącznie za pomocą operacji bitowych.

Kilka wspaniałych hacków:

Http://www.ugcs.caltech.edu/~wnoise/base2.html
http://www.jjj.de/bitwizardry/bitwizardrypage.html

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

Możesz ich używać jako szybkiego i brudnego sposobu na hashowanie danych.

int a = 1230123;
int b = 1234555;
int c = 5865683;
int hash = a ^ b ^ c;

Bitowe & jest używane do maskowania / wyodrębniania pewnej części bajtu.

1 zmienna bajtowa

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

W szczególności operator zmiany (>) jest często używany do obliczeń.

Jest to przykład odczytu kolorów z obrazu bitmapowego w formacie bajtów

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.

Kodowanie Base64 jest przykładem. Kodowanie Base64 jest używane do reprezentowania danych binarnych jako drukowalnych znaków do wysyłania przez systemy poczty elektronicznej (i innych celów). Kodowanie Base64 konwertuje serię 8-bitowych bajtów na 6-bitowe indeksy wyszukiwania znaków. Operacje bitowe, przesuwanie i 'ING lub' ING, nie ' ING są bardzo przydatne do implementacji operacji bitowych niezbędnych do kodowania i dekodowania Base64.

To oczywiście tylko jeden z niezliczonych przykładów.

Jestem zaskoczony, że nikt nie wybrał oczywistej odpowiedzi na wiek Internetu. Obliczanie poprawnych adresów sieciowych dla podsieci.

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

W abstrakcyjnym świecie współczesnego języka, nie jest zbyt wiele. File IO jest łatwy, który przychodzi na myśl, choć to wykonywanie operacji bitowych na czymś już zaimplementowanym i nie implementuje czegoś, co używa operacji bitowych. Mimo to, jako prosty przykład, kod ten demonstruje usunięcie atrybutu Tylko do odczytu z pliku (aby mógł być używany z nowym strumieniem plików określającym Kod pliku.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 rozproszonej aplikacji do drugiej. Zasadniczo jest analogiczny do poczty e-mail, wraz z skrzynką odbiorczą, skrzynką nadawczą, wysłaną itp., ale ma również gwarantowaną dostawę z paragonami odczytu, więc istnieją dodatkowe podfoldery poza "skrzynką odbiorczą" i "wysłaną."To, co to było, było dla mnie wymogiem ogólnego zdefiniowania, co jest" w skrzynce odbiorczej "lub co jest"w folderze wysłanym". Z wysłanego folderu, muszę wiedzieć co przeczytane, a co nieprzeczytane. Z tego, co jest nieprzeczytane, muszę wiedzieć, co zostało odebrane, a co nie. Używam tych informacji do budowania dynamicznej klauzuli where, która filtruje lokalne źródło danych i wyświetla odpowiednie informacje.

Oto jak się składa enum:

    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
    }

Oto skrócona wersja metody tworzy 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 zazwyczaj nie wymaga operacji bitowych.

Wydaje się, że nikt nie wspomniał o matematyce punktów stałych.

(Tak, jestem stary, ok?)

Operatory bitowe są przydatne do zapętlania tablic, których długość jest potęgą 2. Jak wiele osób wspomniało, operatory bitowe są niezwykle przydatne i są używane w flagach , grafika, Networking, Szyfrowanie . Nie tylko to, ale są niezwykle szybkie. Moim ulubionym zastosowaniem jest loopan arrayBEZ conditionals. Załóżmy, że macie tablicę opartą na indeksie zerowym (np. indeks pierwszego elementu wynosi 0) i trzeba go zapętlić w nieskończoność. W nieskończoność mam na myśli przechodzenie 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ąć if , możesz użyć Moduł podejścia w następujący sposób:

int[] arr = new int[8];
int i = 0;
while (true) {
    print(arr[i]);
    i = i + 1;
    i = i % arr.length;
}

Dół tych dwóch metod polega na tym, że operator modułu jest drogi, ponieważ szuka reszty po podziale całkowitym. I pierwsza metoda uruchamia if Oświadczenie o każda iteracja. Z operatorem bitowym jednak jeśli długość tablicy jest potęgą 2, możesz łatwo wygenerować sekwencję podobną do 0 .. length - 1 za pomocą & (bitwise and) operator taki jak so i & length. Więc 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);
}

num & 7;

Jeśli num jest mniejszy lub równy 7, to wynik będzie num, ponieważ każdy bit & - ed z 1 jest sobą. Jeśli num jest większe niż 7, podczas operacji & komputer weźmie pod uwagę początkowe zera 7, które oczywiście pozostaną jako zera po operacji & pozostanie tylko końcowa część. Podobnie jak w przypadku 9 & 7 w pliku binarnym będzie to wyglądać

1001 & 0111

Wynik będzie 0001 który jest 1 w dziesiętnym i adresuje drugi element w tablicy.

Zwykle operacje bitowe są szybsze niż mnożenie/dzielenie. Więc jeśli chcesz pomnożyć zmienną x przez powiedzmy 9, wykonasz x<<3 + x, co byłoby o kilka cykli szybciej niż x*9. Jeśli ten kod znajduje się wewnątrz ISR, zaoszczędzisz czas odpowiedzi.

Podobnie, jeśli chcesz użyć tablicy jako okrągłej kolejki, szybsze (i bardziej eleganckie) byłoby obsługiwanie kontroli zawijania za pomocą bitowych operacji. (rozmiar tablicy powinien wynosić 2). Np:, możesz użyć tail = ((tail & MASK) + 1) zamiast tail = ((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 razem, każdy bit może zawierać oddzielną wartość. Możesz i to z każdym indywidualnym kodem błędu jako czekiem. Jest to używane w Unixowych kodach błędów.

Również N-bitowa bitmapa 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 reprezentowania bieżącego stanu.

Używam ich do wielu opcji 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żna utworzyć relację n-n między nimi za pomocą tabeli BlogEntryCategory lub gdy nie ma zbyt wielu rekordów kategorii blogów, możesz użyć jednej wartości w BlogEntry, aby połączyć się z wieloma rekordami kategorii blogów, tak jak to zrobisz z oznaczonymi enumami, w większości RDBMS są również bardzo szybkie operatory do wyboru w kolumnie "oznaczonej"...

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ć wykonane tylko logarytmicznie liczba razy)

(x & (x - 1)) == 0

Który jest najwyższym bitem liczby całkowitej x? (To na przykład może być użyte, aby znaleźć minimalną moc 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 jest najniższym 1 bitem liczby całkowitej x? (Pomaga znaleźć liczbę razy podzielną przez 2.)

x & -x

Jeśli chcesz zmienić tylko niektóre bity wyjść mikrokontrolera, ale rejestr do zapisu jest bajtem, robisz coś takiego (pseudocode):

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 na zmianę każdego bitu z osobna...

Jeśli kiedykolwiek chcesz obliczyć swoją liczbę mod (%) pewną moc 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;

Jest to prawdopodobnie tylko przydatne jako alternatywa dla operacji modułowych z bardzo dużą dywidendą, która wynosi 2^N... Ale nawet wtedy jego wzrost prędkości nad działaniem modułu jest znikomy w moim teście na. Net 2.0. Podejrzewam, że współczesne Kompilatory już wykonują takie optymalizacje. Ktoś wie coś więcej na ten temat?

Widziałem je używane w systemach kontroli dostępu opartych na rolach.

W moim pytaniu jest użyteczny Świat-
odpowiadasz tylko na pierwsze powiadomienie WM_KEYDOWN?

Podczas używania komunikatu WM_KEYDOWN w bit 30 interfejsu api windows C określa poprzedni stan klucza. Wartość jest równa 1, Jeśli klucz jest w dół przed wysłaniem wiadomości, lub jest równa zero, jeśli klucz jest w górę

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 takie tam, ale nie wszystko klikało z tym, jak właściwie z niego korzystać, dopóki nie przeczytałem tego artykułu http://www.gamedev.net/reference/articles/article1563.asp (co daje prawdziwe przykłady życia)

Nie wydaje mi się, że to liczy się jako bitowe, ale tablica ruby definiuje operacje set poprzez normalne operatory bitowe. Więc [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