c++ löschen eines Bit aus Vektor

[Piak]

Servus,
habe einen std::vector<uint8> nun will ich z.b. exakt dass 37.te bit löschen, also eigentlich einfach alles was danach kommt um 1 shiften. Sodass sich dann auch alle "Zahlenwerte" der uint8-Elemente nach dem 37.ten bit ändern. Hat jemand ne Idee?

Bsp.
std::vector<uint8> dummy = {12,12,12,12} = 00001100 00001100 00001100 00001100
lösche 21.tes Bit
wird zu
00001100 00001100 00001000 00011000 = {12,12, 8, 24}

Sollte doch eigentlich effizient zu bewerkstelligen sein, da die Elemente im Vector doch eh geschlossen hintereinander abliegen.

Am besten ist natürlich ein Codebeispiel, aber auch ne Idee wie das klappt.

 

[TopperHarley87]

Das Zauberwort heißt hier: "Bitmasken"

Ein Bit in einer Variablen löschen würde z.B. so aussehen:

x &= ~(1<<9); // clear Bit 9

Für mehr Details könnte das weiterhelfen:
https://www.mikrocontroller.net/articles/Bitmanipulation

 

[Piak]

Danke für den Link, den kenn ich.

Aber was ich suche ist nicht ein Bit zu 0 setzen, sondern vor allem den ganzen Rest nachschieben und mehr oder weniger diese Position löschen. Wie in meinem Beispiel, sollen sich auch die Zahlen danach verändern.

 

[Poati]

Haben deine Vektoren denn immer 4 Elemente? Ansonsten ist die Grundidee doch genau richtig. Du kannst dann für den dritten Vektor &-Verknüpfen mit 11110111 müsste es sein und dann fällt da das Bit mit der 0 raus. Bei den restlichen bleibt alles was vorher 1 war erhalten.
Danach für die restlichen Elemente left shits um 1. Bildet zumindest genau dein Beispiel ab. Sonst erkläre nochmal genauer, was passieren soll.

 

[Piak]

@Poati : Das was du beschreibst passt schon. Du meinst das dritte Element. Mein Vektor wird zusammen gebastelt und hat verschiedene Größe.
Eigentlich will ich an exakt 255255 dieselben 255255 Bit in Kopie anhängen. Gespeichert werden diese aber in 31907 Byte, sodass also das letzte Bit von den 8*31907= 255256 bereits durch dass erste Bit des zweiten Abschnitts überschrieben werden soll.
Lösen würde mein Dilemma eigentlich erstmal wenn ich zu nem Bitset umsteige, dummerweise sind da die Zugriffe wesentlich langsamer. Also unterm Strich kein Gewinn.

 

[KingLz]

Hier ein bisschen Pseudocode wie man das Problem lösen kann.
Hab ich nicht getestet, kann also Fehler enthalten.
Ich gehe hier von unsigned, also keine Vorzeichen aus. Also Bitgröße der Variablen gehe ich auch von 8 Bit aus. Ansonsten muss man es anpassen. Das soll auch erstmal nur so eine grobe Idee sein wie es geht.
Evtl. kannst du auf deinem Vector einen Typecast anwenden, so dass du dann statt uint8 ihn in uint64 Blöcken bearbeitest. Größere Blöcke als deine Architectur wird von HW Ebene aber nicht gehen und wenn C++ es dir anbietet dann baut dir der Compiler auch nur irgendetwas was so ähnlich wie das hier sein wird.

v = 00001100
bit_pos = 4
# wir wollen die erste 1 löschen, also Position 4

bitmask = (~0 >> bit_pos  ) << bit_pos
# ~0 ist 11111111, mit den rechts links shifts erzeugen wir am rechten Ende 4 Nullen => 11110000

result = v & bitmask
# Wir lassen alles links neben der bit_pos stehen => result = 00000000

v = (v << 1) & ~bitmask
# wir shiften v nach links (00011000) und löschen dann alle bits die in result bisher stehengeblieben sind (deswegen inverse von bitmask) => 00001000

result = result | v
# den hinteren Teil (v) in result wieder einfügen

last_bit = 1
result = result | last_bit
# wir müssen das letzte Bit noch setzen, welches vom hinteren Eintrag reingeschoben wird.

# result = 00001001


#### Für alle nachfolgenden Bytes:

byte = byte <<1 | (byte_davor >> 7)
#ich gehe davon aus, dass bei shift rechts 0 reingeschoben wird und nicht 1, da musst du mal schauen

 

[Poati]

Eigentlich will ich an exakt 255255 dieselben 255255 Bit in Kopie anhängen.

Damit machst du dir das Leben ein bisschen schwer. Wieso ist es notwendig, dass Bit 255256 schon wieder die Kopie ist? Kannst du da den Zugriff nicht ändern? Also wenns eh eine Kopie der vorherigen Bits ist, was spricht dagegen auf die selbe Adresse ein zweites Mal zuzugreifen?

