Reale Anwendungsfälle von bitweisen Operatoren [geschlossen]

223

Was sind einige reale Anwendungsfälle der folgenden bitweisen Operatoren?

  • UND
  • XOR
  • NICHT
  • ODER
  • Links- / Rechtsverschiebung
Louis Go
quelle
1
Ich erinnere mich, als ich zum ersten Mal von ihnen erfuhr, schien es, als würden sie nur für Low-Level-C verwendet ... aber seitdem sind sie per Toolbox eingegeben worden und ich benutze sie oft, auch wenn ich "High-Level" -Programmierung mache. Sie sind jetzt wie + und * für mich.
Eiche
2
@Anon.: In meinen Augen sollte die reale Welt alles andere als Low-Level-Programmierung bedeuten, was die offensichtlichste Verwendung von bitweisen Operatoren ist.
Olivier Lalonde
Kann auch binäres XOR verwenden, um eine fehlende Zahl in einer Permutation zu finden: martinkysel.com/codility-permmissingelem-solution
Janac Meena

Antworten:

215
  • Bitfelder (Flags)
    Sie sind die effizienteste Art, etwas darzustellen, dessen Status durch mehrere "Ja oder Nein" -Eigenschaften definiert ist. ACLs sind ein gutes Beispiel. Wenn Sie beispielsweise 4 diskrete Berechtigungen (Lesen, Schreiben, Ausführen, Ändern von Richtlinien) haben, ist es besser, diese in 1 Byte zu speichern, als 4 zu verschwenden. Diese können für zusätzlichen Komfort Aufzählungstypen in vielen Sprachen zugeordnet werden.

  • Die Kommunikation über Ports / Sockets
    umfasst immer Prüfsummen, Parität, Stoppbits, Flusssteuerungsalgorithmen usw., die normalerweise von den Logikwerten einzelner Bytes im Gegensatz zu numerischen Werten abhängen, da das Medium möglicherweise nur ein Bit übertragen kann eine Zeit.

  • Komprimierung, Verschlüsselung
    Beide sind stark von bitweisen Algorithmen abhängig. Schauen Sie sich den Deflate- Algorithmus als Beispiel an - alles ist in Bits, nicht in Bytes.

  • Finite-State-Maschinen
    Ich spreche hauptsächlich von der Art, die in eine Hardware eingebettet ist, obwohl sie auch in Software zu finden sind. Dies sind die kombinatorischen in der Natur - sie könnten buchstäblich bekommen „kompilierte“ bis zu einer Reihe von Logikgattern, so dass sie wie folgt ausgedrückt werden AND, OR, NOTusw.

  • Grafik Hier ist kaum genug Platz, um in jeden Bereich zu gelangen, in dem diese Operatoren in der Grafikprogrammierung verwendet werden. XOR(oder ^) ist hier besonders interessant, da ein zweites Anwenden derselben Eingabe die erste rückgängig macht. Ältere GUIs stützten sich bei der Hervorhebung der Auswahl und anderen Überlagerungen darauf, um kostspielige Neuzeichnungen zu vermeiden. Sie sind immer noch nützlich in langsamen Grafikprotokollen (dh Remotedesktop).

Dies waren nur die ersten Beispiele, die ich mir ausgedacht habe - dies ist kaum eine vollständige Liste.

Aaronaught
quelle
Hallo @Aaronaught, Sie haben wirklich ein sehr gutes Wissen mit uns geteilt. Ich bin daran interessiert, mehr über die realen Fälle von Bitwise Operator zu erfahren. Würde es Ihnen etwas ausmachen, Ihre Referenz mit uns zu teilen, wäre es wirklich hilfreich, mehr darüber zu lesen.
Heena Hussain
Sind bitweise Operationen für vektorisierbare Berechnungen nützlich?
Aaron Franke
46

Ist es seltsam?

(value & 0x1) > 0

Ist es durch zwei (gerade) teilbar?

