C++ Fragen zu Programm das Dezimalzahlen in Binärzahlen umwandeln soll.

[BlackMark]

@nerdalicious Die Aufgabe verlangt, dass nur <iostream> verwendet werden soll und verbietet explizit Arrays. Die Lösung mit einem String geht also nicht, ein String in diesem Kontext ist auch ein Array.

@Laschadura Wieso sollte die Aufgabenstellung fehlerhaft sein? Es wurden ja sogar schon mehrere Lösungen präsentiert, die nur <iostream> verwenden und nichts in einem Array/String zwischenspeichern.

Die Lösung mit Rekursion von @Panzerfahrer funktioniert und erfüllt die Aufgabenstellung und die Lösung von @mkossmann ebenfalls. Auch wenn beide Implementierungen nicht komplett korrekt sind, die Ideen dahinter stimmen.

Hier die beiden Lösungen von @Panzerfahrer und @mkossmann komplett ausimplementiert/korrigiert und auch der Edge-case von 0 behandelt:

#include <iostream>

void estimateLengthConversion(unsigned int number) {
  if (number == 0) {
    std::cout << "0\n";
    return;
  }

  bool leadingZeros = true;
  for (int i = sizeof(unsigned int) * 8 - 1; i >= 0; --i) {
    const unsigned int mask = 1 << static_cast<unsigned int>(i);
    if (number & mask) {
      leadingZeros = false;
      std::cout << '1';
    } else if (!leadingZeros) {
      std::cout << '0';
    }
  }
  std::cout << '\n';
}

void recursiveConversionHelper(unsigned int number) {
  if (number > 0) {
    recursiveConversionHelper(number >> 1);
    std::cout << (number % 2);
  }
}

void recursiveConversion(unsigned int number) {
  if (number == 0) {
    std::cout << "0\n";
  } else {
    recursiveConversionHelper(number);
    std::cout << '\n';
  }
}

int main() {
  unsigned int input;
  std::cin >> input;

  estimateLengthConversion(input);
  recursiveConversion(input);

  return 0;
}

Gruß
BlackMark

 

[Panzerfahrer]

Hallo BlackMark,

du hast recht den Sonderfall zahl=0 habe ich nicht bedacht.
Vielen Dank.

Viele Grüße

Panzerfahrer

 

[RalphS]

Der Hinweis auf bitshift anstelle modulo beschränkt sich darauf, daß bitshift in beide Richtungen funktioniert und nicht nur eine.
Mit lshift kann man die Chose "umgekehrt" verarbeiten. Mit modulo geht nur vom höherwertigen Bit in Richtung niederwertigem, also rshift.

Ob ich mit n/2 komme oder mit n >> 2 ist wumpe, nur daß eins davon eine logische Operation ist und die andere bitwise.

n * 2 oder n << 2 ist genauso wumpe. Muß dann aber die Sache etwas gescheiter angehen, da wir hier ein Überlaufbit betrachten müssen.

Irgendwas sagt mir, daß man mit einem Komplement eine sehr elegante Lösung hinbekommen sollte, aber das könnte auch Wunschdenken meinerseits sein.

 

[BlackMark]

@RalphS Dir ist schon klar, dass n / 2 != n >> 2 ist, oder? Du bist um einen Faktor 2 daneben: n / 2 == n >> 1.

Gruß
BlackMark

 

[RalphS]

Schande über mir (mich) — ist schon spät und Wochenende und überhaupt. 🤗

 

[nerdalicious]

n / 2 ist äquivalent zu >> 1.
modulo 2 zeigt dir nur an, was das letzte bit ist. Anders formuliert, und leicht eingesehen kannst du dies mathematisch: Modulo 2 ist äquivalent zur Frage "ist die Zahl gerade oder nicht". Nur das letzte Bit hat Einfluss darauf, ob eine Zahl mit oder ohne Rest durch zwei teilbar ist. Alle anderen Bits entsprechen Zahlen, die Vielfache der Zahl 2 sind.

 

[RalphS]

... eigentlich ging es nur darum, per lshift die Eingabe “rückwärts”, also most significant bit first, zu verarbeiten und unterwegs nichts speichern zu müssen.
Mathematik ist explizit raus. Es geht rein um die Präsentation ohne Anspruch darauf, daß der ausgegebene Wert identisch dem eingegebenen ist.

 

[BigNum]

Nachdem die Büchse der Pandora (Posten von Lösungscode) schon geöffnet ist kippe ich hier mal meine Lösung rein...

#include <iostream>


int main()
{
    unsigned int number;
    unsigned int power_of_2= 1;
    
    std::cin >> number;
    
    while(number >= power_of_2) power_of_2<<= 1; // go bitwise up to find MSB of "number"
    if (power_of_2>1) power_of_2>>= 1; // we've gone 1 bit too far, so go back one, but keep at least one
    for( ; power_of_2>0; power_of_2>>= 1) std::cout << ((number & power_of_2) ? "1" : "0"); // go bitwise down
    
    return 0;
}

also effektiv ein Dreizeiler.
Wenn man einen kleinen Trick anwendet ist's nur ein Zweizeiler:

#include <iostream>


int main()
{
    unsigned int number;
    unsigned int power_of_2= 1;
    
    std::cin >> number;
    
    while(number/2 >= power_of_2) power_of_2<<= 1; // go bitwise up to find MSB of "number"
    for( ; power_of_2>0; power_of_2>>= 1) std::cout << ((number & power_of_2) ? "1" : "0"); // go bitwise down
    
    return 0;
}

HTH

BigNum

 

[Laschadura]

Hallo @BlackMark.
Ich habe gemeint die Aufgabenstellung könnten Fehlerhaft sein, da die Lösungen @Panzerfahrer und @mkossmann neue Konzepte verwenden die wir in der Vorlesung noch nicht hatten. Du musst wissen das wir vor 2 Wochen mit C++ angefangen haben und ich noch ein totaler Neuling im Feld bin. Deswegen waren ein paar der vorgeschlagenen Konzepte auch ein bisschen verwirrend.
Gruss Laschadura

 

[Aliosy]

Warum ist Rekursion nicht deterministisch?

Man kann die Aufruftiefe nicht (immer) abschätzen. d.h. je nach Komplexität ist die CPU Zeit nicht zu bestimmen.
Man nehme einen verketteten Baum vor, z.B. Dateisystem. Über rekursive Aufrufe macht es zwar einfacher alle Verzeichnisse durchzugehen, aber sollte aus bestimmten Gründen pausiert/abgebrochen werden, musst du den ganzen Weg wieder zurückgehen. Ist der gleiche Ablauf flach aufgebaut, kann sofort abgebrochen werden, es ist sogar möglich die CPU Zeit relativ einfach zu errechnen. In zeitkritischen Anwendungen muss man die CPU Zeit kennen, um Zeit-Scheiben nicht zu verletzten.

 

[new Account()]

Eine schwierigere Abschätzbarkeit ergibt aber noch keinen Nichtdeterminismus.
Die CPU-Zeit, die du fürs hochhangeln brauchst, kannst du auch relativ einfach berechnen.