Ansonsten bleibt es bei dem Maskieren und Rumgeshifte. Nur mit Bitmasken kannst du einzelne Bits in C++ manipulieren.

 

[Iqra]

Was ist denn da der Usecase, mal abgesehen von einer Hausaufgabe?

Für mich liest sich das nicht ganz eindeutig. Es geht anscheinend nicht darum, Bit an der Stelle k auf 0 zu setzen, sondern buchstäblich das n-bit Wort zu einem (n-1) Bit Wort zu machen ab Stelle k, richtig?

Ich würde ja insbesondere für einen Vektor die Bitarithmetik weglassen wollen und "normale" integerarithmetik verwenden, aber das ist sicherlich auch dem Umstand geschuldet daß der klare Usecase fehlt. Die ist zwar mehr "hacky" aber definitiv nicht performanter.

Je weniger Einzelbits man angucken muß desto besser ist das, also wäre mein Ansatz, erst eine passende Maske zu bestimmen und dann in einem Rutsch das Eingabebitfeld in ein Ausgabebitfeld zu überführen. Wobei sich es mir ehrlich sträubt einen Vektor als einen Skalar zu behandeln. Aber okay.

Zur Sicherheit, wenn ich nicht völlig belämmert bin dann ist Bit 21 nicht ganz da wo du es verortest, da Bitfelder von "hinten" adressiert werden (per MSB zumindest):

00001100 00001100 00001100 00001100
31..24   23..16   15..8    76543210

sodaß Bit 21 sich hier befindet

00001100 00X01100 00001100 00001100

und wenn man es buchstäblich aus der Bitfolge rauswirft

0000:0110 0000:1100 0000:1100 0000:1100

eher die Werte vorne sich ändern als die hinten. Wenn das nicht so gewünscht ist, dann ist evtl die Aufgabenstellung nicht klar genug bestimmt und eine Rückfrage beim Auftraggeber evtl angezeigt.

Denn offensichtlich ändert das einen doch nicht insignifikanten Teil der Implementierung.

 

[Piak]

@Poati: Es geht darum teuren L2 zu sparen, in dem ein Presieve (das Bitfeld) mehrfach aneinander gehängt wird. Statt komplett im Speicher vorzuhalten. Später soll dann auf der Kopie davon gearbeitet werden.

@Iqra: Danke für deine Ausführung. Es geht sicherlich nicht um eine Hausaufgabe und auch kein Studium inhalt. Ein rein privates Projekt, wo aber schon mehrere 100h Arbeit reingeflossen sind.

Es geht um eine auf Performance getrimmte implementierte Version von einem segmentierten Wheel Sieve von Eratothenes mit einem Presieve von kleinen Primzahlen. 3*5*7*11*13*17 = 255255.

Heißt es wird konkret ein Bitfeld im Speicher vorgehalten, wo bereits ein paar Vielfache gestrichen sind, dies dient dann als Vorlage für jeweils ein Segment (auch ein Bitfeld). Beides muss in den L2 passen. Sofern also mein Presieve schön klein, (und dann auseinander gefaltet/kopiert wird) bleibt mehr Platz für das Segment selbst, bedeutet dann weniger Wiederholungen und dann mehr Performance.

 

[Poati]

Also wenn wir uns auf der Flughöhe befinden, dann kannst du das Maximum wahrscheinlich nur mit Assembler Code rausholen. Das ist bei mit aber noch länger her als C, daher kann ich da nicht viel helfen. Die Länge deiner Segmente bleibt aber auch da unvorteilhaft, wenn du unbedingt das eine "leere" Bit zwischen den Segmenten raus haben möchtest.

 

[striker159]

Wenn man sowieso einen vector von bits haben möchte, wie wäre es dann mit vector<bool>?

#include <vector>
int main(){
    std::vector<bool> bitvector(1024);
    bitvector.erase(bitvector.begin() + 37);
}

 

[nullPtr]

Von hinten her loopen und die uint8 immer um 1 nach links shiften, das raugeschobene Bit des vorherigen Wortes noch einfügen. Mitzählen, wieviele Bits du schon besucht hast. Beim Byte, in dem du löschen willst: Ebenso schieben, finales Byte zusammensetzen aus "ungeschoben & Maske_links" | "geschoben & Maske_rechts".
Das ist eine Art von Problemen, die durch die Abstraktion von Programmiersprachen leider schwerer wird. In Assembly ginge das einfacher, da in den meisten ISAs eine Instruktion für "rotiere über Carry" hat; genau das, was man eigentlich bräuchte.

Das gesagt: Gibt eine Möglichkeit, das Bit, das du entfernen willst, von vorne herein gar nicht mit aufzunehmen? Also: Wie wird dein Bitvektor erzeugt und was für eine Semantik hat er?