(value & 0x1) == 0
Seth
quelle
3
Abhängig von Ihrem Sprachwert kann & 0x1> 0 als Wert & (0x1> 0)
analysiert werden
3
@leeeroy - Richtig. Einige Parens hinzugefügt.
Seth
Moderne Optimierer konvertieren Ausdrücke wie (Wert% 2)! = 0 automatisch in die obigen Ausdrücke. godbolt.org/z/mYEBH4
Ferrarezi
26

Hier sind einige gebräuchliche Redewendungen, die sich mit Flags befassen, die als einzelne Bits gespeichert sind.

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

unsigned int flags = 0;

Setzen Sie das Flag Chargeable:

flags |= Chargeable;

CallerIDMissing-Flag löschen:

flags &= ~CallerIDMissing;

Testen Sie, ob CallerIDMissing und Chargeable eingestellt sind:

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

}
nos
quelle
25

Ich habe bei der Implementierung eines Sicherheitsmodells für ein CMS bitweise Operationen verwendet. Es gab Seiten, auf die Benutzer zugreifen konnten, wenn sie sich in geeigneten Gruppen befanden. Ein Benutzer kann sich in mehreren Gruppen befinden, daher mussten wir überprüfen, ob es einen Schnittpunkt zwischen den Benutzergruppen und den Seitengruppen gab. Deshalb haben wir jeder Gruppe eine eindeutige Potenz-2-Kennung zugewiesen, z.

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

Wir ODER diese Werte zusammen und speichern den Wert (als einzelnes int) mit der Seite. Wenn beispielsweise die Gruppen A und B auf eine Seite zugreifen können, speichern wir den Wert 3 (der binär 00000011 ist) als Seitenzugriffskontrolle. In ähnlicher Weise speichern wir einen Wert von ORed-Gruppen-IDs mit einem Benutzer, um darzustellen, in welchen Gruppen sie sich befinden.

Um zu überprüfen, ob ein bestimmter Benutzer auf eine bestimmte Seite zugreifen kann, müssen Sie nur die Werte UND-Werte zusammen UND prüfen, ob der Wert nicht Null ist. Dies ist sehr schnell, da diese Prüfung in einem einzigen Befehl implementiert wird, keine Schleifen, keine Datenbank-Roundtrips.

JonoW
quelle
24

Low-Level-Programmierung ist ein gutes Beispiel. Möglicherweise müssen Sie beispielsweise ein bestimmtes Bit in ein Speicherregister schreiben, damit eine Hardware das tut, was Sie möchten:

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

Auch htonl()und htons()ist die Verwendung implementiert &und |Operatoren (bei Maschinen , dessen endianness (Byte - Reihenfolge) kein Netzwerk übereinstimmen , um):

#define htons(a) ((((a) & 0xff00) >> 8) | \
                  (((a) & 0x00ff) << 8))

#define htonl(a) ((((a) & 0xff000000) >> 24) | \
                  (((a) & 0x00ff0000) >>  8) | \
                  (((a) & 0x0000ff00) <<  8) | \
                  (((a) & 0x000000ff) << 24))
Carl Norum
quelle
7
Nicht jeder spricht in der Maschine. Was macht dein zweites Beispiel?
ChaosPandion
7
htons()und htonl()sind POSIX-Funktionen zum Austauschen von a shortoder a longvon der host ( h) -Endianness in die network ( n) - Bytereihenfolge.
Carl Norum
Sie können eine ähnliche Methode verwenden, um eine Bitumkehr in O (logN) -Operationen durchzuführen.
Mike DeSimone
lol als ich das zum ersten Mal sah, dachte ich, es wäre eine Montage!
0x499602D2
Ist nicht htonl()für einen 32-Bit- intWert? longbedeutet 64-Bit in vielen Sprachen.
Aaron Franke
21

Ich benutze sie zum Beispiel, um RGB (A) -Werte aus gepackten Farbwerten zu erhalten.

