praktyczne zastosowania operacji bitowych [zamknięte]

1. Do czego używasz operacji bitowych?
2. dlaczego są tak poręczni?
3. czy ktoś może polecić BARDZO prosty tutorial?

Chociaż wydaje się, że wszyscy są uzależnieni od przypadku użycia flag, nie jest to jedyne zastosowanie operatorów bitowych (chociaż prawdopodobnie najbardziej powszechne). Również C # jest językiem na tyle wysokim poziomie, że inne techniki będą prawdopodobnie rzadko używane, ale nadal warto je znać. Oto, co przychodzi mi do głowy:

Te <<i >>operatorzy mogą szybko pomnożyć przez potęgi 2. Oczywiście, optymalizator .NET JIT będzie prawdopodobnie zrobić to dla ciebie (i każdy przyzwoity kompilatora innego języka, jak również), ale jeśli naprawdę złośliwy nad każdym mikrosekundy, ty dla pewności mógłbym to napisać.

Innym powszechnym zastosowaniem tych operatorów jest umieszczenie dwóch 16-bitowych liczb całkowitych w jedną 32-bitową liczbę całkowitą. Lubić:

int Result = (shortIntA << 16 ) | shortIntB;

Jest to powszechne w przypadku bezpośredniego połączenia z funkcjami Win32, które czasami używają tej sztuczki ze starszych powodów.

I oczywiście te operatory są przydatne, gdy chcesz zmylić niedoświadczonych, na przykład podczas udzielania odpowiedzi na pytanie domowe. :)

Jednak w każdym prawdziwym kodzie będzie o wiele lepiej, jeśli zamiast tego użyjesz mnożenia, ponieważ ma on znacznie lepszą czytelność, a JIT optymalizuje go shli shrinstrukcje, więc nie ma spadku wydajności.

Sporo ciekawych sztuczek dotyczy ^operatora (XOR). W rzeczywistości jest to bardzo potężny operator ze względu na następujące właściwości:

• A^B == B^A
• A^B^A == B
• Jeśli wiesz, nie możesz A^Bpowiedzieć, czym Ai czym Bjest, ale jeśli znasz jedno z nich, możesz obliczyć drugie.
• Operator nie cierpi z powodu żadnych przepełnień, takich jak mnożenie / dzielenie / dodawanie / odejmowanie.

Kilka sztuczek, które widziałem przy użyciu tego operatora:

Zamiana dwóch zmiennych całkowitych bez zmiennej pośredniej:

A = A^B // A is now XOR of A and B
B = A^B // B is now the original A
A = A^B // A is now the original B

Lista podwójnie połączona z tylko jedną dodatkową zmienną na pozycję. Będzie to miało niewielkie zastosowanie w C #, ale może się przydać w programowaniu niskiego poziomu systemów wbudowanych, w których liczy się każdy bajt.

Chodzi o to, aby śledzić wskaźnik dla pierwszego elementu; wskaźnik do ostatniej pozycji; i dla każdego przedmiotu, który śledzisz pointer_to_previous ^ pointer_to_next. W ten sposób możesz przeglądać listę z dowolnego końca, ale koszty ogólne to tylko połowa tradycyjnej listy połączonej. Oto kod C ++ do przechodzenia:

ItemStruct *CurrentItem = FirstItem, *PreviousItem=NULL;
while (  CurrentItem != NULL )
{
    // Work with CurrentItem->Data

    ItemStruct *NextItem = CurrentItem->XorPointers ^ PreviousItem;
    PreviousItem = CurrentItem;
    CurrentItem = NextItem;
}

Aby przejść od końca, wystarczy zmienić pierwszą linię z FirstItemna LastItem. To kolejna oszczędność pamięci.

Innym miejscem, w którym ^regularnie używam operatora w C #, jest obliczenie HashCode dla mojego typu, który jest typem złożonym. Lubić:

class Person
{
    string FirstName;
    string LastName;
    int Age;

    public int override GetHashCode()
    {
        return (FirstName == null ? 0 : FirstName.GetHashCode()) ^
            (LastName == null ? 0 : LastName.GetHashCode()) ^
            Age.GetHashCode();
    }
}

Używam operatorów bitowych dla bezpieczeństwa w moich aplikacjach. Będę przechowywać różne poziomy w Enum:

