Bitverarbeitung/Maske



  • Hallo, ich habe hier eine Aufgabe und verstehe die Lösung nicht! Wer kann helfen?

    Aufgabe: Erstellen Sie ein Programm, das nach Eingabe zweier Zahlen das Produkt ermittelt und ausgibt! Das Produkt soll über Bitverarbeitung (Verschieben und Addieren, siehe Vorlesung) ermittelt werden.

    Überall wo "???" stehen, verstehe ich nichts!

    Lösung: #include<iostream.h>
    unsigned int a, b, ergebnis;
    unsigned int maske = 0x80000; // ???
    char nochmal;
    int main()
    {do
    {
    cout<<"Bitte Zahl a eingeben : ";
    cin>>a;
    cout<<"Bitte Zahl b eingeben : ";
    cin>>b;
    ergebnis = 0; // ???
    while(maske)//maske !=0 // ???
    { ergebnis = ergebnis << 1; // um ein bit nach links verschieben
    if(maske & b) // ???
    ergebnis = ergebnis + a; // ???
    maske = maske >>1; // um ein bit nach rechts verschieben
    }
    cout<<a<<" mal "<<b<<" ergibt "<<ergebnis<<endl;
    cout<<"Programm wiederholen(j/n): ";
    cin>>nochmal;
    }
    while ((nochmal == 'j')||(nochmal == 'J'));
    }

    LG Simon und vielen DANK !!!



  • Wenn du die Bitoperatoren nicht verstehst, dann lies dir mal den Artikel zu http://de.wikipedia.org/wiki/Bitweiser_Operator durch.

    Oder verstehst du das Verfahren als solches nicht?



  • Ich weiß wie das Verfahren geht.

    Es geht mir um den Zusammenhang. Eigentlich um folgende Zeilen:

    { ergebnis = ergebnis << 1;
    if(maske & b)
    ergebnis = ergebnis + a;
    maske = maske >>1;
    }

    Wenig später gibt er das Ergebnis eines Produktes raus... Das verstehe ich nicht!



  • Maske wird am Anfang auf 0x8000 gesetzt (d.h. nur das höchstwertige Bit ist aktiv) und in jedem Schleifendurchlauf um 1 nach rechts geschoben. Also fragst du letztendlich (von "oben" kommend) ab, welche Bits in b gesetzt sind.

    (im letzten Schleifendurchlauf wird einzige gesetzte Bit von maske "raus"geschoben und 0 bleibt zurück - damit hast du dann die Abbruchbedingung)



  • Vielen Dank, das 0x8000 hat mir geholfen...

    if(maske & b)

    heißt das, dass diese Bedingung nur wahr wird, wenn das höchste Bit gleich ist?

    Wie kommt er auf das Produkt (a*b)? Der Zusammenhang ist mir völlig unklar!



  • Die Bedingung wird wahr, wenn irgendein Bit in maske UND b gesetzt ist. D.h. im ersten Durchlauf wird das höchstwertige Bit von b abgefragt, im nächsten Durchlauf das zweithöchste, etc - bis zum niedrigsten Bit.

    Und den Zusammenhang kannst du dir am schriftlichen Multiplizieren abgucken - du multiplizierst a nacheinander mit allen Ziffern von b und addierst diese Teilprodukte dann (passend verschoben) zum Gesamtergebnis. Nur ist hier der Unterschied, daß du nur zwei mögliche Ziffern hast: 0 und 1.



  • CStoll schrieb:

    Die Bedingung wird wahr, wenn irgendein Bit in maske UND b gesetzt ist. D.h. im ersten Durchlauf wird das höchstwertige Bit von b abgefragt, im nächsten Durchlauf das zweithöchste, etc - bis zum niedrigsten Bit.

    So habe ich es auch gemeint, nur schlecht ausgedrückt!
    Trotzdem fehlt mir der Zusammenhang, wie kommt man auf das Ergebnis?



  • Nehmen wir mal ein Beispiel, damit's verständlich wird:

    11010011 * 10011101 (211*157)

    Start: erg = 0, maske = 0x80 = 10000000

    Ester Durchlauf:
    erg<<=1 -> 0
    maske&b = 10000000 != 0 -> erg = 11010011
    maske>>=1 -> 01000000

    Zweiter Durchlauf:
    erg<<=1 -> 1 10100110
    maske&b = 0 -> nichts passiert
    maske>>=1 -> 00100000

    Dritter Durchlauf:
    erg<<=1 -> 11 01001100
    maske&b = 0 -> nichts passiert
    maske>>=1 -> 00010000

    Vierter Durchlauf:
    erg<<=1 -> 110 10011000
    maske&b = 000010000 != 0 -> erg+=a -> 111 01101011
    maske>>=1 -> 00001000

    etc.

    Wie gesagt - stell dir die schriftliche Multiplikation (solltest du in der Schule gelernt haben, oder?) vor und wende sie an auf das Binärsystem.



  • Vielen Dank, jetzt verstehe ich es....

    Eine Frage aber noch. Wenn ich z.B. 21*15 rechne benötige ich eine maske mit der Größe von 1000, da ja 15 in Bit "1111" lautet, wie wäre dazu die Bezeichnung hinter der Maske (0x...)?

    MFG Petrus und vielen DANK!



  • 0x08 - aber wenn du weiter oben anfängst, stört das auch nicht (außer daß du am Anfang der Schleife 12 0-Bits erfasst und verarbeitest). Btw, ich hab dort oben auch den ersten Teil der Schleife unterschlagen - bei deiner Funktion kämen am Anfang 8 Schleifendurchläufe, bis maske auf 0x8000 runtergezählt ist (da b dort oben keine Bits gesetzt wird, ändern die nichts am Ergebnis).



  • CStoll schrieb:

    0x08 - aber wenn du weiter oben anfängst, stört das auch nicht (außer daß du am Anfang der Schleife 12 0-Bits erfasst und verarbeitest). Btw, ich hab dort oben auch den ersten Teil der Schleife unterschlagen - bei deiner Funktion kämen am Anfang 8 Schleifendurchläufe, bis maske auf 0x8000 runtergezählt ist (da b dort oben keine Bits gesetzt wird, ändern die nichts am Ergebnis).

    Ja, dass es nichts am Ergebnis ändert ist mir jetzt klar! Wie kommt man auf 0x08?



  • Indem man die Binärzahl 1000 in einen Hex-Wert umrechnet - alternativ kannst du auch in dieser Tabelle nachschauen.



  • Vielen Dank!!!

    Gruß Petrus


Log in to reply