Terje
quelle
Und das sehr schnell!
Callum Rogers
In C # ist dies einer der Fälle, in denen es wirklich die beste Lösung für Lesbarkeit und Geschwindigkeit ist.
CaptainCasey
4
Auf meinem Computer (a & b) >> cist es mehr als fünfmal schneller als a % d / e(beide Möglichkeiten, einen einzelnen Farbwert aus einem Int zu extrahieren, das ARGB darstellt). Jeweils 6,7 s und 35,2 s für 1 Milliarde Iterationen.
Benji XVI
@BenjiXVI C # verfügt hierfür über Compiler-Optimierungen. Der Grund, warum Sie einen Geschwindigkeitsunterschied beobachten, ist, dass in C # %nicht der Moduloperator, sondern der Restoperator ist. Sie sind für positive Werte äquivalent, unterscheiden sich jedoch von negativen. Wenn Sie die entsprechenden Einschränkungen vorsehen (vorbei an einer uintStelle von intzum Beispiel) , dann die beiden Beispiele sollen die gleiche Geschwindigkeit.
Aaron Franke
Entschuldigung, ich weiß, es ist lange her. Können Sie bitte ein Beispiel zeigen, wie Sie sie verwenden, um jeden einzelnen RGB-Wert zu erhalten?
Jinx
14

Wenn ich ein paar boolesche Flags habe, speichere ich sie alle gerne in einem int.

Ich hole sie mit bitweisem UND raus. Beispielsweise:

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

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

etc.

