praktische Anwendungen von bitweisen Operationen [geschlossen]

1. Wofür haben Sie bitweise Operationen verwendet?
2. Warum sind sie so praktisch?
3. Kann jemand bitte ein SEHR einfaches Tutorial empfehlen?

Obwohl jeder an den Flags-Anwendungsfall gebunden zu sein scheint, ist dies nicht die einzige Anwendung von bitweisen Operatoren (obwohl wahrscheinlich die häufigste). Auch C # ist eine Sprache, die hoch genug ist, dass andere Techniken wahrscheinlich selten verwendet werden, aber es lohnt sich immer noch, sie zu kennen. Folgendes kann ich mir vorstellen:

Die Operatoren <<und >>können sich schnell mit einer Potenz von 2 multiplizieren. Natürlich wird der .NET JIT-Optimierer dies wahrscheinlich für Sie (und jeden anständigen Compiler einer anderen Sprache) tun, aber wenn Sie sich wirklich über jede Mikrosekunde ärgern, sind Sie es könnte dies nur schreiben, um sicher zu sein.

Eine andere häufige Verwendung für diese Operatoren besteht darin, zwei 16-Bit-Ganzzahlen in eine 32-Bit-Ganzzahl zu stecken. Mögen:

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

Dies ist bei der direkten Verbindung mit Win32-Funktionen üblich, die diesen Trick manchmal aus älteren Gründen verwenden.

Und natürlich sind diese Operatoren nützlich, wenn Sie Unerfahrene verwirren möchten, beispielsweise wenn Sie eine Antwort auf eine Hausaufgabenfrage geben. :) :)

In jedem echten Code , obwohl Sie werden viel besser dran , durch Multiplikation anstatt zu verwenden, da es eine viel bessere Lesbarkeit bekommt ist und die JIT optimiert sie shlund shrAnweisungen ohnehin so gibt es keine Leistungseinbuße.

Nicht wenige kuriose Tricks beschäftigen sich mit dem ^Operator (XOR). Dies ist aufgrund der folgenden Eigenschaften ein sehr leistungsfähiger Operator:

• A^B == B^A
• A^B^A == B
• Wenn Sie wissen, A^Bist es unmöglich zu sagen, was Aund Bsind, aber wenn Sie einen von ihnen kennen, können Sie den anderen berechnen.
• Der Operator leidet nicht unter Überläufen wie Multiplikation / Division / Addition / Subtraktion.

Einige Tricks, die ich mit diesem Operator gesehen habe:

Vertauschen von zwei ganzzahligen Variablen ohne Zwischenvariable:

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

Doppelt verknüpfte Liste mit nur einer zusätzlichen Variablen pro Element. Dies hat in C # wenig Sinn, kann jedoch für die Low-Level-Programmierung eingebetteter Systeme nützlich sein, bei denen jedes Byte zählt.

Die Idee ist, dass Sie den Zeiger für das erste Element verfolgen; der Zeiger für das letzte Element; und für jeden Gegenstand, den Sie im Auge behalten pointer_to_previous ^ pointer_to_next. Auf diese Weise können Sie die Liste von beiden Seiten aus durchlaufen, der Overhead ist jedoch nur halb so hoch wie bei einer herkömmlichen verknüpften Liste. Hier ist der C ++ - Code zum Durchlaufen:

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

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

Um vom Ende durchzugehen, müssen Sie nur die allererste Zeile von FirstItemnach ändern LastItem. Das ist eine weitere Speichereinsparung genau dort.

Ein anderer Ort, an dem ich den ^Operator regelmäßig in C # verwende, ist, wenn ich einen HashCode für meinen Typ berechnen muss, der ein zusammengesetzter Typ ist. Mögen:

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

Ich verwende aus Sicherheitsgründen bitweise Operatoren in meinen Anwendungen. Ich werde die verschiedenen Ebenen in einer Aufzählung speichern:

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

Und weisen Sie einem Benutzer dann seine Ebenen zu:

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

Überprüfen Sie anschließend die Berechtigungen für die ausgeführte Aktion:

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

Ich weiß nicht, wie praktisch es ist, ein Sudoku zu lösen, das Sie für möglich halten, aber nehmen wir an, es ist.

Stellen Sie sich vor, Sie möchten einen Sudoku-Löser oder auch nur ein einfaches Programm schreiben, das Ihnen das Board zeigt und Sie das Rätsel selbst lösen lässt, aber sicherstellt, dass die Bewegungen legal sind.

Die Tafel selbst wird höchstwahrscheinlich durch ein zweidimensionales Array dargestellt, wie:

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

Wert 0bedeutet, dass die Zelle noch leer ist und Werte aus dem Bereich [1u, 9u] die tatsächlichen Werte auf der Karte sind.

