Wie gut muss ein gut gerundeter Programmierer mit bitweisen Operationen umgehen können? [geschlossen]

Ich habe einige OpenJDK Code kürzlich gegrast und haben einige gefunden interessanten Teile des Codes gibt , die mit dem zu tun hat bitweise Operationen . Ich habe sogar eine Frage dazu auf StackOverflow gestellt.

Ein weiteres Beispiel, das den Punkt veranschaulicht:

 1141       public static int bitCount(int i) {
 1142           // HD, Figure 5-2
 1143           i = i - ((i >>> 1) & 0x55555555);
 1144           i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
 1145           i = (i + (i >>> 4)) & 0x0f0f0f0f;
 1146           i = i + (i >>> 8);
 1147           i = i + (i >>> 16);
 1148           return i & 0x3f;
 1149       }

Dieser Code befindet sich in der Integer- Klasse.

Ich kann nicht anders, als mich dumm zu fühlen, wenn ich mir das ansehe. Habe ich ein oder zwei Stunden auf dem College verpasst oder soll ich das nicht einfach bekommen ? Ich kann einfache bitweise Operationen ausführen (wie UND-Verknüpfung, ODER-Verknüpfung, XOR-Verknüpfung, Verschiebung), aber wie kommt jemand auf einen Code wie diesen?

Wie gut muss ein gut gerundeter Programmierer mit bitweisen Operationen umgehen können?

Nebenbei bemerkt ... Was mich beunruhigt, ist, dass die Person, die meine Frage zu StackOverflow beantwortet hat, diese in wenigen Minuten beantwortet hat. Wenn er das könnte, warum starrte ich dann nur wie ein Reh in die Scheinwerfer?

Ich würde sagen, dass Sie als runder Entwickler die Operatoren und bitweisen Operationen verstehen müssen .

Zumindest sollten Sie also in der Lage sein, den obigen Code nach einigem Überlegen herauszufinden.

Bitweise Vorgänge sind in der Regel auf einem relativ niedrigen Niveau. Wenn Sie also an Websites und LOB-Software arbeiten, ist es unwahrscheinlich, dass Sie diese häufig verwenden.

Wie bei anderen Dingen, wenn Sie sie nicht oft benutzen, sind Sie nicht mit ihnen vertraut.

Sie sollten sich also keine Sorgen machen, dass jemand es sehr schnell herausfindet, da er (wahrscheinlich) viel mit dieser Art von Code arbeitet. Schreiben Sie möglicherweise OS-Code, Treibercode oder andere knifflige Manipulationen.

Wenn Sie verstehen, wie Sie Probleme wie "Bestimmen, ob die Bits 3 und 8 gesetzt sind", "Löschen von Bit 5" oder "Ermitteln des durch die Bits 7-12 dargestellten Ganzzahlwerts" lösen, haben Sie genug Verständnis für bitweise Operatoren, um die Can zu überprüfen Twiddle Bits- Kästchen auf der Checkliste "Gut gerundet".

Was in Ihrem Beispiel enthalten ist, stammt von Hacker's Delight , einer Zusammenstellung von Hochleistungsalgorithmen zur Bearbeitung kleiner Datenmengen wie Ganzzahlen. Wer diesen Code ursprünglich geschrieben hat, hat ihn nicht innerhalb von fünf Minuten ausgespuckt. Die Geschichte dahinter ist wahrscheinlicher, dass es einer schnellen, verzweigungsfreien Methode zum Zählen von Bits bedurfte und der Autor etwas Zeit hatte, um auf Bitketten zu starren und einen Weg zu finden, um das Problem zu lösen. Niemand wird verstehen, wie es auf einen Blick funktioniert, wenn er es nicht schon einmal gesehen hat. Mit einem soliden Verständnis der bitweisen Grundlagen und einiger Zeit, die Sie mit dem Code verbracht haben, könnten Sie wahrscheinlich herausfinden, wie er das tut, was er tut.

Auch wenn Sie diese Algorithmen nicht verstehen, trägt die Tatsache, dass sie existieren, zu Ihrer "Rundung" bei, dass Sie wissen, was Sie zu studieren haben, wenn es beispielsweise um das Hochleistungszählen von Bits geht. In der Welt vor Google war es viel schwieriger, diese Dinge herauszufinden. Jetzt ist es Tastenanschläge entfernt.