Tenner
quelle
23
Hoffentlich sind das tatsächlich Konstanten in Ihrem realen Code und keine magischen Zahlen :)
Earlz
1
Ein Beispiel für die Verwendung von Booleschen Flags in der Welt ohne niedrige Ebenen ist die Arbeit mit verschiedenen GUI-Plattformen. Zum Beispiel könnten Sie my_button.Style | = STYLE_DISABLED verwenden, um es auszuschalten.
MauriceL
1
Ich weiß, dass dieses Thema sprachunabhängig ist, aber C bietet eine einfache Möglichkeit, dies mit Bitfeldern zu tun, damit Sie Dinge wie verwenden können if (flags.feature_one_is_one) { // turn on feature }. Es ist im ANSI C-Standard enthalten, daher sollte Portabilität kein Problem sein.
Polandeer
Es wäre schön, eine Erklärung zu erhalten, was dieser Codeausschnitt bewirkt, warum Flags nicht initialisiert werden, was Sie unter "alle in einem Int speichern" verstehen, welche Notation verwendet wird ...
Angelo Oparah
12

& = AND:
Maskiert bestimmte Bits.
Sie definieren die spezifischen Bits, die angezeigt oder nicht angezeigt werden sollen. 0x0 & x löscht alle Bits in einem Byte, während 0xFF x nicht ändert. 0x0F zeigt die Bits im unteren Halbbyte an.

Konvertierung:
Um kürzere Variablen in längere mit Bitidentität umzuwandeln, müssen die Bits angepasst werden, da -1 in einem int 0xFFFFFFFF ist, während -1 in einem langen 0xFFFFFFFFFFFFFFFF ist. Um die Identität zu erhalten, wenden Sie nach der Konvertierung eine Maske an.

| = ODER
Bits setzen. Die Bits werden unabhängig gesetzt, wenn sie bereits gesetzt sind. Viele Datenstrukturen (Bitfelder) haben Flags wie IS_HSET = 0, IS_VSET = 1, die unabhängig gesetzt werden können. Um die Flags zu setzen, wenden Sie IS_HSET | an IS_VSET (In C und Assembly ist dies sehr bequem zu lesen)

^ = XOR
Finde gleiche oder unterschiedliche Bits.

~ = NICHT
Bits spiegeln.

Es kann gezeigt werden, dass alle möglichen lokalen Bitoperationen durch diese Operationen implementiert werden können. Wenn Sie möchten, können Sie einen ADD-Befehl ausschließlich durch Bitoperationen implementieren.

Einige wundervolle Hacks:

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

Thorsten S.
quelle
Der folgende Link enthält hervorragende Beispiele für die Verwendung bitweiser Operatoren in AS3 für superschnelle mathematische Operationen (könnte jedoch wahrscheinlich auf die meisten Sprachen angewendet werden): lab.polygonal.de/2007/05/10/bitwise-gems-fast- Ganzzahl-Mathematik
involviert
Ich denke, "NICHT" sollte sein = ~, nicht |=, was ODER ist.
Mike DeSimone
Für & = AND- Warum sollte ich alle Bits löschen wollen, warum sollte ich eine unveränderte Version des Bytes erhalten wollen und was soll ich mit dem unteren Halbbyte tun?
verwirrt00
1
@ confused00 richtig, der schnellere / einfachere Weg, ein Ergebnis zu annullieren, ist xores für sich. Ich kann mir einige Gründe vorstellen, warum Sie das untere Knabberzeug extrahieren möchten. Insbesondere, wenn dieses untere Halbbyte Teil einer Datenstruktur ist und Sie es als Maske oder ORmit einer anderen Struktur verwenden möchten .
James M. Lay
11

Verschlüsselung ist alles bitweise Operationen.

rekursiv
quelle
4
"Ja wirklich?" Verschlüsselungsimplementierungen verwenden wahrscheinlich bitweise Operationen, aber Verschlüsselungsalgorithmen werden normalerweise in numerischen Begriffen und nicht in Form von Bitdarstellungen beschrieben.
Constantin
1
Was machen Sie mit anderen Algorithmen als sie zu implementieren? Ich bin neugierig.
rekursiv
2
@Constantin: Siehe zum Beispiel die Beschreibung, wie DES implementiert wird: ( en.wikipedia.org/wiki/…
Wayne Conrad
1
@recursive, Wenn Sie persönlich nach mir fragen - ich entwerfe weder kryptografische Algorithmen noch implementiere ich sie. Aber die Leute machen viele Dinge, wie sie auf theoretische Schwächen zu analysieren.
Constantin
@Constantin: Schauen Sie sich das an, dies ist nur ein Beispiel unter vielen, wie (ein Teil von) kryptografischen Algorithmen normalerweise beschrieben werden: en.wikipedia.org/wiki/Substitution_box
SyntaxT3rr0r
9

Sie können sie als schnelle und schmutzige Methode zum Hashing von Daten verwenden.

int a = 1230123;
int b = 1234555;
int c = 5865683;
int hash = a ^ b ^ c;
ChaosPandion
quelle
8

Ich habe gerade vor ^ungefähr drei Minuten bitwise-XOR ( ) verwendet, um eine Prüfsumme für die serielle Kommunikation mit einer SPS zu berechnen ...

Ezod
quelle
7

Bitweise & wird verwendet, um einen bestimmten Teil eines Bytes zu maskieren / zu extrahieren.

1 Byte Variable

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

Insbesondere der Schichtoperator (<< >>) wird häufig für Berechnungen verwendet.

DrDol
quelle
6

Dies ist ein Beispiel zum Lesen von Farben aus einem Bitmap-Bild im Byte-Format

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.

Ich hoffe dieses winzige Beispiel hilft ....

Buhake Sindi
quelle
5

In der abstrahierten Welt der heutigen modernen Sprache nicht zu viele. Datei-E / A ist eine einfache Aufgabe, die in den Sinn kommt, obwohl sie bitweise Operationen an bereits implementierten Objekten ausführt und keine bitweisen Operationen implementiert. Als einfaches Beispiel zeigt dieser Code das Entfernen des schreibgeschützten Attributs für eine Datei (damit es mit einem neuen FileStream verwendet werden kann, der FileMode.Create angibt) in 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);
}

