3-bit Zahl effizient mit Bitmaske in Byte einfügen?
Gegeben ist eine 3-bit große Zahl (0 - 7) und eine Bitmaske der Form 11100000. Ich möchte nun gerne die Zahl in ein Byte einfügen, in dem sich bereits andere Daten befinden (die erhalten bleiben sollen). Die Bitmaske soll angeben, wo die Zahl eingefügt werden soll (dort werden die Daten dann natürlich überschrieben).
Mein bisheriger Ansatz ist es, das Byte mit der invertierten Bitmaske bitweise mit UND zu verknüpfen, um die alten Daten der oberen 3 bits zu löschen, und danach das Byte mit der um 5 nach links geshifteten Zahl mit ODER zu verknüpfen.
Für mich klingt das aber recht ineffizient. Neben 4 Logikoperationen muss ich mir zusätzlich noch den Verschiebungsvektor der Shift-Operation merken, obwohl dieser sich letztlich aus der Bitmaske ergibt.
Hat jemand eine bessere Idee?
2 Antworten
Du meinst:
data &= ~mask
data |= (bits<<pos) & mask
sei ineffizient? So ticken aber handelsübliche Prozessoren. Statt Unmengen von Spezialbefehlen anzubieten, punkten sie mit rasanter Ausführung ihres überschaubaren Befehlssatzes.
Brauchst Du es noch schneller, musst Du einen Prozessor mit nativen Bitoperationen kaufen (oder bauen) und eine Programmiersprache wählen, die das unterstützt.
Redundanz mag ich auch nicht. Aber wenn's um Performance geht, hilft es eben, einmalige Berechnungen vorab zu erledigen. Ich sehe hier sogar drei eng zusammenhängende Werte: mask, ~mask und shift; und eventuell noch ein viertes width=3. Ich würde sie in dieser Reihenfolge definieren:
shift = 5
width = 3
mask = ( (1<<width)-1) << shift
nmask = ~mask
Falls aber nur mask gegeben ist und shift und width berechnen werden sollen, geht das auch ohne Schleife:
shift = (mask ^ (mask-1)).bit_length() - 1
width = mask.bit_length() - shift
Für Übungen im Grundkurs Informatik würde ich das aber nicht empfehlen :-)
Ich verstehe, was ...
shift = (mask ^ (mask-1)).bit_length() - 1
... bewirken soll, aber leider finde ich die Funktion .bit_length() oder eine vergleichbare nicht in den Arduino-Standard-Bibliotheken. Werde also eher auf eine Lösung wie in deinem ersten Ansatz übergehen. Muss mal eine Nacht drüber schlafen.
Vielen Dank auf jeden Fall. Hat mir sehr weitergeholfen.
int.bit_length() gibt es erst seit Python 3.3.
In Python 2 bleibt Dir im Einzeiler für shift wohl nur math.log().
Ein Grund mehr, auf 3 zu wechseln.
Ähm, ich habe nie behauptet, dass ich in Python programmieren würde. Ich programmiere einen AVR-Mikrocontroller über die Arduino-Plattform.
Ups! Keine Ahnung, wie ich auf Python kam... In C könnte es so gehen:
int const shift = ilogb( mask ^ (mask-1) );
Sofern mask eine Konstante ist, sollte das beim Kompilieren berechnet werden. Andernfalls wäre das ohne FPU ziemlich teuer.
Der erste Weg mit gegebenem shift und width geht natürlich genauso in C .
Hm, leider scheint die relevante Bibliothek unter der Arduino-IDE nicht verfügbar zu sein. Ich werde wohl doch auf die redundante Variante ausweichen.
würde erst Byte mit 1110 0000 UND verknüpfen. Dadurch wird der Teil wo die 111 hin soll auf 0 gesetzt.
Dann verschiebste die 111 ( Schieberegister ) auf die Position wo sie hin soll.
Nun machste Oder Verknüpfung sprich 1110 0000 mit 0001 1100
Wenn ich das Byte mit 11100000 UND-verknüpfe, dann lösche ich doch gerade die 5 unteren Bits, die ich erhalten möchte, oder sehe ich da was falsch?
Noch einmal zur Verdeutlichung an einem Beispiel:
Byte (Beispiel): [101]11011
Zahl (Beispiel): [110]
Bitmaske: [111]00000
Ergebnis: [110]11011
Danke für die Rückmeldung. Ich wollte nur sicher gehen, dass ich am Ende nicht eine viel einfachere Methode übersehe.
Was mich noch ein wenig stört, ist wie gesagt, dass ich mit mask und pos zwei Werte habe, die im Prinzip redundant sind. Wenn ich das eine verändere, muss ich gleichzeitig auch immer daran denken, das andere zu verändern.
Mir fiele jetzt spontan nur eine Funktion ein, die mit einer Schleife prüft, an welcher Stelle die erste 1 in mask steht.
Bevor ich aber eine solche Funktion durchlaufen lasse, speichere ich wohl lieber das zusätzliche, redundante Byte ab. Oder gibt es hier irgendwelche einfachen binären Operationen, mit denen ich das herausfinden kann?