Wofür sind Bitoperatoren gut? [geschlossen]

19

Programmiersprachen werden oft mit verschiedenen Bitoperatoren geliefert (z. B. bitweise Links- und Rechtsverschiebung, bitweises UND, ODER, XOR ...). Diese werden jedoch nicht sehr gewöhnt, oder zumindest war dies meine Erfahrung. Sie werden manchmal bei Programmierherausforderungen oder Interviewfragen verwendet, oder die Lösung kann sie erfordern, z.

  • Erstellen Sie ohne Verwendung eines Gleichheitsoperators eine Funktion, die zurückgibt, truewenn zwei Werte gleich sind
  • Tauschen Sie den Wert von zwei Variablen aus, ohne eine dritte Variable zu verwenden

Diese wiederum haben wahrscheinlich nur wenige reale Verwendungszwecke. Ich denke, dass sie schneller sein sollten, weil sie den Speicher auf einer niedrigen Ebene direkt manipulieren.

Warum gibt es solche in den meisten Programmiersprachen? Gibt es Anwendungsfälle aus der realen Welt?

Anto
quelle
@Anto - Ein einfaches Beispiel wäre das Senden von Daten im Wert von 256 KB mit einer Rate von jeweils 256 Wörtern (4096 Byte) an einen Client.
Ramhound
1
Msgstr "Ohne einen Gleichheitsoperator erstellen Sie eine Funktion, die true zurückgibt, wenn zwei Werte gleich sind" - in C return !(x-y);:? Ich weiß nicht
Andrew Arnold
@ Andrew: Das ist eine Lösung, aber Sie können es auch mit bitweisen Operatoren tun.
Anto
19
"Diese werden aber nicht sehr gewöhnt" - Sicher darüber? Ich benutze sie die ganze Zeit. Wir arbeiten nicht alle in Ihrer Problemdomäne.
Ed S.
2
Nicht genug für eine vollständige Antwort, aber versuchen Sie, die obersten 4 Bits eines Bytes zu lesen, ohne ein bisschen herumzuspielen, und bedenken Sie dann, dass einige Datenformate sehr dicht gepackt sind.
Setzen Sie Monica am

Antworten:

53

Nein, sie haben viele reale Anwendungen und sind grundlegende Operationen auf Computern.

Sie werden verwendet für

  • Durchsuchen von Bytes, die nicht in die Datentypen der Programmiersprachen passen
  • Umschalten der Codierung zwischen Big- und Little-Endian.
  • Packen Sie 4 6-Bit-Daten in 3 Bytes für eine serielle oder USB-Verbindung
  • Viele Bildformate weisen unterschiedliche Bitmengen auf, die jedem Farbkanal zugewiesen sind.
  • Alles, was IO-Pins in eingebetteten Anwendungen betrifft
  • Datenkomprimierung, die häufig keine Daten enthält, passt an schöne 8-Bit-Grenzen. \
  • Hashing-Algorithmen, CRC oder andere Datenintegritätsprüfungen.
  • Verschlüsselung
  • Pseudozufallszahlengenerierung
  • RAID 5 verwendet bitweises XOR zwischen Volumes, um die Parität zu berechnen.
  • Tonnen mehr

Logischerweise laufen alle Operationen auf einem Computer letztendlich auf Kombinationen dieser bitweisen Operationen auf niedriger Ebene hinaus, die innerhalb der elektrischen Tore des Prozessors stattfinden.

Whatsisname
quelle
1
+1 für Ihre ziemlich umfassende Liste, die Sie anscheinend sogar ergänzen
Anto
28
+1. @Anto: Diese Liste ist bei weitem nicht vollständig. Eine umfassende Liste von Anwendungsfällen für bitweise Operatoren in der Systemprogrammierung wäre genauso lang wie eine umfassende Liste für SQL-Abfragen in Geschäftsanwendungen. Unterhaltsame Tatsache: Ich verwende die ganze Zeit bitweise Operationen, habe aber seit Jahren keine SQL-Anweisung mehr geschrieben
;-)
4
@nikie: Und ich schreibe die ganze Zeit SQL, habe aber seit Jahren keine bitweisen Operatoren mehr benutzt! :)
FrustratedWithFormsDesigner
3
Ich arbeite in eingebetteten Systemen - bitweise Operatoren sind Brot und Butter. Wird jeden Tag bedenkenlos verwendet.
quick_now
9
Bekomme ich einen Preis, wenn ich gelegentlich Bitverschiebung in SQL verwende?
Ameise
13