[Flags]
public enum SecurityLevel
{
    User = 1, // 0001
    SuperUser = 2, // 0010
    QuestionAdmin = 4, // 0100
    AnswerAdmin = 8 // 1000
}

A następnie przypisz użytkownikowi jego poziomy:

// Set User Permissions to 1010
//
//   0010
// | 1000
//   ----
//   1010
User.Permissions = SecurityLevel.SuperUser | SecurityLevel.AnswerAdmin;

A następnie sprawdź uprawnienia w wykonywanej akcji:

// Check if the user has the required permission group
//
//   1010
// & 1000
//   ----
//   1000
if( (User.Permissions & SecurityLevel.AnswerAdmin) == SecurityLevel.AnswerAdmin )
{
    // Allowed
}

Nie wiem, jak praktyczne jest rozwiązanie sudoku, które uważasz za takie, ale załóżmy, że tak jest.

Wyobraź sobie, że chcesz napisać narzędzie do rozwiązywania sudoku lub nawet prosty program, który pokazuje planszę i pozwala samodzielnie rozwiązać zagadkę, ale zapewnia, że ​​ruchy są legalne.

Sama tablica będzie najprawdopodobniej reprezentowana przez dwuwymiarową tablicę, taką jak:

uint [, ] theBoard = new uint[9, 9];

Wartość 0oznacza, że ​​komórka jest nadal pusta, a wartości z zakresu [1u, 9u] to rzeczywiste wartości na tablicy.

Teraz wyobraź sobie, że chcesz sprawdzić, czy jakiś ruch jest legalny. Oczywiście możesz to zrobić za pomocą kilku pętli, ale maski bitowe pozwalają na znacznie szybsze działanie. W prostym programie, który po prostu zapewnia przestrzeganie reguł, nie ma to znaczenia, ale w rozwiązaniu może.

Możesz utrzymywać tablice masek bitowych, które przechowują informacje o liczbach, które są już wstawione w każdym wierszu, każdej kolumnie a i każdym polu 3x3.

uint [] maskForNumbersSetInRow = new uint[9];

uint [] maskForNumbersSetInCol = new uint[9];

uint [, ] maskForNumbersSetInBox = new uint[3, 3];

Odwzorowanie liczby na wzorzec bitów, z jednym bitem odpowiadającym ustawionemu numerowi, jest bardzo proste

1 -> 00000000 00000000 00000000 00000001
2 -> 00000000 00000000 00000000 00000010
3 -> 00000000 00000000 00000000 00000100
...
9 -> 00000000 00000000 00000001 00000000

W C # możesz obliczyć wzorzec bitów w ten sposób ( valuejest uint):

uint bitpattern = 1u << (int)(value - 1u);

W powyższym wierszu 1uodpowiadającym wzorowi bitów 00000000 00000000 00000000 00000001jest przesuwany w lewo value - 1. Jeśli na przykład value == 5dostaniesz

00000000 00000000 00000000 00010000

Na początku maska ​​dla każdego wiersza, kolumny i pola to 0. Za każdym razem, gdy umieszczasz jakąś liczbę na tablicy, aktualizujesz maskę, więc ustawiany jest bit odpowiadający nowej wartości.

Załóżmy, że wstawiasz wartość 5 w wierszu 3 (wiersze i kolumny są numerowane od 0). Maska dla wiersza 3 jest przechowywana w maskForNumbersSetInRow[3]. Załóżmy też, że przed wstawieniem {1, 2, 4, 7, 9}w rzędzie 3 były już liczby . Wzór bitów w masce maskForNumbersSetInRow[3]wygląda następująco:

00000000 00000000 00000001 01001011
bits above correspond to:9  7  4 21

Celem jest ustawienie bitu odpowiadającego wartości 5 w tej masce. Możesz to zrobić za pomocą bitowego lub operatora ( |). Najpierw utwórz wzór bitowy odpowiadający wartości 5

uint bitpattern = 1u << 4; // 1u << (int)(value - 1u)

a następnie użyj, operator |aby ustawić bit w mascemaskForNumbersSetInRow[3]

maskForNumbersSetInRow[3] = maskForNumbersSetInRow[3] | bitpattern;

lub używając krótszej formy

maskForNumbersSetInRow[3] |= bitpattern;

00000000 00000000 00000001 01001011
                 |
00000000 00000000 00000000 00010000
                 =
00000000 00000000 00000001 01011011

