Schreiben Sie ein Programm, welches eine unsigned int Variable einliest (Bitmanipulation)

Question

Schreiben Sie ein Programm, welches eine unsigned int Variable einliest (Bitmanipulation)

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++
}

Gefragt 1 Feb 2018 von user18697

2 Antworten

Ein anderes Problem?

Stell deine Frage

Werner-Salomon · Answer 1 · 2018-02-03T10:12:46+0000

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

Beantwortet 3 Feb 2018 von Werner-Salomon

ich unterstelle Du meinst die Zeile

int bit = x & 1;

Lies meine Antwort noch mal GANZ durch. Du hast den Code auch nicht ausprobiert! Das solltest Du tun, bevor Du (solche) Fragen stellst. i wäre auch falsch.

Ich schrieb: "for( int i = 0; i < 8*sizeof(unsigned int); ++i, x >>= 1 ) // x bei jeden Schritt nach rechts shiften "

nach jedem Durchlauf der Schleife werden die Bits nach rechts geschiftet. D.h. das Bit mit dem Index i steht dann immer an Position 0.

ich schrieb "int bit = x & 1; // durch das Shiften steht das Bit mit Index 'i' jetzt an Position 0"

Denk' dran. Programmieren und Mathematik ist wie Autofahren. Du lernst es nicht durch zuschauen bzw. Lösungen anschauen. Du musst es selber tun!

Kommentiert 3 Feb 2018 von Werner-Salomon

Ja - ein int bit = x & i; wäre völlig falsch. Da in i nicht die Bit-maske, sondern die Nummer des Bits enthalten ist, das ist nicht das gleiche. Eine alternative Implementierung könnte aber so aussehen:

unsigned int reverse_Bits( unsigned int x )
{
    unsigned int ergebnis = 0;
    for( int i = 0; i < 8*sizeof(unsigned int); ++i ) // x bleibt konstant
    {
        ergebnis <<= 1;
        int bit = x & (1 << i); // die '1' wird in die Position 'i' geshiftet
        if( bit != 0 )
        {
            ergebnis |= 1;
        }
        std::cout << "Bit " << i << " = " << bit << "  Ergebnis = 0x" << std::hex << ergebnis << std::dec << std::endl;
    }
    return ergebnis;
}

hier bleibt das 'x' unverändert und aus dem i wird mit 1<<i eine Bitmaske erzeugt, die das i'te Bit isoliert. Der Unterschied zu oben ist auch, dass die Variable 'bit' nicht nur Werte von 0 oder 1 annimmt, sondern von 0 oder $2^i$. Da bit aber nur auf !=0 abgefragt wird, spielt dieser Unterschied keine Rolle.

Ach und frag' ruhig; ich wollte Dich nicht verschrecken. Es gibt keine dummen Fragen!

Kommentiert 3 Feb 2018 von Werner-Salomon

Nein, z=x;, so wie Du es schreibst ist falsch. Die Eingabe als double und prüfen auf unsigned int könnte so aussehen:

#include <iostream>

int main()
{
    using namespace std;
    double z;
    cout << "ein double bitte: ";
    if( cin >> z )  // 1.) (s.u.)
    {
        unsigned int x = (unsigned int)z; // 2.)
        if( double(x) == z )    // 3.)
        {
            cout << "Ok - die Eingabe war eine ganze positive Zahl" << endl;
        }
        else
        {
            cout << "falsch - die Eingabe war keine ganze oder keine positive oder eine zu grosse Zahl" << endl;
        }
    }
    else
    {
        cout << "Fehler bei der Eingabe" << endl;
    }
    return 0;
}

1.) prüfe auch, ob die Eingabe eines doubles korrekt ist

2.) hier wird der Inhalt von z der Variable x zugewiesen.

3.) wenn dies noch gleich ist, dann konnte der Inhalt von z vollständig nach x kopiert werden

Gruß Werner

Kommentiert 4 Feb 2018 von Werner-Salomon

Als ich die erste Funktion getestet habe funktionierte das Programm fehlerfrei, konnte sogar sehr hohe Zahlen eingeben ohne, dass das die Variable überladen wurde.

Aber als ich diese eine Funktion reverse_Bits( unsigned int x ) aufrufen und testen sollte, lief es nicht...

Ich glaube, dass es an mir lag, dass mir da ein Fehler unterlaufen ist

#include <cstdlib>
#include <iostream>

using namespace std;

int zaehle_1erBits(unsigned int x)
{
    int anzahl = 0;
    for(;x !=0;x>>=1)
    {
    if(x&1)
        ++anzahl;
}
    return anzahl;
}
unsigned reserve_Bits(unsigned int x)
{
    for(int i =0; i<8*sizeof(unsigned int); ++i, x>>=1)
    {
        int bit = x&1;
        std::cout << "Bit" << i << "=" << bit << std::endl;
    }
    return 0;
}

  int main(int argc, char** argv) {
  
    using namespace std;
    for(unsigned int zahl; cin >> zahl;)
    {
        cout << "Die Anzahl der 1'en in " << zahl << " ist " << reserve_Bits(zahl) << endl;
    }

    return 0;
}