Stellen Sie sich nun vor, Sie möchten prüfen, ob ein Umzug legal ist. Natürlich können Sie dies mit ein paar Schleifen tun, aber mit Bitmasken können Sie die Dinge viel schneller machen. In einem einfachen Programm, das nur sicherstellt, dass die Regeln eingehalten werden, spielt es keine Rolle, aber in einem Solver könnte es.

Sie können Bitmasken-Arrays verwalten, die Informationen zu den Zahlen speichern, die bereits in jede Zeile, jede Spalte a und jedes 3x3-Feld eingefügt wurden.

uint [] maskForNumbersSetInRow = new uint[9];

uint [] maskForNumbersSetInCol = new uint[9];

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

Die Zuordnung von der Zahl zum Bitmuster, wobei ein Bit dieser eingestellten Zahl entspricht, ist sehr einfach

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

In C # können Sie das Bitmuster folgendermaßen berechnen ( valueist ein uint):

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

In der obigen 1uZeile 00000000 00000000 00000000 00000001wird das dem Bitmuster entsprechende nach links verschoben value - 1. Wenn Sie zum Beispiel value == 5bekommen

00000000 00000000 00000000 00010000

Zu Beginn ist die Maske für jede Zeile, Spalte und Box 0. Jedes Mal, wenn Sie eine Zahl auf die Tafel setzen, aktualisieren Sie die Maske, sodass das dem neuen Wert entsprechende Bit gesetzt wird.

Angenommen, Sie fügen den Wert 5 in Zeile 3 ein (Zeilen und Spalten sind von 0 nummeriert). Die Maske für Zeile 3 ist in gespeichert maskForNumbersSetInRow[3]. Nehmen wir auch an, dass vor dem Einfügen bereits Zahlen {1, 2, 4, 7, 9}in Zeile 3 vorhanden waren. Das Bitmuster in der Maske maskForNumbersSetInRow[3]sieht folgendermaßen aus:

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

Das Ziel ist es, das Bit zu setzen, das dem Wert 5 in dieser Maske entspricht. Sie können dies mit bitweisem oder operator ( |) tun . Zuerst erstellen Sie ein Bitmuster, das dem Wert 5 entspricht

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

und dann setzen Sie operator |das Bit in der Maske mitmaskForNumbersSetInRow[3]

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

oder mit kürzerer Form

maskForNumbersSetInRow[3] |= bitpattern;

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

Jetzt zeigt Ihre Maske an, dass {1, 2, 4, 5, 7, 9}diese Zeile Werte enthält (Zeile 3).

Wenn Sie überprüfen möchten, ob sich ein Wert in der Zeile befindet, können Sie operator &überprüfen, ob das entsprechende Bit in der Maske gesetzt ist. Wenn das Ergebnis dieses auf die Maske angewendeten Operators und eines diesem Wert entsprechenden Bitmusters ungleich Null ist, befindet sich der Wert bereits in der Zeile. Wenn das Ergebnis 0 ist, befindet sich der Wert nicht in der Zeile.

Wenn Sie beispielsweise überprüfen möchten, ob sich der Wert 3 in der Zeile befindet, können Sie dies folgendermaßen tun:

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.

Im Folgenden finden Sie Methoden zum Festlegen eines neuen Werts auf der Karte, zum Aktualisieren geeigneter Bitmasken und zum Überprüfen, ob ein Umzug zulässig ist.

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;

}

Mit den Masken können Sie überprüfen, ob der Umzug wie folgt legal ist:

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

Dutzende von Beispielen hier

Der Code ist in C, aber Sie können ihn leicht an C # anpassen

Wenn Sie jemals mit Hardware kommunizieren müssen, müssen Sie irgendwann ein bisschen Twiddling verwenden.

Extrahieren der RGB-Werte eines Pixelwerts.

So viele Sachen

1. Sie können verwendet werden, um viele Argumente über eine Variable mit begrenzter Größe an eine Funktion zu übergeben.
2. Vorteile sind geringer Speicheraufwand oder niedrige Speicherkosten: Daher höhere Leistung.
3. Ich kann nicht sofort ein Tutorial schreiben, aber sie sind da draußen, da bin ich mir sicher.

Sie können für eine ganze Reihe verschiedener Anwendungen verwendet werden. Hier sind einige Fragen, die ich zuvor hier gestellt habe und die bitweise Operationen verwenden:

Bitweise UND, Bitweise Inklusive ODER-Frage in Java

Schauen Sie sich für andere Beispiele (z. B.) gekennzeichnete Aufzählungen an.

In meinem Beispiel habe ich bitweise Operationen verwendet, um den Bereich einer Binärzahl von -128 ... 127 auf 0..255 zu ändern (Änderung der Darstellung von vorzeichenbehaftet in vorzeichenlos).

den MSN Artikel hier ->

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

ist nützlich.

Und obwohl dieser Link:

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

ist sehr technisch, es deckt alles ab.

HTH