In Bezug auf benutzerdefinierte Implementierungen ist hier ein aktuelles Beispiel: Ich habe ein "Message Center" zum Senden sicherer Nachrichten von einer Installation unserer verteilten Anwendung an eine andere erstellt. Grundsätzlich ist es analog zu E-Mail, einschließlich Posteingang, Postausgang, Gesendet usw., aber es hat auch eine garantierte Zustellung mit Lesebestätigungen, sodass es zusätzliche Unterordner gibt, die über "Posteingang" und "gesendet" hinausgehen. Was dies bedeutete, war für mich eine Anforderung, generisch zu definieren, was "im Posteingang" oder was "im gesendeten Ordner" ist. Von dem gesendeten Ordner muss ich wissen, was gelesen und was ungelesen ist. Von dem, was ungelesen ist, muss ich wissen, was empfangen wurde und was nicht. Ich verwende diese Informationen, um eine dynamische where-Klausel zu erstellen, die eine lokale Datenquelle filtert und die entsprechenden Informationen anzeigt.

So wird die Aufzählung zusammengestellt:

    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
    }

Sehen Sie, was das tut? Durch Anding (&) mit dem Enum-Wert "Inbox", InboundMemos, weiß ich, dass sich InboundMemosForMyOrders im Posteingang befindet.

Hier ist eine überarbeitete Version der Methode, mit der der Filter erstellt und zurückgegeben wird, der eine Ansicht für den aktuell ausgewählten Ordner definiert:

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

Extrem einfach, aber eine ordentliche Implementierung auf einer Abstraktionsebene, die normalerweise keine bitweisen Operationen erfordert.

Fred
quelle
4

Die Base64-Codierung ist ein Beispiel. Die Base64-Codierung wird verwendet, um Binärdaten als druckbare Zeichen für das Senden über E-Mail-Systeme (und andere Zwecke) darzustellen. Die Base64-Codierung konvertiert eine Reihe von 8-Bit-Bytes in 6-Bit-Zeichensuchindizes. Bitoperationen, Verschieben und "oder", "Noting" sind sehr nützlich, um die für die Base64-Codierung und -Decodierung erforderlichen Bitoperationen zu implementieren.

Dies ist natürlich nur eines von unzähligen Beispielen.

rayd09
quelle
4

Ich bin überrascht, dass niemand die offensichtliche Antwort für das Internetzeitalter ausgewählt hat. Berechnung gültiger Netzwerkadressen für ein Subnetz.

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

Rechnung
quelle
4

Normalerweise sind bitweise Operationen schneller als Multiplizieren / Dividieren. Wenn Sie also eine Variable x mit beispielsweise 9 multiplizieren müssen, tun Sie dies, x<<3 + xwas einige Zyklen schneller wäre alsx*9 . Wenn sich dieser Code in einem ISR befindet, sparen Sie Antwortzeit.

Wenn Sie ein Array als kreisförmige Warteschlange verwenden möchten, ist es ebenfalls schneller (und eleganter), Wrap-Around-Prüfungen mit bitweisen Operationen durchzuführen. (Ihre Array-Größe sollte eine Potenz von 2 sein). Beispiel: Sie können tail = ((tail & MASK) + 1)anstelle von verwenden tail = ((tail +1) < size) ? tail+1 : 0, wenn Sie einfügen / löschen möchten.

Wenn ein Fehlerflag mehrere Fehlercodes zusammenhalten soll, kann jedes Bit einen eigenen Wert enthalten. Sie können es mit jedem einzelnen Fehlercode UND überprüfen. Dies wird in Unix-Fehlercodes verwendet.

Auch eine n-Bit-Bitmap kann eine wirklich coole und kompakte Datenstruktur sein. Wenn Sie einen Ressourcenpool der Größe n zuweisen möchten, können wir n-Bits verwenden, um den aktuellen Status darzustellen.

Benutzer3382203
quelle
3

Niemand scheint Fixpunktmathematik erwähnt zu haben.