Der Benutzer, der Ihre SO-Frage beantwortet hat, hat das Problem möglicherweise schon einmal gesehen oder Hashing studiert. Schreiben Sie ihm und fragen Sie.

Von Ihrem Beispiel gibt es einige Dinge, die Sie unbedingt wissen sollten, ohne wirklich darüber nachzudenken.

1143 i = i - ((i >>> 1) & 0x55555555);

Sie sollten das Bitmuster 0x555 ... als abwechselndes Bitmuster 0101 0101 0101 erkennen und dass die Operatoren es um 1 Bit (nach rechts) versetzen und dass & eine Maskierungsoperation ist (und was Maskierung bedeutet).

1144 i = (i & amp; 0x33333333) + ((i >>> 2) & amp; 0x33333333);

Wieder ein Muster, dieses ist 0011 0011 0011. Auch, dass es diesmal zwei verschiebt und wieder maskiert. Die Verschiebung und Maskierung erfolgt nach einem Muster, das Sie erkennen sollten ...

1145 i = (i + (i >>> 4)) & 0x0f0f0f0f;

das Muster verfestigt sich. Diesmal ist es 00001111 00001111 und natürlich verschieben wir es dieses Mal um 4. Jedes Mal verschieben wir uns um die Größe der Maske.

1148 return i & 0x3f;

Ein weiteres Bitmuster, 3f, ist ein Block von Nullen, gefolgt von einem größeren Block von Einsen.

All diese Dinge sollten auf einen Blick ersichtlich sein, wenn Sie "gut gerundet" sind. Auch wenn Sie nicht glauben, dass Sie es jemals verwenden werden, werden Sie wahrscheinlich einige Gelegenheiten verpassen, Ihren Code erheblich zu vereinfachen, wenn Sie dies nicht wissen.