Immer wenn Sie eine Option von 1 oder mehr in Kombination von Elementen haben, ist bitweise normalerweise eine einfache Lösung.

Einige Beispiele sind Sicherheitsbits (Warten auf Justins Beispiel ..), Planungstage usw.

Ich muss sagen, dass eine der häufigsten Anwendungen darin besteht, Bitfelder zu modifizieren, um Daten zu komprimieren. Sie sehen dies hauptsächlich in Programmen, die versuchen, mit Paketen sparsam umzugehen.

Beispiel für die Netzwerkkomprimierung mithilfe von Bitfeldern

Eines der häufigsten Dinge, für die ich sie in C # verwende, ist die Erstellung von Hashcodes. Es gibt einige einigermaßen gute Hashing-Methoden, die sie verwenden. ZB für eine Koordinatenklasse mit einem X und Y, die beide Ints waren, die ich verwenden könnte:

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

Dies erzeugt schnell eine Zahl, die garantiert gleich ist, wenn sie von einem gleichen Objekt erzeugt wird (vorausgesetzt, Gleichheit bedeutet, dass sowohl X- als auch Y-Parameter in beiden verglichenen Objekten gleich sind), während auch keine Kollisionsmuster für Objekte mit niedrigem Wert erzeugt werden (wahrscheinlich) am häufigsten in den meisten Anwendungen).

Ein anderer ist das Kombinieren von Flag-Aufzählungen. Z.BRegexOptions.Compiled | RegexOptions.CultureInvariant | RegexOptions.IgnoreCase

Es gibt einige Operationen auf niedriger Ebene, die normalerweise nicht erforderlich sind, wenn Sie gegen ein Framework wie .NET codieren (z. B. in C # muss ich keinen Code schreiben, um UTF-8 in UTF-16 zu konvertieren, es ist für mich da in das Framework), aber natürlich musste jemand diesen Code schreiben.

Es gibt einige Bit-Twiddling-Techniken, wie das Aufrunden auf die nächste Binärzahl (z. B. Aufrunden von 1010 auf 10000):

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

Welche sind nützlich, wenn Sie sie brauchen, aber das ist in der Regel nicht sehr häufig.

Schließlich können Sie sie auch zur Mikrooptimierung von Mathematik verwenden, z. B. << 1anstatt, * 2aber ich schließe dies ein, nur um zu sagen, dass dies im Allgemeinen eine schlechte Idee ist, da sie die Absicht des realen Codes verbirgt, fast nichts an Leistung spart und einige subtile Fehler verbergen kann .

Binäre Sortierung. Es gab Probleme, bei denen die Implementierung einen Divisionsoperator anstelle eines Bitshift-Operators verwendete. Dies führte dazu, dass BS versagte, nachdem die Sammlung Größen über 10.000.000 erreicht hatte

Sie werden sie aus verschiedenen Gründen verwenden:

• Speichern (und Überprüfen!) von Optionsflags speichereffizient
• Wenn Sie Computerprogrammierung durchführen, sollten Sie einige Ihrer Operationen optimieren, indem Sie bitweise Operationen anstelle von mathematischen Operatoren verwenden (Vorsicht vor Nebenwirkungen).
• Grauer Code !
• Aufzählungswerte erstellen

Ich bin sicher, Sie können an andere denken.

Abgesehen davon müssen Sie sich manchmal fragen: Ist der Gedächtnis- und Leistungsschub die Mühe wert? Nachdem Sie diese Art von Code geschrieben haben, lassen Sie ihn eine Weile ruhen und kehren Sie zu ihm zurück. Wenn Sie Probleme damit haben, schreiben Sie mit einem besser wartbaren Code neu.

Andererseits ist es manchmal durchaus sinnvoll, bitweise Operationen zu verwenden (denken Sie an Kryptographie).

Besser noch, lassen Sie es von jemand anderem lesen und dokumentieren Sie es ausführlich.

Spiele!

Früher habe ich damit die Figuren eines Reversi-Spielers dargestellt. Es ist 8X8, also habe ich einen longTyp gebraucht , und dann, wenn Sie zum Beispiel wissen möchten, wo sich alle orTeile an Bord befinden - Sie beide Spieler.
Wenn Sie alle möglichen Schritte eines Spielers möchten, sagen Sie rechts - Sie stellen >>die Spielsteine ​​des Spielers durch eins dar und ANDprüfen mit den gegnerischen Steinen, ob es jetzt gemeinsame Einsen gibt (das heißt, rechts von Ihnen befindet sich eine gegnerische Figur). Dann machst du das weiter. Wenn Sie zu Ihren eigenen Stücken zurückkehren - keine Bewegung. Wenn Sie ein klares Stück erreichen, können Sie dorthin ziehen und alle Teile auf dem Weg erfassen.
(Diese Technik wird häufig in vielen Arten von Brettspielen verwendet, einschließlich Schach.)