Mussten Sie jemals Bit Shifting in realen Projekten verwenden?

83

Mussten Sie jemals Bit-Shifting in echten Programmierprojekten verwenden? Die meisten (wenn nicht alle) Hochsprachen enthalten Schichtoperatoren, aber wann müssten Sie sie tatsächlich verwenden?

Philip Morton
quelle

Antworten:

58

Ich schreibe immer noch Code für Systeme, die keine Gleitkomma-Unterstützung in der Hardware haben. In diesen Systemen müssen Sie für fast alle Ihre Arithmetik Bitverschiebungen durchführen.

Außerdem benötigen Sie Verschiebungen, um Hashes zu generieren. Polynomarithmetik (CRC, Reed-Solomon-Codes sind die Hauptanwendungen) oder verwendet auch Verschiebungen.

Schichten werden jedoch nur verwendet, weil sie praktisch sind und genau das ausdrücken, was der Autor beabsichtigt hat. Sie können alle Bitverschiebungen mit Multiplikation emulieren, wenn Sie möchten, aber das wäre schwieriger zu schreiben, weniger lesbar und manchmal langsamer.

Die Compiler erkennen Fälle, in denen die Multiplikation auf eine Verschiebung reduziert werden kann.

Nils Pipenbrinck
quelle
37

Ja, ich habe sie oft benutzt. Bit-Twiddling ist bei eingebetteter Hardware wichtig, bei der Bit-Masken sehr häufig sind. Dies ist auch bei der Programmierung von Spielen wichtig, wenn Sie die letzte Leistung benötigen.

Bearbeiten: Außerdem verwende ich sie häufig zum Bearbeiten von Bitmaps, zum Beispiel zum Ändern der Farbtiefe oder zum Konvertieren von RGB <-> BGR.

MrZebra
quelle
Abgeordnet. Ich mache viel Embedded-Programmierung, und Bitverschiebung ist eine häufige Operation.
e.James
RGB <-> BGR-Konvertierungen hier.
Neil N
25
  • Erstellen netter Flag-Werte für die Aufzählungen (anstatt manuell 1, 2, 4 ... einzugeben ...)
  • Entpacken der Daten aus den Bitfeldern (viele Netzwerkprotokolle verwenden sie)
  • Durchquerung der Z-Kurve
  • Performance-Hacks

Und ich kann mir nicht viele Fälle vorstellen, in denen sie verwendet werden. Es ist normalerweise umgekehrt - es gibt ein spezifisches Problem, und es stellt sich heraus, dass die Verwendung von Bitoperationen die besten Ergebnisse liefert (normalerweise in Bezug auf Leistung - Zeit und / oder Raum).

Anonym
quelle
Möglicherweise müssen Sie beispielsweise zwei shorts in einem intEger-Feld im Sitzungsstatus in ASP.net speichern, ohne die Sitzung auslesen und sperren zu müssen, um zwei separate Werte zu lesen. Außerdem wird der Speicheraufwand für das Speichern von zwei Werten in der Sitzung gespeichert.
David d C e Freitas
15

Ein Ort, an dem ich sie ständig benutze, ist die Transponierung der Endianz von Ganzzahlen für plattformübergreifende Anwendungen. Sie sind manchmal auch nützlich (zusammen mit anderen Bitmanipulationsoperatoren), wenn 2D-Grafiken gemischt werden.

MattK
quelle
Abgeordnet, Schreiben eines Konverters für den EBCDIC-Zeichensatz. Leider erledigt dies wirklich Low-Level-Arbeit in einer High-Level-Sprache, aber es ist in einigen Fällen notwendig.
Michael Meadows
9

Ich habe sie ein paar Mal verwendet, aber so ziemlich immer zum Parsen eines binären Dateiformats.

David Grant
quelle
7

Bitverschiebungen sind schnell. Sie wurden in CPU-Befehlssätzen implementiert, lange bevor Divisions- und Moduloperationen durchgeführt wurden. Viele von uns haben Bitverschiebungen für die Arithmetik verwendet, die auf Bleistift und Papier einfach ist, aber auf unseren CPUs nicht verfügbar ist.

