Teilwort extrahieren



  • Hi Leute!

    Die unten gezeigt Funktion zeigt meinen Versuch ein Teilwort aus einem Bitvector zu extrahieren. Leider funktioniert das so nicht, wie es soll. Ich komme da aber jetzt schon seit Tagen nicht mehr weiter. Die Datenhaltung im Vektor sieht so aus:

    Man setzt z.B. diesen BitVector:

    0000000101100000
     ^              ^
     |              |
    MSB            LSB
    

    Dann sieht das im char-Array so aus:

    |01100000|00000001|
         ^        ^
         |        |
    Element 1  Element 2
    

    Wie kann ich nun auf einfachsten Weg ab einer bestimmten Position 'pos' eine gewisse Länge 'n' an Bits aus dem "großen" BitVector extrahieren und in ein neues Array kopieren?

    Ich schaff's einfach nicht. Könnt ihr mir helfen?

    PS: Das Problem ist irgendwie die Datenhaltung des arrays. Ich weiß nicht recht von welcher Richtung aus, ich die Position, also 'pos' sehen soll. Irgendwie ist das alles ziemlich doof.

    Mein bisheriger Versucht sieht so aus:

    struct bitvector
    {
    	unsigned char *bits;		//deklaration der Membervariable
    };
    
    struct bitvector *createBitVector(struct bitvector *bv, unsigned int anzahl)
    {
    	int var;
    
    	if(anzahl%8 != 0)
    	{
    		var = (anzahl / 8) + 1;
    	}
    	else
    	{
    		var = anzahl / 8;
    	}
    
    	bv->bits = new unsigned char[var];
    
    	for(int i=0; i<var; i=i+1)		//Array wird standardmäßig auf 0 gesetzt!
    	{
    		bv->bits[i] = 0;
    	}
    
    return bv;
    }
    
    struct bitvector *getSlice(struct bitvector *bv, unsigned int anzahl, unsigned int pos, unsigned int n)
    {
    	bitvector maske;
    
    	createBitVector(&maske, n);
    
    	pos = pos + 1;		//(pos+1) ist die konvertierung zurück von Index nach "richtiger" Stelle
    
    	bv->bits[pos/8] = bv->bits[pos/8] >> (pos - n);
    	//maske.bits[i/8] = maske.bits[i/8] | (bv->bits[i/8] & (1 >> i%8));
    
    	cout << "verschoben: ";
    	printBitVector(bv, anzahl);
    
    	for(unsigned int i=0; i<n; i=i+1)
    	{
    		maske.bits[i/8] |= (bv->bits[i/8] & (1 << i%8));
    		//maske.bits[i/8] = bv->bits[(pos+(i-(pos+n+1)))/8] | ~(maske.bits[(pos+(i-(pos+n+1)))/8]);
    	}
    
    	cout << "extrahierte Bits: ";
    	printBitVector(&maske, n);
    
    return bv;
    }
    

  • Mod

    Ist das für dich selbst zum Programmieren lernen oder gibt es einen anderen vernünftigen Grund, warum du nicht so Sachen wie std::bitset oder std:vector benutzt?



  • Nein, wir sollen diese C++ Konstrukte (noch) nicht verwenden. Wir sollen eben bitset usw selbst implementieren. Deswegen der Code.



  • Damit ich von der etwas dummen Speicherhaltung im array wegkomme, hab ich noch eine for-Schleife eingebaut, die mir die Elemente des Arrays umkopiert.

    struct bitvector *getSlice(struct bitvector *bv, unsigned int anzahl, unsigned int pos, unsigned int n)
    {
    	bitvector maske, bv_neu;
    	char tmp_char;
    	int var;
    
    	createBitVector(&bv_neu, anzahl);
    
    	if(anzahl%8 != 0)
    	{
    		var = (anzahl / 8) + 1;
    	}
    	else
    	{
    		var = anzahl / 8;
    	}
    
    	for(unsigned int i=0; i<2; i=i+1)		//umkopieren
    	{
    		tmp_char = bv->bits[i];
    		bv_neu.bits[var-i-1] = tmp_char;
    	}
    
    	pos = pos + 1;		//(pos+1) ist die konvertierung zurück von Index nach "richtiger" Stelle
    
    	createBitVector(&maske, n);
    
    	//bv->bits[pos/8] = bv->bits[pos/8] >> (pos - n);
    	//maske.bits[i/8] = maske.bits[i/8] | (bv->bits[i/8] & (1 >> i%8));
    
    	for(unsigned int i=0; i<n; i=i+1)
    	{
    		maske.bits[i/8] = maske.bits[i/8] | (bv_neu->bits[pos-i/8] & (1 << i%8));
    		//maske.bits[i/8] = bv->bits[(pos+(i-(pos+n+1)))/8] | ~(maske.bits[(pos+(i-(pos+n+1)))/8]);
    	}
    
    	cout << "extrahierte Bits: ";
    	printBitVector(&maske, n);
    
    return bv;
    }
    

    Nach dem umkopieren steht der BitVector nun so im array:

    MSB             LSB
      |               |
     |00000001|01100000|
         ^        ^
         |        |
    Element 0  Element 1
    

    Jetzt hab ich aber weiterhin noch das Problem, dass ich nicht weiß wie ich das Teilwort extrahieren soll. Ich denke mal eine Schleife wäre von Vorteil :-). Position kann man ja jetzt von rechts nach links gesehen angeben.



  • Ich hab nochmal weiter gearbeitet:

    struct bitvector *getSlice(struct bitvector *bv, unsigned int anzahl, unsigned int pos, unsigned int n)
    {
    	bitvector maske, bv_neu;
    	char tmp_char;
    	int var;
    
    	createBitVector(&bv_neu, anzahl);
    
    	if(anzahl%8 != 0)
    	{
    		var = (anzahl / 8) + 1;
    	}
    	else
    	{
    		var = anzahl / 8;
    	}
    
    	for(unsigned int i=0; i<2; i=i+1)		//umkopieren
    	{
    		tmp_char = bv->bits[i];
    		bv_neu.bits[var-i-1] = tmp_char;
    	}
    
    	pos = pos + 1;		//(pos+1) ist die konvertierung zurück von Index nach "richtiger" Stelle
    
    	createBitVector(&maske, n);
    
    	//bv->bits[pos/8] = bv->bits[pos/8] >> (pos - n);
    	//maske.bits[i/8] = maske.bits[i/8] | (bv->bits[i/8] & (1 >> i%8));
    	//maske.bits[i/8] = bv->bits[(pos+(i-(pos+n+1)))/8] | ~(maske.bits[(pos+(i-(pos+n+1)))/8]);
    
    	for(unsigned int i=0; i<n; i=i+1)
    	{
    		if(((pos-i) % 8) != 0)
    		{
    			if((pos-i) > 8)
    			{
    				var = (pos / 8) - 1;
    			}
    		}
    		else
    		{
    			var =  var + 1;
    		}
    
    		maske.bits[i/8] = maske.bits[i/8] | (bv_neu.bits[var] & (1 << var%8));
    	}
    
    	cout << "extrahierte Bits: ";
    	printBitVector(&maske, n);
    
    return bv;
    }
    

    Wenn ich die Funktion jetzt mit der Position 9 und mit der Länge 4 durchlaufen lasse, dann gibt er mir bei diesem BitVector

    MSB             LSB
      |               |
     |00000001|01100000|
         ^        ^
         |        |
    Element 0  Element 1
    

    0001 aus.

    Ausgeben sollte er aber: 1011.

    Ich weiß nicht wo der Fehler ist. Kann mir jemand helfen?


Log in to reply