(Ja, ich bin alt, ok?)

Jason Williams
quelle
3

Ist eine Zahl xeine Potenz von 2? (Nützlich zum Beispiel bei Algorithmen, bei denen ein Zähler inkrementiert wird und eine Aktion nur logarithmisch ausgeführt werden soll.)

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

Welches ist das höchste Bit einer ganzen Zahl x? (Dies kann zum Beispiel verwendet werden, um die Mindestleistung von 2 zu ermitteln, die größer ist als x)

x |= (x >>  1);
x |= (x >>  2);
x |= (x >>  4);
x |= (x >>  8);
x |= (x >> 16);
return x - (x >>> 1); // ">>>" is unsigned right shift

Welches ist das niedrigste 1Bit einer ganzen Zahl x? (Hilft zu finden, wie oft durch 2 teilbar ist.)

x & -x
Dimitris Andreou
quelle
Die vorzeichenlose Rechtsverschiebung erfolgt in C, indem die LHS in einen vorzeichenlosen Typ umgewandelt wird. Ihre letzte Formel findet nicht das niedrigste [gesetzte] Bit, sondern prüft, ob X eine Potenz von 2 ist. Um das niedrigste gesetzte Bit zu finden, tun Sie dies x & -x.
Potatoswatter
Hmm, Sie haben Recht, irgendwie habe ich x & -x durch das erste Snippet ersetzt, danke für die Bearbeitung
Dimitris Andreou
3

Bitweise Operatoren sind nützlich, um Arrays zu schleifen, deren Länge die Potenz von 2 ist. Wie viele Leute erwähnt haben, sind bitweise Operatoren äußerst nützlich und werden in Flags , Grafiken , Netzwerken und Verschlüsselung verwendet . Nicht nur das, sie sind auch extrem schnell. Mein persönlicher Lieblingsgebrauch ist das Schleifen eines Arrays ohne Bedingungen . Angenommen, Sie haben ein Array mit null Index (z. B. der Index des ersten Elements ist 0) und müssen es auf unbestimmte Zeit durchlaufen. Mit auf unbestimmte Zeit meine ich, vom ersten zum letzten Element zu gehen und zum ersten zurückzukehren. Eine Möglichkeit, dies zu implementieren, ist:

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

Dies ist der einfachste Ansatz. Wenn Sie die if- Anweisung vermeiden möchten, können Sie den Modul- Ansatz folgendermaßen verwenden:

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

Der Nachteil dieser beiden Methoden ist, dass der Moduloperator teuer ist, da er nach einer ganzzahligen Division nach einem Rest sucht. Die erste Methode führt bei jeder Iteration eine if- Anweisung aus. Mit dem bitweisen Operator können Sie jedoch, wenn die Länge Ihres Arrays eine Potenz von 2 ist, einfach eine Sequenz wie diese generieren, 0 .. length - 1indem Sie den &(bitweisen und) Operator wie folgt verwenden i & length. Wenn Sie dies wissen, wird der Code von oben

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

So funktioniert es. Im Binärformat wird jede Zahl, deren Potenz von 2 von 1 subtrahiert wird, nur mit Einsen ausgedrückt. Zum Beispiel ist 3 in binär 11, 7 ist 111, 15 ist 1111und so weiter, Sie bekommen die Idee. Was passiert nun, wenn Sie &eine Zahl gegen eine Zahl haben, die nur aus Einsen in Binärform besteht? Nehmen wir an, wir machen das:

num & 7;

Wenn numkleiner oder gleich 7 ist, ist das Ergebnis, numdass jedes Bit &mit 1 selbst ist. Wenn numgrößer als 7 ist, &berücksichtigt der Computer während des Betriebs die führenden Nullen von 7, die natürlich nach dem &Betrieb als Nullen bleiben, nur der nachfolgende Teil bleibt übrig. Wie im Fall von 9 & 7in binär wird es so aussehen

1001 & 0111