Beispielsweise:

  • Ich habe Bitverschiebungen für Projekte verwendet, bei denen große Verbundwerkstoffe in ihre Hauptfaktoren einbezogen wurden.
  • Ich habe auch Bitverschiebungen verwendet, um die Quadrat- und Kubikwurzel von beliebig großen ganzen Zahlen zu finden.
elf81
quelle
Kannst du bitte ein Beispiel posten, wie du damit den Würfel oder die Quadratwurzel findest? Ich sehe ein bisschen nicht, wie das gemacht werden kann.
Xsmael
5

Ja, es wird immer noch benötigt.

Hier in meinem Job entwickeln wir zum Beispiel Software für die Kommunikation mit der SPS über die serielle Schnittstelle COMx. Es ist notwendig, Bits innerhalb eines Bytes zu behandeln. Wir verwenden Tag für Tag die Verschiebung nach links / rechts und die Logikoperatoren OR, XOR UND.

Nehmen wir zum Beispiel an, wir müssen das Bit 3 (von rechts nach links) eines Bytes einschalten:

Es ist viel effizienter zu tun:

Byte B;

B := B XOR 4;

Anstatt:

Byte B = 0;
String s;  // 0 based index

s = ConvertToBinary (B);
s[5] = "1";
B := ConvertToDecimal (s);

Grüße.

Carlos Eduardo Olivieri
quelle
1
Vielleicht möchten Sie hinzufügen, warum 4 sich auf Bit 3 bezieht (von rechts nach links)
HCP
1
Warum s [5]? Sollte es nicht S [2] sein?
IamIC
1
B: = B XOR 4; Sollte es in diesem Fall nicht nur ODER sein, um ein bestimmtes Bit einzuschalten? Wird XOR nicht zum Umschalten verwendet? stackoverflow.com/questions/47981/…
Hari
4

Als ich in Assemblersprache schrieb, war mein Code voller Bitverschiebungen und Maskierungen.

Hat es auch in C eine ganze Menge geklappt?

Ich habe nicht viel in JavaScript oder Serversprachen gemacht.

Die wahrscheinlich beste moderne Verwendung besteht darin, ein gepacktes Array von Booleschen Werten zu durchlaufen, die als Einsen und Nullen dargestellt werden. Früher habe ich in der Assembly immer die linke Schicht verschoben und nach Vorzeichen gesucht, aber in höheren Sprachen vergleicht man sie mit einem Wert.

Wenn Sie beispielsweise 8 Bits haben, überprüfen Sie das oberste Bit mit "if (a> 127) {...}". Dann haben Sie die Verschiebung verlassen (oder mit 2 multipliziert), ein "und" mit 127 ausgeführt (oder eine Subtraktion von 256 durchgeführt, wenn das letzte Bit gesetzt wurde) und erneut ausgeführt.

Nosredna
quelle
3

Ich habe sie häufig bei der Bildkomprimierung / -dekomprimierung verwendet, bei der die Bits in einer Bitmap komprimiert wurden. Wenn Sie http://en.wikipedia.org/wiki/Huffman_coding verwenden, bestehen die zu komprimierenden Elemente aus einer unterschiedlichen Anzahl von Bits (sie sind nicht alle byte-ausgerichtet). Daher müssen Sie sie beim Codieren oder Decodieren bitverschieben .

ChrisW
quelle
3

Zum Beispiel bei der Implementierung kryptografischer Methoden in Sprachen wie C, C ++. Binärdateien, Komprimierungsalgorithmen und logische Listenoperationen - bitweise Operation ist immer gut =)

Anton
quelle
3

Bitverschiebung löst keine Programmierprobleme auf hoher Ebene, aber manchmal müssen wir Probleme auf niedrigerer Ebene lösen, und es ist praktisch, keine separate Bibliothek in C schreiben zu müssen, um dies zu tun. Das ist, wenn es am meisten verwendet wird, ist meine Vermutung.

Ich habe es persönlich verwendet, um einen Encoder für einen EBCDIC- Zeichensatzkonverter zu schreiben .

