praktyczne zastosowania operacji bitowych [zamknięte]

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 przypisać użytkownikowi ich 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ązywanie sudoku, ale załóżmy, że tak.

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

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

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

Wartość 0 oznacza, że komórka jest nadal pusta, a wartości z zakresu [1U, 9u] są rzeczywistymi wartościami w zarządzie.

Można utrzymywać tablice bitmasek, 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 od liczby do bitpattern, z jednym bitem odpowiadającym temu zestawowi liczb, jest bardzo prosty

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

W C# można obliczyć bitpattern w ten sposób (value jest uint):

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

W linii powyżej 1u odpowiadającej bitpattern 00000000 00000000 00000000 00000001 jest przesunięty w lewo o value - 1. Jeśli na przykład value == 5, otrzymujesz

00000000 00000000 00000000 00010000

Na początku maską dla każdego wiersza, kolumny i pola jest 0. Za każdym razem, gdy umieścisz jakiś numer na tablicy, aktualizujesz maskę, więc bit odpowiadający do nowej wartości jest ustawiona.

Załóżmy, że wstawiasz wartość 5 w wierszu 3 (wiersze i kolumny są ponumerowane od 0). Maska dla wiersza 3 jest przechowywana w maskForNumbersSetInRow[3]. Załóżmy również, że przed wstawką były już liczby {1, 2, 4, 7, 9} w wierszu 3. Wzór bitowy 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żna to zrobić za pomocą operatora bitowego lub (|). Najpierw tworzymy 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 masce maskForNumbersSetInRow[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 zastosowanego do maski i odpowiadającego tej wartości wzorca bitowego jest niezerowy, to wartość jest już w wierszu. Jeżeli wynikiem jest 0, wartość nie znajduje się w wierszu.

Na przykład, jeśli chcesz sprawdzić, czy wartość 3 jest w wierszu, 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 planszy, aktualizowania odpowiednich bitmasek i sprawdzania, czy ruch jest legalny.

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 ten 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);
}

Jeśli kiedykolwiek będziesz musiał komunikować się ze sprzętem, musisz użyć bit twidling w pewnym momencie.

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

Tyle rzeczy

Dziesiątki bitowych przykładów tutaj

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

Mogą być używane do całego obciążenia różnych aplikacji, oto pytanie, które wcześniej tu zamieszczałem, które wykorzystuje operacje bitowe:

Bitwise i, bitwise Inclusive lub question, w Javie

Dla innych przykładów, spójrz na (powiedzmy) oznaczonych wyliczeń.

W moim przykładzie używałem operacji bitowych, aby zmienić zakres liczby binarnej z -128...127 do 0..255 (zmiana reprezentacji z podpisanej na niepodpisaną).

MSN artykuł tutaj - >

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

Jest przydatne.

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 w kombinacji elementów, wtedy bitwise jest zwykle łatwym rozwiązaniem.

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

Muszę powiedzieć, że jednym z najczęstszych zastosowań jest modyfikowanie pól bitowych w celu kompresji danych. Widać to głównie w programach próbujących być ekonomicznymi z pakietami.

Przykład kompresji sieci przy użyciu bitfieldów

Jedną z najczęstszych rzeczy, do których ich używam w C#, jest tworzenie hashcodów. Jest kilka całkiem dobrych metod haszujących, które ich używają. Na przykład dla klasy współrzędnych z X i Y, które były zarówno ints mogę użyć:

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

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

Innym jest łączenie wyliczeń flag. Np. RegexOptions.Compiled | RegexOptions.CultureInvariant | RegexOptions.IgnoreCase

Są pewne operacje niskiego poziomu, które nie są zwykle konieczne, gdy kodujesz na frameworku takim jak. NET (np. w C# Nie będę musiał pisać kodu, aby przekonwertować UTF - 8 na UTF-16, to jest dla mnie w frameworku), ale oczywiście ktoś musiał napisać ten kod.

Istnieje kilka technik, takich jak zaokrąglanie do najbliższej liczby binarnej (np. round up 1010 to 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 to nie jest zbyt powszechne.

Wreszcie, można również użyć ich do mikro-optymalizacji matematyki, takiej jak << 1 zamiast * 2, ale dodam, że jest to ogólnie zły pomysł, ponieważ ukrywa intencje prawdziwego kodu, nie oszczędza prawie nic w wydajności i może ukryć kilka subtelnych błędów.

1. mogą być używane do przekazywania wielu argumentów do funkcji poprzez jedną zmienną o ograniczonym rozmiarze.
2. zaletami są niski koszt pamięci lub niski koszt pamięci: dlatego zwiększona wydajność.
3. nie mogę napisać tutoriala na miejscu, ale są tam na pewno.

Sortowanie binarne. Pojawiły się problemy, w których implementacja używała operatora podziału zamiast operatora bitshift. To spowodowało, że BS nie powiodło się 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!) flagi opcji w pamięci efektywny sposób
• jeśli wykonujesz programowanie obliczeniowe, możesz rozważyć optymalizację niektórych operacji za pomocą operacji bitowych zamiast operatorów matematycznych (uważaj na skutki uboczne)
• Szary Kod !
• Tworzenie wartości wyliczonych

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

To jest powiedziane, czasami trzeba zapytać yourself: czy zwiększenie pamięci i wydajności jest warte wysiłku. Po napisaniu tego rodzaju kodu pozostaw go na chwilę i wróć do niego. Jeśli zmagasz się z tym, przepisz kod bardziej dający się utrzymać.

Z drugiej strony, czasami ma sens używanie operacji bitowych (myśl kryptografia).

Jeszcze lepiej, niech ktoś inny to przeczyta i udokumentuje.

Gry!

W dawnych czasach, używałem go do reprezentowania elementów odtwarzacza Reversi. To jest 8X8, więc zajęło mi long typ, a następnie, na przykład, jeśli chcesz wiedzieć, gdzie są wszystkie kawałki na pokładzie-ty {[1] } obu graczy kawałki.
Jeśli chcesz wszystkie możliwe kroki gracza, powiedz po prawej-Ty >> figury gracza reprezentują przez jeden, i AND to z figurami przeciwnika, aby sprawdzić, czy są teraz wspólne 1 (to znaczy, że jest przeciwnik kawałek po prawej). Wtedy rób tak dalej. jeśli wrócisz do swoich własnych kawałków - nie ruszaj się. Jeśli dojdziesz do jasnego bitu - możesz się tam przenieść i uchwycić wszystkie elementy po drodze.
(Technika ta jest szeroko stosowana w wielu rodzajach gier planszowych, w tym w szachach)