Das Ergebnis ist 0001, was 1 in Dezimalzahl ist und das zweite Element im Array adressiert.

Benutzer3552161
quelle
Ihre Bemerkung zur Hälfte des Textes, wenn die Länge Ihres Arrays eine Zweierpotenz ist, sollte in den ersten Satz eingefügt werden. Es ist eine sehr schwerwiegende Einschränkung, diesen Trick zu verwenden. Persönlich würde ich dies sowieso nicht implementieren, der Code ist schwerer zu verstehen als die if- oder mod- Ansätze.
Jan Doggen
@ JanDoggen Du hast recht, ich werde es in den ersten Satz setzen. Was das Array als Zweierpotenz betrifft, so hat es meiner Erfahrung nach mehr als ein paar Mal funktioniert. Wahrscheinlich, weil es mit Netzwerk und Grafik zu tun hatte.
user3552161
1
In diesem Beitrag sollte gezeigt werden, dass bitweise Operatoren nützlich sind, um Folgen von Zahlen zu generieren. 0, 1, 2, 3, 0, 1, 2 ... Die Folge war nur die erste, die mir in den Sinn kam.
user3552161
2

Ich verwende sie für Mehrfachauswahloptionen. Auf diese Weise speichere ich nur einen Wert anstelle von 10 oder mehr

SQLMenace
quelle
2

Es kann auch in einem relationalen SQL-Modell nützlich sein. Angenommen, Sie haben die folgenden Tabellen: BlogEntry, BlogCategory

Traditionell können Sie mithilfe einer BlogEntryCategory-Tabelle eine nn-Beziehung zwischen ihnen erstellen. Wenn nicht so viele BlogCategory-Datensätze vorhanden sind, können Sie einen Wert in BlogEntry verwenden, um eine Verknüpfung mit mehreren BlogCategory-Datensätzen herzustellen, genau wie bei gekennzeichneten Aufzählungen. In den meisten RDBMS gibt es diese Ein sehr schneller Operator, der in dieser 'markierten' Spalte ausgewählt werden kann ...

Tim Mahy
quelle
2

Wenn Sie nur einige Bits der Ausgänge eines Mikrocontrollers ändern möchten, das zu schreibende Register jedoch ein Byte ist, gehen Sie wie folgt vor (Pseudocode):

char newOut = OutRegister & 0b00011111 //clear 3 msb's
newOut = newOut | 0b10100000 //write '101' to the 3 msb's
OutRegister = newOut //Update Outputs

Natürlich können Sie bei vielen Mikrocontrollern jedes Bit einzeln ändern ...

Emilio M Bumachar
quelle
Welche Sprache soll das sein?
Carson Myers
@Carson: Keine Sprache, das ist Pseudocode. Als ich das vor ein paar Jahren tatsächlich getan habe, war es Versammlung, aber ich nehme an, es ist einfach, es in C zu tun. Vielen Dank für die
Hinweise
Ich habe die Antwort bearbeitet, um die Kommentare zu ändern, damit die Hervorhebung nicht so verfälscht ist. Und ich verstehe, ich dachte, es könnte C sein, aber Sie haben die 0b ... -Notation verwendet, von der ich mir wünschte, sie wäre in C verfügbar.
Carson Myers
2

Wenn Sie jemals Ihre Zahl mod (%) mit einer bestimmten Potenz von 2 berechnen möchten, können Sie diese verwenden yourNumber & 2^N-1, was in diesem Fall dasselbe ist wie yourNumber % 2^N.

number % 16 = number & 15;
number % 128 = number & 127;

Dies ist wahrscheinlich nur eine Alternative zum Modulbetrieb mit einer sehr großen Dividende von 2 ^ N ... Aber selbst dann ist seine Geschwindigkeitssteigerung gegenüber dem Modulbetrieb in meinem Test unter .NET 2.0 vernachlässigbar. Ich vermute, dass moderne Compiler solche Optimierungen bereits durchführen. Weiß jemand mehr darüber?

