+1 Daumen
3,5k Aufrufe

Aufgabe Bitmanipulation:

Schreiben Sie ein Programm, welches eine unsigned int Variable einliest und

1. die Anzahl der vorkommenden Einsen im Bitmuster zählt und ausgibt

2. die Reihenfolge der Bits umkehrt und den entstehenden Zahlenwert in einer neuen unsigned int Variable speichert

3. beide Zahlen im Hexadezimalformat auf den Bildschirm ausgibt

Verwenden Sie zur Lösung der Aufgaben Bitoperationen. Nicht erlaubt sind die mathematische Bibliothek, sowie Felder/Vektoren/Strings/Dateien o. ä.

Berücksichtigen Sie, dass die Lange des unsigned int Datentyps von der gegebenen Rechnerhardware abhängig ist. Ihr Programm soll plattformunabhängig sein, also sowohl auf 16 Bit, 32 Bit oder 64 Bit Architekturen laufen (Verwendung des sizeof-Operators). Der Algorithmus ist durch die Verwendung von Bitoperationen (z.B. &, |, >> usw.) zu realisieren.
Fur die Eingabe der Zahl soll zusätzlich gelten:

• Bei der Eingabe soll die Zahl zunächst als double-Wert eingelesen werden, und anschließend eine Überprüfung stattfinden, ob die eingegebene Zahl – eine ganze Zahl ist – als unsigned int darstellbar ist.
• Für den Benutzer sollen sehr große Zahlenwerte mithilfe des Zweierkomplements durch Eingabe eines negativen integer Wertes möglich sein, d.h. durch Eingabe von z.B. -5 soll die funftgrößte unsigned int Zahl gemeint sein

Geeignete Testfälle zur Überprüfung Ihres Programmes:

-5, 3000000000 (3 Milliarden), 5000000000 (5 Milliarden), -4.5 <<


Mein Ansatz:

#include <iostream>

using namespace std;

int main() {

  double z;
  unsigned int = 0;
  int eins=0;
  int null=0;
  int einerstelle;
 
  z=(sizeof(int*8));
 
  cout << "Geben Sie eine Zahl ein: " << endl;
  cin >> z;
 
for(int i;i>=1;i--) {
 
    einerstelle = z & 1;
    if(einerstelle) {
          eins++;
    } else null++;
    z = z >> 1;
 
  return 0;
}


Pseudocode:

count =0
inverse = 0

cin >> zahl

for (int i=0; i<sizeof(int)*8;i++)
{
inverse <<= 1
inverse += zahl & 1
zahl >>=1
count++
}
Avatar von

2 Antworten

+4 Daumen

Im ersten Schritt solltest Du versuchen, Dein Programm compilierfähig zu machen. Dein Code oben ist nur ein Fragment aus Codeschnipseln. Folgende Dinge sind da essentiell:

1. jede Variable hat einen Typ und einen Namen und sollte zum Zeitpunkt der Deklaration auch initialisiert werden

unsigned int = 0;  // ist falsch hier fehlt der Name

unsigned int zahl = 0; // korrekt eine Variable mit Typ 'unsigned int' und Namen 'zahl' wird mit 0 initialisiert

2. auf jede geöffnete Klammer '{' muss eine schließende '}' folgen. Gewöhne Dir an, den Code entsprechend zu formatieren, d.h. rücke die Zeile nach jeder geöffneten Klammer ein. Also z.B. so:

for( int i=8*sizeof(unsigned int); i>0; --i )  // auch hier muss 'i' initialisiert werden
{ // offenen Klammer
    if( .... )
    { // offen
          // mehr Code noch mehr eingerückt
    } // geschlossen
} // geschlossen Klammer

Wenn Du den Code kompilierst und Du erhältst Fehler, so entferne sie und den stelle den Code erst vor, wenn der Compiler keinen Fehler mehr liefert. Wenn Du Schwierigkeiten hast, gehe in kleinen Schritten vor. Schreibe erst wenige Zeilen, kompiliere sie und erst wenn dies fehlerfrei ist, dann füge weiter Zeilen hinzu.

Aber bevor Du dies machst, prüfe erst mit dem Debugger oder einer Ausgabe, ob der Code auch das macht, was Du denkst.

3.) Zerlege das Problem in kleine Stücke (Funktionen) und packe jede Funktionalität in eine eigen Funktion (bzw. später Klasse)


zum ersten Problem: "... die Anzahl der vorkommenden Einsen im Bitmuster zählt und ausgibt " könnte so aussehen:

int zaehle_1erBits( unsigned int x )
{
    int anzahl = 0;
    // solange x!=0 ist, sind noch 1'en in x enthalten
    for( ; x != 0; x >>= 1 )  // mit jedem Durchlauf werden alle Bits nach links verschoben
    {
        if( x & 1 ) // tritt eine 1 im Bit0 auf, so wird sie gezaehlt
            ++anzahl;
    }
    return anzahl;
}

Im Unterschied zu Deinem Code läuft die Schleife nicht über alle Bits von unsigned int, sondern bricht ab, sobald die Variable 'x' zu 0 wird. Denn dann sind keine Einsen mehr enthalten. Und wenn Du so eine kleine Funktion fertig hast, so teste sie ausführlich:

int main()
{
    using namespace std;
    for( unsigned int zahl; cin >> zahl; )
    {
        cout << "Die Anzahl der 1'en in " << zahl << " ist " << zaehle_1erBits( zahl ) << endl;
    }
    return 0;
}

Erst wenn das gut funktioniert (gebe auch eine 0 oder eine negative Zahl ein), dann gehe zum nächsten Problem

"... die Reihenfolge der Bits umkehrt und den entstehenden Zahlenwert in einer neuen unsigned int Variable speichert"

Überlege, was genau zu tun ist. Sicher musst Du in einer Schleife über alle Bits laufen und jedes Bit an die entgegen gesetzte Stelle des Ergebnisses wieder eingefügt werden. Beginne mit einer Funktion und einer Schleife

unsigned reverse_Bits( unsigned int x )
{
    for( int i = 0; i < 8*sizeof(unsigned int); ++i )
    {
        std::cout << i << std::endl; // nur zur Kontrolle der Schleife
    }

    return 0;
}


.. und bevor es weiter geht, prüfe die Schleife mit dem Debugger oder einer Ausgabe wie oben, ob sie auch das tut, was Du denkst. In diesem Fall sollten die Zahlen von 0 bis 31 ausgegeben werden (bei üblicher 32Bit Architektur). Im nächsten Schritt prüfe ob an der betreffende Stelle eine 1 in 'x' steht.

unsigned reverse_Bits( unsigned int x )
{
    for( int i = 0; i < 8*sizeof(unsigned int); ++i, x >>= 1 ) // x bei jeden Schritt nach rechts shiften
    {
        int bit = x & 1; // durch das Shiften steht das Bit mit Index 'i' jetzt an Position 0
        std::cout << "Bit " << i << " = " << bit << std::endl;
    }
    return 0;
}

Rufst Du die Funktion mit 23 auf, so sollte die Ausgabe der ersten Bits dann so aussehen:

Bit 0 = 1
Bit 1 = 1
Bit 2 = 1
Bit 3 = 0
Bit 4 = 1
Bit 5 = 0

da \(23 = 2^0 + 2^1 + 2^2 + 2^4 = 1 +2 + 4 + 16\) ist. Alle weiteren Bits sollten =0 sein.

Erst jetzt das Ergebnis zusammen bauen:

unsigned int reverse_Bits( unsigned int x )
{
    unsigned int ergebnis = 0;
    for( int i = 0; i < 8*sizeof(unsigned int); ++i, x >>= 1 )
    {
        ergebnis <<= 1;
        int bit = x & 1;
        if( bit != 0 )
        {
            ergebnis |= 1;
        }
        std::cout << "Bit " << i << " = " << bit << "  Ergebnis = 0x" << std::hex << ergebnis << std::dec << std::endl;
    }
    return ergebnis;
}

Die Ausgabe (von 'ergebnis') erfolgt im Hexadezimalformat und ist daher besser zu kontrollieren. So jetzt versuche es bitte mal allein. Wenn Du Fragen hast (wirst Du haben!), dann melde Dich einfach.

Gruß Werner

Avatar von

Hallo user18697,

das kannst Du machen wie Du möchtest. Umso mehr Erfahrung Du hast, desto mehr schreibst Du in eine Zeile oder einen Ausdruck. Anfänger neigen dazu, alles einzeln hinzu schreiben, das ist auf jeden Fall einfacher zu debuggen.

Und z und zahl bedeuten doch das gleiche , also sollte es doch beides z oder zahl heißen.

Benenne gleiche Dinge gleich und unterschiedliche unterschiedlich. Hört sich trivial an, ist aber in der Praxis gar nicht so einfach!

Benenne die Variable, die die Zahl speichert, mit 'zahl' - das ist "sprechend" und so weißt Du, was in der Variablen steht.

mit z ist also auch die Variable 'zahl' gemeint?

Ja - natürlich: und es ist verwunderlich, dass DU mich das fragst. Ich hatte die Variablenbezeichnung von dir übernommen - nach dem Motto: benenne gleich Dinge mit dem gleichem Namen. Du hast die Zahl selbst zunächst mit \(\text{z}\) und später mit \(\text{zahl}\) bezeichnet (s. Deine Frage oben).

0 Daumen

Als Bitweise und if würde ich nicht zusammen bringen wollen.

Grobplan (ich hab Java nicht gelernt: die 1 durchschieben und aufsammeln was nach den verunden stehen bleibt) etwa 

t=1

while(t>0) {

  Zähler+=Prüfzahl & t

  t < 1

}

Avatar von

Das habe ich ja schon im Ansatz.

Es geht aber eher darum, die Zahl einzugeben und dann ohne zu überladen die Zahl der Einsen des Bitmusters der Zahl zu zählen und beide Zahlen im Hexdezimal auszugeben.


Dabei ist noch die Frage, wie ich diese unsigned int einbaue(muss size of verwenden glaub ich)

Wäre wirklich nett, wenn ihr mir helfen würdet...

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community