Überall Bit[jeweilige Nummer] = 0

Das Programm an sich funktioniert aber mit der Funktion zaehle_1erBits.

Wäre nett, wenn du mir auch da helfen würdest :)

Kommentiert 4 Feb 2018 von user18697

ich meinte die Funktion 'reserve_Bits(zahl)', und habe das auch geschrieben (s.o.)

Die Funktion soll doch aus einer gegebenen Zahl (Parameter zahl) vom Typ unsigned int eine andere Zahl generieren, bei der die Bitfolge genau anders herum ist - also 'reverse'. So wie in Deiner Aufgabenstellung beschrieben "ein Programm, welches ... die Reihenfolge der Bits umkehrt und den entstehenden Zahlenwert in
einer neuen unsigned int Variable speichert"

Ich hatte Dir auch diese Funktion schon fix und fertig gepostet (s.o. meine Antwort). Du hast aber einen Zwischenstand aus meiner Antwort verwendet, wo ich Dir nur erklären wollte, wie man dieses Funktion entwickelt.

Ich schließe daraus, dass Du so wenig von dem Code verstehst, dass Du eine Lösung nicht erkennst, wenn man sie Dir zeigt. Das macht die Sache ziemlich schwierig für mich, Dir irgendwas zu erklären.

Bist Du Student oder Schüler? Wie lange lernst Du schon C++ und wo?

Kommentiert 4 Feb 2018 von Werner-Salomon

"... dass dieser Code auch den Hexadezimalcode der eingegeben Zahl(der umgekehrt ausgegeben wird)"

Dies ist Dein zuletzt geposteter Code der Funktion 'reserve_Bits'

unsigned reserve_Bits(unsigned int x) 
{ 
    for(int i =0; i<8*sizeof(unsigned int); ++i, x>>=1) 
    { 
        int bit = x&1; 
        std::cout << "Bit" << i << "=" << bit << std::endl; 
    } 
    return 0; 
}

er enthält eine for-Schleife, die genauso oft durchlaufen wird, wie die Anzahl der Bits im Typ unsigned int. Mit jedem Durchlauf wird die Variable x nach rechts geshiftet (weisst Du was das bedeutet?) und anschließend das Bit an der Position 0 selekiert (int bit = x & 1;). Dieses Information wird dann auf std::cout ausgegeben. Nach Ablauf der Schleife wird immer 0 zurück gegeben (das macht return 0;)

Weder in dieser Funktion, noch in dem ganzen Programm welches Du gepostet hast, befindet sich irgendetwas mit 'hex' oder Hexadezimal.

Ich rede immer von dem Code, den Du hier einstellst!

Kommentiert 5 Feb 2018 von Werner-Salomon

Mmmh! über was reden wir denn ?

Diese Zeile "std::cout << "Bit " << i << " = " << bit << " Ergebnis = 0x" << std::hex << " stammt aus meiner Antwort. Ich rede die ganze Zeit über Deinen Code.
Du schriebst: "Aber als ich diese eine Funktion reverse_Bits( unsigned int x ) aufrufen und testen sollte, lief es nicht..."

und dazu schriebst Du diesen Code (s.o. vor 17 Stunden):

unsigned reserve_Bits(unsigned int x) 
{ 
    for(int i =0; i<8*sizeof(unsigned int); ++i, x>>=1) 
    { 
        int bit = x&1; 
        std::cout << "Bit" << i << "=" << bit << std::endl; 
    } 
    return 0; 
}

und dann fragte ich Dich, was Du denn meinst was DEIN Code (der blaue) da oben denn macht? Lies die ganze Konversation noch mal in Ruhe durch.

Kommentiert 5 Feb 2018 von Werner-Salomon

'hexa-' als Päfix kommt aus dem Griechischen und steht für die 6. 'dezi' steht für die 10 - macht zusammen 16. Das Hexadezimalsystem ist das Stellenwertsystem für Zahlen zur Basis 16. So wäre z.B eine 223 (dezimal)

$$223 = 13\cdot 16^1 + 15 \cdot 16^0= DF_{16}$$

Das D steht für eine 13 und das F für eine 15. Da es keine (Dezimal-)Ziffern für die Zahlen 10 bis 15 gibt, ersetzt man diese durch die Buchstaben A bis F.

Das was Du mit '0001 1110' meinst, ist das Binärsystem. Also das Stellenwertsystem zur Basis 2. Der Vorteil des Hexadezimalsystems besteht darin, dass Du es relativ leicht in das Binärsystem umwandeln kannst, da 2 ein Teiler von 16 ist. Und die Bits sind nur im Binärsystem 'sichtbar'.

Der Manipulator std::hex sorgt dafür, dass Zahlen im Hexadezimalsystem ausgegeben werden.

Kommentiert 5 Feb 2018 von Werner-Salomon

"Sry, dass ich dich wieder nerve, ..." Du nervst nicht! Für Fragen und auch für Nachfragen ist dieses Forum da.