Weil sie grundlegende Operationen sind.

Mit der gleichen Überlegung könnte man argumentieren, dass Addition nur wenige reale Verwendungen hat, da sie vollständig durch Subtraktion (und Negation) und Multiplikation ersetzt werden kann. Aber wir behalten die Ergänzung bei, weil es eine grundlegende Operation ist.

Und denken Sie nicht einen Moment, dass nur, weil Sie nicht viel Bedarf an bitweisen Operationen gesehen haben, dies nicht bedeutet, dass sie nicht sehr oft verwendet werden. In der Tat habe ich bitweise Operationen in fast jeder Sprache verwendet, die ich für Dinge wie Bitmaskierung verwendet habe.

Ich verwende bitweise Operationen für die Bildverarbeitung, für Bitfelder und Flags, für die Textverarbeitung (z. B. alle Zeichen einer bestimmten Klasse haben häufig ein gemeinsames Bitmuster), für die Codierung und Decodierung serialisierter Daten, für die Decodierung von VMs oder CPUs Opcodes und so weiter. Ohne bitweise Operationen würden die meisten dieser Aufgaben viel komplexere Operationen erfordern, um die Aufgabe weniger zuverlässig oder mit schlechterer Lesbarkeit auszuführen.

Beispielsweise:

// Given a 30-bit RGB color value as a 32-bit int
// A lot of image sensors spit out 10- or 12-bit data
// and some LVDS panels have a 10- or 12-bit format
b = (color & 0x000003ff);
g = (color & 0x000ffc00) >> 10;
r = (color & 0x3ff00000) >> 20;

// Going the other way:
color = ((r << 20) & 0x3ff00000) | ((g << 10) & 0x000ffc00) | (b & 0x000003ff);

Das Dekodieren von CPU-Anweisungen für RISC-CPUs (z. B. beim Emulieren einer anderen Plattform) erfordert das Extrahieren von Teilen mit einem großen Wert wie oben. Manchmal kann die Ausführung dieser Operationen mit Multiplikation und Division und Modulo usw. bis zu zehnmal langsamer sein als die entsprechenden bitweisen Operationen.

greyfade
quelle
12

Ein typisches Beispiel ist das Extrahieren der einzelnen Farben aus einem 24-Bit-RGB-Wert und zurück.


BEARBEITEN: Von http://www.docjar.com/html/api/java/awt/Color.java.html

    value =  ((int)(frgbvalue[2]*255 + 0.5))    |
                (((int)(frgbvalue[1]*255 + 0.5)) << 8 )  |
                (((int)(frgbvalue[0]*255 + 0.5)) << 16 ) |
                (((int)(falpha*255 + 0.5)) << 24 );

quelle
Dieses Beispiel in der Praxis zeigen? Ein Code-Schnipsel?
Anto
Ein besseres Beispiel könnte die Verarbeitung von 16-Bit- (4,5 bpc) oder 30-Bit- (10 bpc) RGB-Werten sein.
greyfade
@grey, zögern Sie nicht, solche Beispiele hinzuzufügen.
6

Hier ist ein Beispiel aus der Praxis, das Sie in Quake 3, Quake 4 finden. Doom III. All diese Spiele, die die Q3-Engine verwendeten .

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

(Um diesen Code zu verstehen, muss man verstehen, wie Gleitkommazahlen gespeichert sind, darauf kann ich definitiv nicht näher eingehen.)

In Bezug auf die Verwendung, es sei denn, Sie sind in Bereichen, die Bit-Verschiebung erfordern, wie z. B. Netzwerke oder Grafiken, finden Sie ihren Zweck möglicherweise etwas akademisch. Aber immer noch interessant (für mich zumindest).

Chris S
quelle
+1 Für diese Kommentare, auch wenn sie nicht deine sind. Hat mich zum Lachen gebracht.
Bassinator
4

Das Schalten ist schneller als das Multiplizieren oder Dividieren durch eine Zweierpotenz. Zum Beispiel multipliziert a << = 2 a mit 4. Umgekehrt dividiert a >> = 2 a durch vier. Mit den bitweisen Operatoren können Daten auch bitweise an ein Gerät ausgegeben werden. Zum Beispiel können wir N serielle Datenströme aus einem N-Pin-Port senden, indem wir Shift-, Xor- und "and" -Operationen innerhalb von N-Schleifen verwenden. Alles, was mit digitaler Logik erreicht werden kann, kann auch mit Software erreicht werden und umgekehrt.

Bit-Twiddler
quelle
1
Seien Sie nur vorsichtig, wenn Sie mit Auf- oder Abrunden teilen. Die Verschiebung berücksichtigt dies nicht. Daher empfinde ich es als besser, eine Codeteilung zu verwenden, wenn ich eine Division meine, und den Compiler diese in eine Verschiebung optimieren und hinzufügen zu lassen für mich.
Daemin
@Daemin: Ich arbeite mit ganzen Zahlen, wenn ich diese Technik verwende. Das Standardverhalten für die Ganzzahldivision in C und C ++ ist das Abschneiden gegen Null. Wenn Sie also eine Ganzzahl um eine Zweierpotenz nach rechts verschieben, erhalten Sie dasselbe Ergebnis, als wenn Sie eine Ganzzahl durch eine Zweierpotenz dividieren.
Bit-Twiddler
1
@ bit-twiddler Rechtsverschiebung funktioniert nicht wie Division für negative Zahlen.
Daemin
@Daemin: Du scheinst verdammt darauf bedacht zu sein, mir das Gegenteil zu beweisen. Zuerst werfen Sie das Rundungsproblem auf. Wenn ich diese Behauptung ablehne, indem ich sage, dass die Division in C und C ++ gegen Null abgeschnitten ist, werfen Sie das Problem mit den Ganzzahlen mit Vorzeichen aus. Wo habe ich gesagt, dass ich den Schichtoperator auf vorzeichenbehaftete negative Ganzzahlen mit zwei Komplementen anwende? Trotzdem kann man den Schichtoperator verwenden, um durch eine Zweierpotenz zu dividieren. Da jedoch C und C ++ anstelle einer einfachen alten Rechtsverschiebung eine arithmetische Rechtsverschiebung ausführen, muss zunächst geprüft werden, ob der Wert negativ ist. Wenn der Wert negativ ist,
Bit-Twiddler
1
Seien Sie vorsichtig, wenn Sie Shifting als Ersatz für Multiplikation und Division verwenden, da es subtile Unterschiede gibt. Nicht mehr und nicht weniger.
Daemin
3

Vor langer Zeit waren Bitoperatoren nützlich. Heute sind sie es weniger. Oh, sie sind nicht völlig nutzlos, aber es ist lange her, dass ich gesehen habe, dass eine verwendet wurde, die hätte verwendet werden sollen.

1977 war ich Assembler-Programmierer. Ich war überzeugt, dass Assembler die einzig wahre Sprache war. Ich war mir sicher, dass eine Sprache wie Pascal für akademische Neulinge gedacht war, die nie wirklich etwas erledigen mussten.

Dann las ich "The C Programming Language" von Kernighan und Ritchie. Es hat meine Meinung völlig geändert. Der Grund? Es hatte Bitoperatoren! Es war eine Assemblersprache! Es hatte nur eine andere Syntax.

Damals konnte ich mir nicht vorstellen, Code ohne Ands, Ors, Shifts und Rotates zu schreiben. Heutzutage benutze ich sie fast nie.

Die kurze Antwort auf Ihre Frage lautet also: "Nichts." Das ist aber nicht ganz fair. Die längere Antwort lautet also: "Meistens nichts."

Onkel Bob.
quelle
xkcd.com/378 fällt mir ein.
Maxpm
Bitoperatoren sind bis heute nützlich. Die Tatsache, dass sie in Ihrer Domain nicht verwendet werden, führt dazu, dass sie nicht oder nur sehr selten verwendet werden. Hier ist ein einfaches Beispiel: Versuchen Sie, AES ohne Bitoperatoren zu implementieren. Dies ist ein einfaches Beispiel für etwas, das auf den meisten Computern täglich hunderte oder tausende Male pro Tag ausgeführt wird.
NUR MEINE STELLUNGNAHME
Das Kodieren / Dekodieren von Daten ohne bitweise Operatoren ist bestenfalls schmerzhaft. Wenn wir einer Nachricht beispielsweise MIME-Anhänge hinzufügen, müssen wir in der Lage sein, drei bis vier Codierungen von Daten (auch bekannt als Radix64-Codierung) vorzunehmen.
Bit-Twiddler
2

Verschlüsselung

Ich schlage vor, einen sehr kleinen Ausschnitt aus dem DES-Verschlüsselungsalgorithmus zu betrachten :

temp = ((left >>> 1) ^ right) & 0x55555555; right ^= temp; left ^= (temp << 1);
temp = ((right >>> 8) ^ left) & 0x00ff00ff; left ^= temp; right ^= (temp << 8);
temp = ((right >>> 2) ^ left) & 0x33333333; left ^= temp; right ^= (temp << 2);
temp = ((left >>> 16) ^ right) & 0x0000ffff; right ^= temp; left ^= (temp << 16);
temp = ((left >>> 4) ^ right) & 0x0f0f0f0f; right ^= temp; left ^= (temp << 4);
Scott Whitlock
quelle
Obwohl nicht sicher, ob DES in diesen Tagen empfohlen wird: P
Armand
@Alison: Nein, aber die Verschlüsselungsalgorithmen, die es ersetzt haben, beinhalten meiner Meinung nach noch mehr Bitmanipulationsoperationen. :-)
Carson63000
@Alison - natürlich, aber TripleDES wird nur 3-mal mit 3-mal den Schlüsselbits des gemacht.
Scott Whitlock
2

Viele gute Antworten, daher werde ich diese Verwendungen nicht wiederholen.