Michael Meadows
quelle
3

Ja, habe ich. Wie Sie vielleicht vermuten, ist dies am wahrscheinlichsten in der Programmierung auf niedriger Ebene zu finden, beispielsweise bei der Entwicklung von Gerätetreibern. Ich arbeitete jedoch an einem C # -Projekt, bei dem ich einen Webdienst entwickeln musste, der Daten von medizinischen Geräten erhielt. Alle vom Gerät gespeicherten Binärdaten wurden in SOAP-Pakete codiert, die Binärdaten wurden jedoch komprimiert und codiert. Um es zu dekomprimieren, müssten Sie viele, viele Bitmanipulationen durchführen. Außerdem müssten Sie viele Bitverschiebungen durchführen, um nützliche Informationen zu analysieren. Beispielsweise ist die Seriennummer des Geräts eine niedrigere Hälfte des zweiten Bytes oder ähnliches. Außerdem habe ich einige Leute in der .NET (C #) -Welt gesehen, die Bitmaskierung und Flag-Attribute verwenden. Ich persönlich hatte nie den Drang, dies zu tun.

WebMatrix
quelle
3

ja. Ich muss vorher Verschlüsselungsalgorithmen schreiben und das nutzt sie definitiv.

Sie sind auch nützlich, wenn Sie Ganzzahlen usw. verwenden, um den Status zu verfolgen.

Kevin
quelle
3

Beim Konvertieren von Zahlen vom Little-Endian-Format in das Big-Endian-Format und umgekehrt

Ludwig Wensauer
quelle
3

Ich arbeite für einen Hersteller von Computerperipheriegeräten. Ich bin auf Code gestoßen und musste ihn implementieren, der Bitverschiebungen verwendet, fast jeden Tag.

Wechselmodus
quelle
3

Bitverschiebung wird häufig zum Entschlüsseln der Protokolle von Online-Spielen verwendet. Die Protokolle sind so konzipiert, dass sie so wenig Bandbreite wie möglich verwenden. Anstatt die Anzahl der Spieler auf einem Server, Namen usw. in int32s zu übertragen, werden alle Informationen in so wenige Bytes wie möglich gepackt. Heutzutage ist es bei den meisten Menschen, die Breitband verwenden, nicht wirklich notwendig, aber als sie ursprünglich entwickelt wurden, verwendeten die Leute 56k-Modems für Spiele, also zählte jedes Bit.

Die bekanntesten Beispiele hierfür sind Valves Multiplayer-Spiele, insbesondere Counter-Strike, Counter-Strike Source. Das Quake3-Protokoll ist ebenfalls dasselbe, jedoch ist Unreal nicht ganz so schlank.

Hier ist ein Beispiel (.NET 1.1)

string data = Encoding.Default.GetString(receive);

if ( data != "" )
{
    // If first byte is 254 then we have multiple packets
    if ( (byte) data[0] == 254 )
    {
        // High order contains count, low order index
        packetCount = ((byte) data[8]) & 15; // indexed from 0
        packetIndex = ((byte) data[8]) >> 4;
        packetCount -= 1;

        packets[packetIndex] = data.Remove(0,9);
    }
    else
    {
        packets[0] = data;

    }
}

Natürlich liegt es an Ihnen, ob Sie dies als echtes Projekt oder nur als Hobby (in C #) betrachten.

Chris S.
quelle
2

Schnelle Fourier-Transformation - FFT und seine Cooley-Tukey-Technik erfordern Bitverschiebungsoperationen.

LicenseQ
quelle
Rollen Sie Ihre eigenen FFT-Routinen? tut-tut :) Ich gebe zu, ich habe es auch selbst gemacht - großartig, um den Algorithmus tief zu verstehen.
Marty
2

Finden Sie die nächste Potenz von zwei größer oder gleich der angegebenen Zahl:

1 << (int)(ceil(log2(given)))

Wird für die Texturierung auf Hardware benötigt, die keine beliebigen Texturgrößen unterstützt.

Zoul
quelle
1