Dan7
quelle
Compiler verwenden diese Optimierung ... aber wenn Sie nichts über die Optimierung wissen, können Sie möglicherweise keinen Divisor auswählen, der eine exakte Potenz von 2 hat.
Ben Voigt
Es hängt von der Situation ab. In C # führt dies tatsächlich zu unterschiedlichen Ergebnissen, ebenso wie %bei der Restoperation werden Negative unterschiedlich behandelt. Wenn Sie jedoch uintan übergeben %, erzeugt der C # -Compiler tatsächlich Maschinencode mit bitweisem UND, wenn das zweite Argument eine vorbekannte Zweierpotenz ist.
Aaron Franke
1

Ich habe gesehen, dass sie in rollenbasierten Zugriffskontrollsystemen verwendet werden.

ScottE
quelle
1

In meiner Frage gibt es hier eine reale Verwendung -
Nur auf die erste WM_KEYDOWN-Benachrichtigung antworten?

Beim Konsumieren einer WM_KEYDOWN-Nachricht im Windows-API-Bit 30 wird der vorherige Schlüsselstatus angegeben. Der Wert ist 1, wenn der Schlüssel gedrückt ist, bevor die Nachricht gesendet wird, oder Null, wenn der Schlüssel oben ist

Nick Van Brunt
quelle
1

Sie werden meist für bitweise Operationen verwendet (Überraschung). Hier sind einige Beispiele aus der Praxis in der PHP-Codebasis.

Zeichenkodierung:

if (s <= 0 && (c & ~MBFL_WCSPLANE_MASK) == MBFL_WCSPLANE_KOI8R) {

Datenstrukturen:

ar_flags = other->ar_flags & ~SPL_ARRAY_INT_MASK;

Datenbanktreiber:

dbh->transaction_flags &= ~(PDO_TRANS_ACCESS_MODE^PDO_TRANS_READONLY);

Compiler-Implementierung:

opline->extended_value = (opline->extended_value & ~ZEND_FETCH_CLASS_MASK) | ZEND_FETCH_CLASS_INTERFACE;
Constantin
quelle
1

Wann immer ich mit der C-Programmierung anfing, verstand ich die Wahrheitstabellen und all das, aber es klickte nicht alles darauf, wie man sie tatsächlich verwendet, bis ich diesen Artikel http://www.gamedev.net/reference/articles/article1563.asp las (was Beispiele aus dem wirklichen Leben gibt)

Earlz
quelle
1
Nein, es ist nicht dasselbe. In C ergibt if x == 1und y == 2dann x || y1 und x | y0. Ich sehe auch nicht, warum x^truees !xin irgendeiner Weise überlegen ist . Es ist mehr tippen, weniger idiomatisch, und wenn xes nicht so ist, ist booles unzuverlässig.
David Thornley
Oh, warte ... ja, das ist meinerseits dumm. Ich kann heute nicht klar denken.
Earlz
x | y ergibt 3 (edit: nvm, ich sehe, dass du auf etwas verwiesen hast, das weg bearbeitet wurde!)
Pod
1
@DavidThornley: Ein Fall, der x^trueüberlegen ist, !xist, dass some->complicated().member->lookup ^= true; es keine zusammengesetzten Zuweisungsversionen von unären Operatoren gibt.
Ben Voigt
1

Ich denke nicht, dass dies bitweise zählt, aber Rubys Array definiert Set-Operationen durch die normalen ganzzahligen bitweisen Operatoren. Also [1,2,4] & [1,2,3] # => [1,2]. Ähnliches gilt für a ^ b #=> set differenceund a | b #=> union.

Tim Snowhite
quelle
1

Die lineare Lösung von Tower Of Hanoi verwendet bitweise Operationen, um das Problem zu lösen.

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

Die Erklärung für diese Lösung finden Sie hier

Dungeon Hunter
quelle