Selbst in einer höheren Sprache werden Bitmuster verwendet, um VIEL größere Datenmengen in kleineren Feldern zu speichern. Aus diesem Grund gibt es in Spielen immer Limits von 127/8, 63/4 und 255/6. Das liegt daran, dass Sie so viele dieser Dinge speichern müssen, dass Sie, ohne die Felder zu packen, das Zehnfache des Werts verwenden müssen Speichermenge. (Nun, das Ultimative wäre, wenn Sie eine große Anzahl von Booleschen Werten in einem Array speichern müssten. Sie könnten das 32- bis 64-fache der Speicherkapazität sparen, die Sie benötigen würden, wenn Sie nicht darüber nachdenken würden. Die meisten Sprachen implementieren Boolesche Werte als Ein Wort, das oft 32 Bit lang ist. Wer sich auf dieser Ebene nicht wohl fühlt, kann solche Daten nicht speichern, nur weil er Angst vor dem Unbekannten hat.

Sie scheuen auch Dinge wie das manuelle Analysieren von Paketen, die über das Netzwerk in einem gepackten Format übermittelt werden - etwas, das trivial ist, wenn Sie keine Angst haben. Dies kann dazu führen, dass ein Spiel, für das ein 1k-Paket erforderlich ist, weniger als 200 Bytes benötigt. Das kleinere Paket wird effizienter durch das Netzwerk gleiten, die Latenz verringern und höhere Interaktionsgeschwindigkeiten ermöglichen (was möglicherweise ganz neue Spielmodi für ein Spiel ermöglicht).

Ich habe den Code zufällig erkannt, weil ich ihn zuvor in einer Software zur Bearbeitung von Videoframes gesehen habe. Wenn Sie regelmäßig mit Audio- und Video-CODECs, Netzwerkprotokollen oder Chip-Registern arbeiten, sehen Sie viele bitweise Operationen, und das wird für Sie zur zweiten Natur.

Sie sollten sich nicht schlecht fühlen, wenn Ihre Arbeit nicht sehr oft mit diesen Bereichen zusammenfällt. Ich kenne mich mit bitweisen Operationen gut aus, aber ich verlangsame mich in den seltenen Fällen, in denen ich eine GUI schreiben muss, aufgrund all der Macken mit Layouts und Gewichtung und Erweiterung und der Tatsache, dass ich mir sicher bin, dass dies eine Selbstverständlichkeit für andere ist. Ihre Stärken sind dort, wo Sie die meiste Erfahrung haben.

Sie sollten sich vor allem darüber im Klaren sein, wie Ganzzahlen dargestellt werden (im Allgemeinen ein Bitvektor mit fester Länge, bei dem die Länge plattformabhängig ist) und welche Operationen auf ihnen verfügbar sind

Die wichtigsten arithmetischen Operationen + - * / %können verstanden werden, ohne dass man sie verstehen muss, obwohl es für Mikrooptimierungen nützlich sein kann (obwohl der Compiler die meiste Zeit in der Lage ist, dies für Sie zu erledigen).

Die Bitmanipulationsmenge | & ~ ^ << >> >>>erfordert mindestens ein vorübergehendes Verständnis, um sie verwenden zu können

Meistens werden Sie sie jedoch nur verwenden, um Bit-Flags an eine Methode zu übergeben, ORindem Sie ein int zusammenführen und dann ANDdie Einstellungen ausgeben. Dies ist besser lesbar, als mehrere (bis zu 32) Boolesche Werte in einer langen Parameterliste zu übergeben und zuzulassen Die möglichen Flags können geändert werden, ohne die Schnittstelle zu ändern

Ganz zu schweigen davon, dass Boolesche Werte in der Regel separat in Bytes oder Ints gespeichert werden, anstatt sie wie die Flags zusammen zu packen

Beim Code-Snippet werden die Bits parallel gezählt, wodurch der Algorithmus ausgeführt werden kann. O(log(n))Dabei ist n die Anzahl der Bits anstelle der naiven SchleifeO(n)

Der erste Schritt ist am schwersten zu verstehen, aber wenn Sie mit dem Setup beginnen, müssen Sie die Bitsequenzen 0b00nach 0b00, 0b01nach 0b01, 0b10nach 0b01und 0b11nach ersetzen , damit 0b10Sie leichter folgen können

i - ((i >>> 1) & 0x55555555)Wenn wir also für den ersten Schritt annehmen i, dass wir gleich sind, sollte 0b00_01_10_11die Ausgabe davon sein0b00_01_01_10

(Beachten Sie, dass 0x5gleich ist 0b0101)

iuf wir nehmen i = 0b00_01_10_11das heißt das 0b00_01_01_10 - (0b00_00_11_01 & 0b01_01_01_01)ist 0b00_01_10_11 - 0b00_00_01_01was wiederum wird0b00_01_01_10

Sie hätten (i & 0x55555555) + ((i >>> 1) & 0x55555555)das gleiche Ergebnis erzielen können, dies ist jedoch eine zusätzliche Operation

Die folgenden Schritte sind ähnlich

Jeder sollte grundlegende bitweise Operationen verstehen. Es ist die Zusammensetzung der Grundoperationen, um Aufgaben auf eine optimierte, robuste Art und Weise auszuführen, die viel Übung erfordert.

Diejenigen, die jeden Tag mit Bit-Manipulation arbeiten (wie eingebettete Leute), werden natürlich eine starke Intuition und eine schöne Menge Tricks entwickeln.

Wie viel Geschick sollte ein Programmierer haben, der keine einfachen Dinge mit bitweiser Manipulation macht? Genug, um sich mit einer Strophe, wie Sie sie eingefügt haben, an einen Tisch zu setzen und sie langsam durchzuarbeiten, als wäre es ein Rätsel.

Aus dem gleichen Grund würde ich sagen, dass ein Embedded-Programmierer so viel über http verstehen sollte wie ein Web-Entwickler über bitweise Manipulationen. Mit anderen Worten, es ist in Ordnung, bei Bit-Manipulationen nicht zu schlau zu sein, wenn Sie sie nicht die ganze Zeit verwenden.

Die Freude von Hacker ist eine abgeleitete Arbeit. Der Vorfahr von allem ist HakMem von 1972. http://w3.pppl.gov/~Hammett/work/2009/AIM-239-ocr.pdf

Wichtig ist zu wissen, dass der offensichtliche Algorithmus für jede Aufgabe nicht unbedingt der beste ist. Es gibt viele Fälle, in denen es wichtig ist, die Existenz einer eleganten Lösung für ein bestimmtes Problem zu kennen.

Wie schwer sind bitweise Operatoren zu interpretieren?

Ich programmiere eingebettete Systeme. Ich habe dieses Zeug viel geübt. Ihre verknüpfte Frage zu Hash-Maps mit dem Code

static int hash(int h) {
   // This function ensures that hashCodes that differ only by
   // constant multiples at each bit position have a bounded
   // number of collisions (approximately 8 at default load factor).
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

machte für mich in etwa so lange Sinn, wie es dauern würde, den Code laut zu diktieren. Die in beschriebenen Ereignisse bitCountsind sofort klar, aber es dauert eine Minute, um herauszufinden, warum es tatsächlich Bits zählt. Kommentare wären jedoch großartig und würden das Verständnis dessen, was der Code tut, nur geringfügig erschweren als das Hash-Problem.

Es ist wichtig, zwischen dem Lesen und dem Verstehen des Codes zu unterscheiden. Ich kann den bitCountCode interpretieren und ablesen, was er tut, aber nachweisen, warum er funktioniert oder sogar, dass er funktioniert, würde eine Minute dauern. Es gibt einen Unterschied zwischen dem reibungslosen Lesen von Code und dem Erkennen, warum der Code so ist, wie er ist. Einige Algorithmen sind einfach schwer. Das Was des hashCodes ergab einen Sinn, aber der Kommentar erklärte, warum das, was getan wurde. Lassen Sie sich nicht entmutigen, wenn eine Funktion mit bitweisen Operatoren schwer zu verstehen ist. Oft werden sie verwendet, um schwierige mathematische Aufgaben auszuführen, die unabhängig vom Format schwierig sind.

Eine Analogie

Ich bin an dieses Zeug gewöhnt. Ein Thema, an das ich nicht gewöhnt bin, ist Regex. Ich setze mich gelegentlich mit ihnen in Build-Skripten auseinander, aber niemals in der täglichen Entwicklungsarbeit.

Ich kann die folgenden Elemente eines regulären Ausdrucks verwenden:

• [] Zeichenklassen
• Der *, .und +Platzhalter
• Der Anfang der Zeichenfolge ^und das Ende der Zeichenfolge$
• Die Zeichenklassen \ d, \ w und \ s
• Das Flag / g

Dies reicht aus, um einfache Abfragen zu erstellen, und viele der Abfragen, die ich sehe, weichen nicht weit davon ab.

Alles, was nicht auf dieser Liste steht, greife ich nach einem Spickzettel. Alles, außer {}und ()- Der Spickzettel wird nicht ausreichen. Ich weiß gerade genug über diese Typen, um zu wissen, dass ich ein Whiteboard, ein Referenzhandbuch und vielleicht einen Kollegen brauchen werde. Sie können einige verrückte Algorithmen in ein paar kurze Zeilen Regex packen.

Um einen regulären Ausdruck zu entwerfen, der alles erfordert oder vorschlägt, was nicht in meiner Liste der bekannten Elemente enthalten ist, liste ich alle Klassen von Eingaben auf, die ich zu erkennen erwarte, und füge sie einer Testsuite hinzu. Ich werde den regulären Ausdruck langsam und schrittweise mit vielen intermittierenden Schritten erstellen und diese Schritte der Quellcodeverwaltung zuweisen und / oder sie in einem Kommentar hinterlassen, damit ich nachvollziehen kann, was später passieren sollte, wenn es kaputt geht. Wenn es sich um Seriencode handelt, stelle ich sicher, dass er von jemandem mit mehr Erfahrung überprüft wird.

Arbeiten Sie hier mit bitweisen Operatoren?

Du willst also gut gerundet sein?

Wenn Sie in der Lage sind, den Code wie folgt zu interpretieren, indem Sie ein Blatt Papier herausziehen oder zum Whiteboard gehen und die Vorgänge manuell ausführen, werden Sie als gut gerundet eingestuft. Um sich im Bereich der bitweisen Operationen als ein guter, abgerundeter Programmierer zu qualifizieren, sollten Sie in der Lage sein, vier Dinge zu tun:

1. Gemeinsame Operationen flüssig lesen und schreiben können
   Für einen Anwendungsprogrammierer umfassen gemeinsame Operationen mit bitweisen Operatoren die Grundoperatoren von |und &zum Setzen und Löschen von Flags. Das sollte einfach sein. Sie sollten in der Lage sein, Dinge wie zu lesen und zu schreiben

   open('file', O_WRONLY | O_APPEND | O_CREAT );
   // Use an OR operator ^ here and ^ here to set multiple flags
   

   ohne langsamer zu werden (vorausgesetzt, Sie wissen, was die Flags bedeuten ).

2. Sie können komplexere Operationen mit einigem
   Aufwand lesen. Zählen Sie Bits sehr schnell in O (log (n)) - Zeit ohne Verzweigungen. Stellen Sie dabei sicher, dass sich die Anzahl der Kollisionen in hashCodes um einen begrenzten Betrag unterscheidet, und analysieren Sie E-Mail-Adressen , Telefonnummern oder HTML mit einem regulären Ausdruck sind schwierige Probleme. Es ist für jeden vernünftig, der in diesen Bereichen kein Experte ist, nach dem Whiteboard zu greifen. Es ist unvernünftig, nicht in der Lage zu sein, mit dem Verstehen zu beginnen.

3. In der Lage sein, einige komplexe Algorithmen mit viel Arbeit zu schreiben
   Wenn Sie kein Experte sind, sollten Sie nicht erwarten, komplexe und schwierige Aufgaben ausführen zu können. Ein guter Programmierer sollte es jedoch schaffen, indem er kontinuierlich daran arbeitet. Tu das genug, und du wirst bald ein Experte sein :)

Wenn Sie eine anständige Universität besucht haben, sollten Sie einen Kurs in Diskreter Mathematik belegen müssen. Sie hätten binäre, oktale und hexadezimale arithmetische und logische Gatter gelernt.

In diesem Sinne ist es normal, dass ich mich verwirrt fühle. Wenn es Sie tröstet, da ich hauptsächlich Webanwendungen schreibe, muss ich selten Code wie diesen betrachten oder schreiben, aber da ich binäre Arithmetik und das Verhalten der bitweisen Operatoren verstehe Ich kann irgendwann herausfinden, was hier vor sich geht, wenn ich genug Zeit habe.

Als Programmierer von Mobiltelefonen musste ich mich mit so etwas auseinandersetzen. Es ist durchaus üblich, dass das Gerät nicht über viel Arbeitsspeicher verfügt oder dass die Übertragungsgeschwindigkeit wichtig ist. In beiden Fällen versuchen Sie, so viele Informationen wie möglich in ein paar Bytes zu packen.

Ich kann mich nicht erinnern, dass ich in den letzten 5 Jahren bei PHP (vielleicht bin es nur ich) bitweise Operatoren verwendet habe, in den letzten 10 Jahren bei der Windows-Programmierung nicht mehr, obwohl bei einigen Windows-Inhalten auf niedrigerer Ebene ein paar Bits gepackt wurden.

Sie sagen: "Ich kann nicht anders, als mich dumm zu fühlen, wenn ich mir das ansehe." NICHT - sich ärgern.

Sie haben gerade die Ausgabe eines Cowboy-Programmierers kennengelernt.

Weiß er nichts von wartbarem Code? Ich hoffe aufrichtig, dass er derjenige ist, der in einem Jahr darauf zurückkommen und versuchen muss, sich daran zu erinnern, was es bedeutet.

Ich weiß nicht, ob Sie Kommentare ausschneiden oder ob es keine gibt, aber dieser Code hat die Codeüberprüfung nicht bestanden, wenn ich ein s / w-QA-Manager war (und ich war schon einige Male).

Hier ist eine gute Faustregel: Die einzigen "nackten ganzen Zahlen", die im Code zulässig sind, sind 0 bis 1. Alle anderen Zahlen sollten je nach Sprache #defines, costs, enums usw. sein.

Wenn diese 3 und 0x33333333 so etwas wie NUM_WIDGET_SHIFT_BITS und WIDGET_READ_MASK gesagt hätten, wäre der Code leichter zu lesen gewesen.

Schade, wen das in einem Open-Source-Projekt herausbringt, aber auch für persönlichen Code gut kommentiert und aussagekräftige Defines / Enums verwendet und eigene Codierungsstandards hat.

Dieser spezielle Code stammt direkt aus dem Buch Hacker's Delight , Abbildung 5.2. Es ist online in C (die Pop-Funktion) hier . Beachten Sie, dass der Autor jetzt die Verwendung aktualisierter Versionen empfiehlt: http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt

Wenn Sie diese Art von Mikrooptimierungen lernen möchten, würde ich dieses Buch vorschlagen. Es macht Spaß, aber wenn Sie nicht oft Bit-Programmierung auf sehr niedrigem Niveau ausführen, werden Sie es wahrscheinlich nicht verstehen. und die meiste Zeit wird Ihr Compiler in der Lage sein, viele dieser Optimierungen für Sie durchzuführen.

Es ist auch hilfreich, alle Hexadezimalzahlen in Binärschrift umzuschreiben, um diese Art von Algorithmen zu verstehen und sie in einem oder zwei Testfällen durchzuarbeiten.

Erklärung am Beispiel. Daten sind Folgen von Bits. Zählen wir die Bits im Byte 01001101 mit den folgenden verfügbaren Operationen: 1. Wir können den Wert des letzten Bits überprüfen. 2. Wir können die Reihenfolge verschieben.

1. 01001101 -> letztes Byte ist 1, gesamt = 1. Verschiebungen
2. 10100110 -> letztes Byte ist 0, gesamt = 1. Verschiebungen
3. 01010011 -> Letztes Byte ist 1, gesamt = 2. Verschiebungen
4. 10101001 -> letztes Byte ist 1, gesamt = 3. Verschiebungen
5. 11010100 -> Letztes Byte ist 0, gesamt = 3. Verschiebungen
6. 01101010 -> letztes Byte ist 0, gesamt = 3. Verschiebungen
7. 00110101 -> letztes Byte ist 1, gesamt = 4. Verschiebungen
8. 10011010 -> letztes Byte ist 0, gesamt = 4. Verschiebungen

Unsere Antwort: 4.

Das war nicht schwer, oder? Die große Sache mit bitweisen Operationen ist, dass wir nur begrenzte Dinge tun können. Wir können nicht ein bisschen direkt zugreifen. Aber wir können zum Beispiel den Wert des letzten Bits kennen, der mit MASK 00000001 verglichen wird, und wir können jedes Bit zum letzten Bit mit Verschiebeoperationen machen. Natürlich wird der resultierende Algorithmus für diejenigen, die es nicht gewohnt sind, beängstigend aussehen. Nichts mit Intelligenz zu tun.

Ich würde nicht sagen, dass Sie es brauchen, es sei denn, die Arbeit, die Sie tun, bezieht sich auf:

• Audioverarbeitung
• Videoverarbeitung
• Grafik
• Netzwerk (besonders wenn die Paketgröße wichtig ist)
• Riesige Datenmengen

Das Speichern von Berechtigungen in Unix-Style-Flags ist auch eine weitere Verwendung, wenn Sie ein besonders komplexes Berechtigungsmodell für Ihr System haben oder auf Kosten der Lesbarkeit wirklich alles in ein einziges Byte packen möchten.

Abgesehen von diesen Bereichen würde ich es als großes Plus betrachten, wenn ein Entwickler / Senior-Entwickler Bitverschiebung demonstrieren und | verwenden könnte & und ^, da es ein Interesse an dem Beruf zeigt, von dem man sagen könnte, dass es zu einem stabileren und zuverlässigeren Code führt.

Soweit Sie die Methode nicht auf den ersten Blick „verstehen“, benötigen Sie, wie bereits erwähnt, eine Erklärung der Funktionsweise und einige Hintergrundinformationen. Ich würde nicht sagen, dass es mit Intelligenz zusammenhängt, aber wie vertraut Sie damit sind, tagtäglich mit Hexadezimalzahlen zu arbeiten und Probleme zu erkennen, die bestimmte Muster lösen können.