Ja, sie wurden im MPEG2-2 Transport Stream Parser verwendet. Es war einfacher und besser lesbar.

RvdK
quelle
1

Ich musste ein Programm schreiben, um die .ifo-Dateien auf DVDs zu analysieren. Dies sind die Dateien, die erklären, wie viele Titel, Kapitel, Menüs usw. sich auf der Disc befinden. Sie bestehen aus gepackten Bits aller Größen und Ausrichtungen. Ich vermute, dass viele Binärformate eine ähnliche Bitverschiebung erfordern.

Steve Rowe
quelle
1

Ich habe bitweise Operatoren gesehen, die verwendet wurden, wenn mehrere Flags als Eigenschaftsparameter verwendet wurden. Zum Beispiel bedeutet Nummer 4 = 1 0 0, dass eines der drei Flags gesetzt ist. Dies ist nicht gut für die öffentliche API, kann jedoch in besonderen Fällen die Dinge beschleunigen, da die Überprüfung auf Bits schnell ist.

Lycha
quelle
1

Jedes Bitblt-er, das ich jemals geschrieben habe, konnte nicht abgeschlossen werden, ohne dass die Bits nach links und rechts verschoben werden konnten.

Scott Evernden
quelle
1

Ich habe sie in Spielen verwendet, um ein paar Flags in ein einzelnes Byte / Zeichen zu packen und auf einer Datenkarte zu speichern. Dinge wie das Speichern des Status von freischaltbaren Objekten usw. Heutzutage nicht mehr so ​​wichtig, können aber Arbeit sparen.

xan
quelle
1

Ich verwende es in einem Projekt für ein eingebettetes System, das die EDID-Daten eines Monitors lesen muss. Einige Daten in einer EDID werden wie folgt codiert:

Byte 3:
Horizontales Ausblenden - untere 8 Bit
Byte 4:
Unteres Nibble: Horizontales Ausblenden - obere 4 Bit
Oberes Nibble: etwas anderes
Tobias Klüpfel
quelle
1

Ja, wenn Sie eine binäre Kommunikation zwischen Java- und C # -Anwendungen durchführen, ist eine Big-Endian-Bytereihenfolge und die andere Little-Endian-Bytereihenfolge (nicht unbedingt in dieser Reihenfolge). Ich habe eine InputStream-Klasse erstellt, die Zahlen mit einer anderen Bytereihenfolge lesen kann, und sie hat Byte-Shifting verwendet, um zu funktionieren.

Manchmal, auch wenn Sie 4 Kurzschlüsse in die 4 Bytes eines Longs einfügen möchten, ist die Verwendung von Byte-Shifting der Fall. Ich glaube, das habe ich vor vielen Jahren getan ...

Ravi Wallau
quelle
1

Eine andere sehr häufige Sache ist, eine 4-Bit-Verschiebung durchzuführen, wenn das hohe Halbbyte eines Bytes extrahiert wird , d. H.

#define HIGH_NIBBLE(byte) (((byte) >> 4) & 0x0F)
#define LOW_NIBBLE(byte)  ( (byte)       & 0x0F)
hlovdal
quelle
Dies gilt insbesondere dann, wenn Sie direkt mit Hardware arbeiten und Daten direkt aus Registern mit beliebigen Bitzuordnungen abrufen.
Chris
0

Eine Bitverschiebung ist auch erforderlich, wenn mit Geräten mit "niedrigerer Ebene", digitalen Ethernet-E / A-Boxen oder SPS kommuniziert wird, die normalerweise einzelne Eingabe- / Ausgabewerte in Bytes packen.

Harriv
quelle
0

Ja, die ganze Zeit. Wie diese Makros zum Packen und Entpacken einer 3-Raum-Koordinate in / aus einer 32-Bit-Ganzzahl:

#define Top_Code(a, b, c)           ((((a) + x) << 20) | (((b) + y) << 10) | ((c) + z))                           
#define From_Top_Code(a, b, c, f)   (a = (((f) >>> 20) - x), b = ((((f) & 0xffc00) >>> 10) - y), c = (((f) & 0x3ff) - z))        
Chaos
quelle