Teraz twoja maska ​​wskazuje, że są wartości {1, 2, 4, 5, 7, 9}w tym wierszu (wiersz 3).

Jeśli chcesz sprawdzić, czy jakaś wartość jest w wierszu, możesz użyć, operator &aby sprawdzić, czy odpowiedni bit jest ustawiony w masce. Jeśli wynik tego operatora zastosowany do maski i wzorca bitowego odpowiadającego tej wartości jest różny od zera, wartość znajduje się już w wierszu. Jeśli wynikiem jest 0, wartości nie ma w wierszu.

Na przykład, jeśli chcesz sprawdzić, czy w wierszu znajduje się wartość 3, możesz to zrobić w ten sposób:

uint bitpattern = 1u << 2; // 1u << (int)(value - 1u)
bool value3IsInRow = ((maskForNumbersSetInRow[3] & bitpattern) != 0);

00000000 00000000 00000001 01001011 // the mask
                 |
00000000 00000000 00000000 00000100 // bitpattern for the value 3
                 =
00000000 00000000 00000000 00000000 // the result is 0. value 3 is not in the row.

Poniżej znajdują się metody ustawiania nowej wartości na tablicy, utrzymywania aktualności odpowiednich masek bitowych i sprawdzania, czy ruch jest prawidłowy.

public void insertNewValue(int row, int col, uint value)
{

    if(!isMoveLegal(row, col, value))
        throw ...

    theBoard[row, col] = value;

    uint bitpattern = 1u << (int)(value - 1u);

    maskForNumbersSetInRow[row] |= bitpattern;

    maskForNumbersSetInCol[col] |= bitpattern;

    int boxRowNumber = row / 3;
    int boxColNumber = col / 3;

    maskForNumbersSetInBox[boxRowNumber, boxColNumber] |= bitpattern;

}

Mając maski, możesz sprawdzić, czy ruch jest legalny w następujący sposób:

public bool isMoveLegal(int row, int col, uint value)
{

    uint bitpattern = 1u << (int)(value - 1u);

    int boxRowNumber = row / 3;
    int boxColNumber = col / 3;

    uint combinedMask = maskForNumbersSetInRow[row] | maskForNumbersSetInCol[col]
                        | maskForNumbersSetInBox[boxRowNumber, boxColNumber];

    return ((theBoard[row, col] == 0) && ((combinedMask & bitpattern) == 0u);
}

Dziesiątki ciekawych przykładów tutaj

Kod jest w C, ale możesz łatwo dostosować go do C #

Jeśli kiedykolwiek będziesz musiał komunikować się ze sprzętem, w pewnym momencie będziesz musiał użyć bitowego skręcania.

Wyodrębnianie wartości RGB z wartości piksela.

Tak wiele rzeczy

1. Mogą być używane do przekazywania wielu argumentów do funkcji za pośrednictwem jednej zmiennej o ograniczonym rozmiarze.
2. Zalety to niskie obciążenie pamięci lub niski koszt pamięci: w związku z tym zwiększona wydajność.
3. Nie mogę napisać tutoriala na miejscu, ale jestem pewien, że tam są.

Mogą być używane do całego obciążenia różnych aplikacji, oto pytania, które wcześniej tutaj zamieściłem, które wykorzystują operacje bitowe:

Bitowe AND, Bitowe uwzględniające LUB pytanie w Javie

Aby zapoznać się z innymi przykładami, spójrz na (powiedzmy) oflagowane wyliczenia.

W moim przykładzie używałem operacji bitowych, aby zmienić zakres liczby binarnej z -128 ... 127 na 0..255 (zmieniając jej reprezentację z podpisanej na niepodpisaną).

artykuł MSN tutaj ->

http://msdn.microsoft.com/en-us/library/6a71f45d%28VS.71%29.aspx

jest przydatny.

I chociaż ten link:

http://weblogs.asp.net/alessandro/archive/2007/10/02/bitwise-operators-in-c-or-xor-and-amp-amp-not.aspx

jest bardzo techniczny, obejmuje wszystko.

HTH

Za każdym razem, gdy masz opcję 1 lub więcej kombinacji elementów, wtedy bitowe jest zwykle łatwym rozwiązaniem.

Niektóre przykłady obejmują bity bezpieczeństwa (czekanie na próbkę Justina ...), planowanie dni itp.

Muszę powiedzieć, że jednym z najczęstszych zastosowań jest modyfikowanie pól bitowych w celu kompresji danych. Najczęściej widzisz to w programach, które próbują oszczędzać na pakietach.

Przykład kompresji sieci przy użyciu pól bitowych

Jedną z najczęstszych rzeczy, do których używam ich w C #, jest tworzenie kodów skrótów. Jest kilka całkiem dobrych metod haszowania, które ich używają. Np. Dla klasy współrzędnych z X i Y, które były obydwoma intami, mogę użyć:

public override int GetHashCode()
{
  return x ^ ((y << 16) | y >> 16);
}

To szybko generuje liczbę, która na pewno jest równa, gdy jest wytwarzana przez równy obiekt (zakładając, że równość oznacza, że ​​oba parametry X i Y są takie same w obu porównywanych obiektach), jednocześnie nie wytwarzając zderzających się wzorców dla obiektów o niskiej wartości (prawdopodobnie najczęściej w większości zastosowań).

Innym jest łączenie wyliczeń flag. Na przykładRegexOptions.Compiled | RegexOptions.CultureInvariant | RegexOptions.IgnoreCase

Jest kilka operacji niskiego poziomu, które częściej nie są konieczne, gdy kodujesz w środowisku, takim jak .NET (np. W C # nie będę musiał pisać kodu, aby przekonwertować UTF-8 na UTF-16, jest dla mnie w framework), ale oczywiście ktoś musiał napisać ten kod.

Istnieje kilka technik manipulowania bitami, takich jak zaokrąglanie w górę do najbliższej liczby binarnej (np. Zaokrąglanie w górę od 1010 do 10000):

        unchecked
        {
            --x;
            x |= (x >> 1);
            x |= (x >> 2);
            x |= (x >> 4);
            x |= (x >> 8);
            x |= (x >> 16);
            return ++x;
        }

Które są przydatne, gdy ich potrzebujesz, ale nie jest to zbyt częste.

Wreszcie, możesz ich również użyć do mikro-optymalizacji matematyki, takiej jak << 1zamiast, * 2ale dodam to tylko po to, aby powiedzieć, że jest to ogólnie zły pomysł, ponieważ ukrywa zamiar prawdziwego kodu, nie zapisuje prawie nic w wydajności i może ukryć niektóre subtelne błędy .

Sortowanie binarne. Wystąpiły problemy, w których implementacja korzystała z operatora dzielenia zamiast operatora przesunięcia bitowego. Spowodowało to niepowodzenie BS po tym, jak kolekcja osiągnęła rozmiary powyżej 10 000 000

Będziesz ich używać z różnych powodów:

• przechowywanie (i sprawdzanie!) flag opcji w sposób oszczędzający pamięć
• jeśli robisz programowanie obliczeniowe, możesz rozważyć optymalizację niektórych operacji za pomocą operacji bitowych zamiast operatorów matematycznych (uwaga na efekty uboczne)
• Gray Code !
• tworzenie wartości wyliczonych

Jestem pewien, że potrafisz myśleć o innych.

Biorąc to pod uwagę, czasami trzeba zadać sobie pytanie: czy zwiększenie pamięci i wydajności jest warte wysiłku. Po napisaniu takiego kodu pozwól mu odpocząć na chwilę i wróć do niego. Jeśli masz z tym problemy, napisz kod z łatwiejszym w utrzymaniu.

Z drugiej strony czasami ma sens użycie operacji bitowych (pomyśl o kryptografii).

Jeszcze lepiej, niech przeczyta go ktoś inny i obszernie udokumentuj.

Gry!

Kiedyś używałem go do reprezentowania pionków gracza Reversi. To 8X8, więc zajęło mi to pewien longtyp, a potem , na przykład, jeśli chcesz wiedzieć, gdzie są wszystkie orbierki na planszy - obaj bierki graczy.
Jeśli chcesz poznać wszystkie możliwe kroki gracza, powiedz po prawej - >>reprezentacja pionków gracza o jeden, a ANDwraz z figurami przeciwnika sprawdź, czy są teraz wspólne jedynki (to znaczy, że po twojej prawej stronie znajduje się figura przeciwnika). Więc rób to dalej. jeśli wrócisz do swoich elementów - bez ruchu. Jeśli dojdziesz do wolnej części - możesz się tam przenieść i złapać wszystkie elementy po drodze.
(Technika ta jest szeroko stosowana w wielu rodzajach gier planszowych, w tym w szachach)