Ich benutze sie ziemlich oft in verwaltetem Code (C # / .Net) und es hat nichts mit platzsparenden, leistungsstarken oder cleveren Bitverschiebungsalgorithmen zu tun. Manchmal ist eine Logik einfach gut geeignet, um Daten auf diese Weise zu speichern. Ich benutze sie oft, wenn ich eine Aufzählung habe, aber die Instanzen können gleichzeitig mehrere Werte aus dieser Aufzählung nehmen. Ich kann kein Beispiel für Code aus der Arbeit posten, aber eine schnelle Google-Suche nach "Flags enum" ("Flags" ist die C # -Methode zum Definieren einer bitweisen Enumeration) liefert dieses schöne Beispiel: http: // www.dotnetperls.com/enum-flags .

Steve
quelle
2

Es gibt auch bitparalleles Rechnen. Wenn Ihre Daten nur aus Einsen und Nullen bestehen, können Sie 64 davon in ein vorzeichenloses langes langes Wort packen und 64-Wege-Paralleloperationen durchführen. Genetische Informationen bestehen aus zwei Bits (die die AGCT-Codierung der DNA darstellen), und wenn Sie die verschiedenen Berechnungen bitparallel durchführen können, können Sie viel mehr tun, als wenn Sie dies nicht tun. Ganz zu schweigen von der Datendichte im Speicher - wenn der Speicher oder die Plattenkapazität oder die Kommunikationsbandbreite begrenzt sind, sollte eine Komprimierung / Dekomprimierung in Betracht gezogen werden. Selbst Ganzzahlen mit niedriger Genauigkeit, die in Bereichen wie der Bildverarbeitung auftreten, können die Vorteile der kniffligen bitparallelen Verarbeitung nutzen. Es ist eine ganze Kunst für sich.

Omega Centauri
quelle
1

Warum werden sie gefunden?

Nun, das liegt wahrscheinlich daran, dass sie Montageanleitungen entsprechen und manchmal nur für Dinge in höheren Sprachen nützlich sind. Gleiches gilt für die gefürchteten, GOTOdie der JMPMontageanleitung entsprechen .

Was sind ihre Verwendungen?

Wirklich, es gibt nur zu viele Verwendungszwecke, um sie zu benennen, also werde ich nur eine kürzliche, wenn auch stark lokalisierte, Verwendung geben. Ich arbeite viel mit 6502 Assembly und habe an einer kleinen Anwendung gearbeitet, die Speicheradressen, Werte, Vergleichswerte usw. in Codes konvertiert, die für das GameGenie-Gerät verwendet werden können (im Grunde genommen eine Cheat-Anwendung für das NES). Die Codes werden durch eine Bitmanipulation erzeugt.


quelle
1

Viele Programmierer sind heutzutage an Computer mit nahezu unbegrenztem Speicher gewöhnt.

Bei einigen Anwendungen werden jedoch immer noch winzige Mikrocontroller programmiert, bei denen jedes Bit zählt (wenn Sie beispielsweise nur über 1 KB RAM oder weniger verfügen), und die bitweisen Operatoren ermöglichen es einem Programmierer, diese Bits einzeln zu verwenden, anstatt viel größere Programme zu verschwenden Abstraktionsentität, die möglicherweise benötigt wird, um einen vom Algorithmus geforderten Zustand zu halten. Die E / A auf diesen Geräten müssen möglicherweise auch bitweise gelesen oder gesteuert werden.

Die "reale Welt" hat weitaus mehr dieser winzigen Mikrocontroller als Server oder PCs.

Bei reinen theoretischen CS-Typen dreht sich bei Turing-Maschinen alles um Zustandsbits.

hotpaw2
quelle
1

Nur eine von vielen Verwendungsmöglichkeiten der bitweisen Operatoren ...

Die bitweisen Operatoren können auch dazu beitragen, den Code besser lesbar zu machen. Beachten Sie die folgende Funktionsdeklaration ....

int  myFunc (bool, bool, bool, bool, bool, bool, bool, bool);

...

myFunc (false, true, false, false, false, true, true, false);

Es ist sehr leicht zu vergessen, welcher boolesche Parameter was bedeutet, wenn der Code geschrieben oder sogar gelesen wird. Es ist auch leicht, den Überblick über Ihre Zählung zu verlieren. Eine solche Routine kann aufgeräumt werden.

/* More descriptive names than MY_FLAGx would be better */
#define MY_FLAG1    0x0001
#define MY_FLAG2    0x0002
#define MY_FLAG3    0x0004
#define MY_FLAG4    0x0008
#define MY_FLAG5    0x0010
#define MY_FLAG6    0x0020
#define MY_FLAG7    0x0040
#define MY_FLAG8    0x0080

int  myFunc (unsigned myFlags);

...

myFunc (MY_FLAG2 | MY_FLAG6 | MY_FLAG7);

Mit aussagekräftigeren Flaggennamen wird es viel lesbarer.

Sparky
quelle
1

Wenn Sie etwas über Unicode wissen , sind Sie wahrscheinlich mit UTF-8 vertraut. Es verwendet eine Reihe von Bittests, Verschiebungen und Masken, um den 20-Bit-Codepunkt in 1 bis 4 Bytes zu packen.

MSalters
quelle
0

Ich benutze sie nicht oft, aber manchmal sind sie nützlich. Enum Handling mir ein.

Beispiel:

enum DrawBorder{None = 0, Left = 1, Top = 2, Right = 4, Bottom = 8}

DrawBorder drawBorder = DrawBorder.Left | DrawBorder.Right;//Draw right & left border
if(drawBorder & DrawBorder.Left == DrawBorder.Left)
  //Draw the left border
if(drawBorder & DrawBorder.Top == DrawBorder.Top)
  //Draw the top border
//...
Carra
quelle
0

Ich bin mir nicht sicher, ob diese Verwendung noch vermerkt wurde:

Ich sehe OR ziemlich oft, wenn ich mit dem illumos-Quellcode (openSolaris) arbeite, um mehrere Rückgabewerte auf 0 oder 1 zu reduzieren, z

int ret = 0;
ret |= some_function(arg, &arg2); // returns 0 or 1
ret |= some_other_function(arg, &arg2); // returns 0 or 1
return ret;
Awalias
quelle