"... aber dazu muss man doch eine seperat zu den anderen Funktionen noch eine schaffen und auf der zahl der anderen Funktion zugreifen?" Jetzt wird's schwierig (für mich). Auf was genau bezieht sich das Wort 'dazu' in Deiner Frage? Und was verstehst Du unter "auf die Zahl der Funktion zugreifen"? Ich unterstelle, Du meinst nicht die Anzahl der Funktionen. Ich gehe mal davon aus, dass Du das Resultat der Funktion meinst; das muss im allgemeinen Fall keine Zahl sein.

Der Versuch einer Antwort:

Du hast drei Aufgaben (oben von 1 bis 3 nummeriert). Die Lösung der erste und der zweite Aufgabe kannst Du jeweils in eine eigene Funktion packen, so wie ich es bereits vorgeschlagen habe. Diese Vorgehensweise ist nicht zwingend, würde ich Dir aber empfehlen.

Die Implementierung der Aufgabe 3 - also die Ausgabe des Eingabe und des Resultats aus Aufgabe 2 (das sind IMHO die beiden Zahlen, von denen in der Aufgabestellung die Rede ist) kannst Du in der main-Funktion vornehmen. Das wäre auch nur eine Zeile Code.

Kommentiert 9 Feb 2018 von Werner-Salomon

Ok - das habe ich nicht geahnt, dass Du das nicht weißt! Du kennst das aus der Mathematik. Das Resultat einer Funktion ist gleich dem Funktionswert

$$y=f(x)$$ wobei das '=' oben nicht dasselbe ist, wie das '=' im Programm, bei letzterem ist es eine Zuweisung. In Code geht das z.B. so:

int main()
{
    using namespace std;
    unsigned int zahl;
    if( cin >> zahl )
    {
        unsigned int zahl_reverse = reserve_Bits( zahl ); // hier ist y:=f(x)
        //  einfach das Resultat der Funktion der 
        //      Variable 'zahl_reverse' zuweisen
        cout << hex << "Die Zahl war 0x" << zahl << " und bei Umkehrung der Bitreihenfolge "
            << " erhaelt man 0x" << zahl_reverse << dec << endl;
    }
    return 0;
}

Gruß Werner

Kommentiert 9 Feb 2018 von Werner-Salomon

"... aber es ging darum wie man von int main auf die Variable der Funktion zugreift..." streng genommen zunächst mal gar nicht! Eine (sogenannte automatische) Variable ist nur in dem Scope gültig, in dem sie definiert wurde. Das gilt für Variablen auf dem Stack, die Heap-Variablen lasse ich mal weg. 'Variable auf dem Stack' bedeutet das was Du unter Variable kennst. Es ist z.B. so

{ // hier beginnt ein Scope

int zahl = 42; // eine Variable auf dem Stack namens 'zahl'

cout << "Zahl = " << zahl << endl; // es wird 42 ausgegeben.

{ // hier beginnt ein 2.Scope

int zahl = 33; // das ist eine zweite Variable, ...

// ... unterschiedlich wie oben, aber mit gleichem Namen!

cout << "Zahl = " << zahl << endl; // es wird 33 ausgegeben.

} // hier endet der 2.Scope; die 2. Variable 'zahl' existiert nun nicht mehr

cout << "Zahl = " << zahl << endl; // es wird wieder 42 ausgegeben.

} // hier endet der 1.Scope

Da so etwas bei dem (menschlichen) Leser des Programms zu Verwirrungen führt, sollte Du nie zwei Variablen in einem geschachtelten Scope gleich benennen! Aber für den Computer ist das ein Problem.

Mit jeder Deklaration einer Funktion beginnt auch ein neuer Scope! Hast Du z.B.

int addiereEineEins( int zahl ) // diese 'zahl' Variable ist neu

{ // der Scope beginnt bereits oben in der Parameterliste

zahl = zahl + 1;

return zahl;

} // Scope Ende

der Parameter 'zahl' ist bereits eine neue Variable, die mit anderen variablen mit Namen 'zahl' nichts zu tun haben. Du könntest sie innerhalb der Funktion auch 'x' oder 'furz' nennen:

int addiereEineEins( int x )
{
x = x + 1;
return x;
}

... das wäre absolut identisch!

Mit Aufruf der Funktion wird dem Aufrufer dann nur das übergeben, was hinter dem return steht. Und das ist immer eine Kopie, genau wie der Parameter oben eine Kopie der beim Aufruf der Funktion übergebenen Variable ist. Und das alles sollte Du schon verstanden haben, sonst hättest Du meine Antwort hier bei dieser Frage gar nicht nachvollziehen können - oder!(?) Es ist nämlich egal, ob Du als Parameter ein int oder ein Objekt übergibst.

Gruß Werner

Kommentiert 10 Feb 2018 von Werner-Salomon

wächter · Answer 2 · 2018-02-02T13:18:27+0000

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

}

Schreiben Sie ein Programm, welches eine unsigned int Variable einliest (Bitmanipulation)

2 Antworten

Ähnliche Fragen

Eingabetools:

Beliebte Fragen:

Heiße Lounge-Fragen: