Dualzahlen in dezimalzahlen

[SaraL]

Ich bin noch absoluter anfänger und brauche etwas hilfe. Ich soll ein programm schreiben in c++ welches dualzahlen in dezimalzahlen umrechnen kann. Ich hab irgendwie den faden verloren. Wer kann helfen.

 

[zerix]

Hallo,

wo hast du ihn denn verloren?

Viele Grüße
Sascha

 

[SaraL]

Die eingabe der zahlen bekomm ich hin. Danach soll eine schleife kommen die zum einen zahl duch 10 und zum anderen die berrechnung vornimmt. Und da komm ich nicht weiter ob do while oder for oder eine kombi aus beiden geht

 

[vfl_freak]

Moin,

ob do while oder for oder eine kombi aus beiden geht

ob WHILE oder FOR sollte eigentlich egal sein, grundlegend sollte man es mit beiden hinbekommen!
Poste mal Deinen bisherigen Ansatz (Code-Tags!!) und stell' dann konkrete Fragen dazu
Du könntest ja auch mal überlegen, wie Du händisch machen würdest! Nimm' mal ein Blatt Papier und schreibe es auf ... die Umsetzung in die Programmiersprache kommt dann fast von alleine

Gruß Klaus

 

[ComFreek]

Kleines Beispiel: 1010 = 10 (dezimal)
Händisch würde man hier wohl 8 + 2 rechnen. Für die Umsetzung in Code ist es jedoch einfacher, wenn du es zuerst 'komplizierter erdenkst':

(( ( ((1) * 2) + 0 ) * 2 ) + 1) * 2 + 0

Du gehst von links nach rechts, nimmst jeweils 1 oder 0 (aktuelle Ziffer), addierst es auf das vorherige, und multiplizierst die Summe insgesamt mit 2.
Vielleicht ist diese Darstellung nicht ganz intuitiv, aber nach dem Ausmultiplizieren siehst du gerade die Definition einer Dualzahl mit Hilfe der Wertigkeiten jeder Stelle:

1 * 2 * 2 * 2 + 0 * 2 * 2 + 1 * 2 + 0 = 1 * 2^3 + 0 * 2^2 + 1 * 2^1 + 0 * 2^0

 

[cwriter]

Hallo

Ich gebe dann auch mal meinen Senf dazu:

Wie ComFreek schon kurz sagte, sind die Zahlensysteme folgendermassen aufgebaut:

Dezimal:
...|100| 10| 1
...| 1 | 0 | 0
= 100d
Binär (Dual)
...| 4 | 2 | 1 |
...| 1 | 0 | 0 |
= 4d

Also wie funktioniert das jetzt?
Sei die Nummer der Stelle k. Dann ist der "Wert" dieser stelle Basis^k. Die erste Stelle ist 0.
Also ist 100d eigentlich 0 * 10^0 + 0 * 10^1 + 1 * 10^2

Das ist die Theorie hinter dem Umwandeln.

Zahlen nun "echt" umzuwandeln, geht folgendermassen:
1. Du suchst dir zuerst die erste Stelle k, die grösser/gleich der gesuchten Zahl ist.
2. Falls b^k kleiner als die Restzahl: subtrahiere (s=Restzahl / b^k) * b^k (= Mache Zahl = Zahl mod s) (s * Basis^Stellennummer) von der Zahl und füge s and Resultat an. Ansonsten: Füge 0 an Resultat an.
3. Verringere k um 1
4. Falls k = -1: Ende, sonst springe zu 2. zurück.

Als Beispiel: 14d in b:
1.
k = 0: 2^0 = 1 < 14
k = 1: 2^1 = 2 < 14
k = 2: 2^2 = 4 < 14
k = 3: 2^3 = 8 < 14
k = 4: 2^3 = 16 >= 14 -> Schritt 2
2.
b^k = 2 ^ 4 = 16 ist grösser als 14, also füge 0 zu Resultat hinzu, Res = 0
3. k = k -1 = 4 -1 = 3
4. k != -1 -> Schritt 2
2.
b^k = 2^3 = 8 is kleiner als 14, und 14/8 = 1 (Int-Division)
Zahl = Zahl mod s = 14 mod 8 = 6
Füge 1 zu Resultat hinzu, Res = 01
3.
k = k-1 = 3-1 = 2
4. k != -1 -> Schritt 2

2. b^k =2 ^ 2 = 4 ist kleiner als 6 -> Zahl = 6 mod 4 = 2, Res = 011
3. k = 2-1 = 1
4. k!=-1 -> 2.

2. 2^1=2 ist kleiner/gleich 2 -> Zahl = 2 mod 2 = 0, Res = 0111
3. k = 0
4. k != -1 -> Springe zu 2.

2. 2^0 = 1 > 0 -> Füge 0 an: Res = 01110
3. k = -1
4. Fertig! (evt. die ersten 0 streichen, also 01110 -> 1110, aber es ist nicht "falsch", die 0 da zu belassen.

Kontrolle: 2^1 + 2^2 + 2^3= 2 + 4 + 8 = 14.

Nun arbeiten wir mit dem Computer und Programmierer sind faul.

Also machen wir uns die bitweisen Operatoren zu Nutze.

Der Einfachheit halber mal ein Beispiel mit 4 bits:
Eine Zahl, warum nicht 14d (1110b), soll analysiert werden.
Dann machen wir uns eine Maske 1000b und ver-und-en das ganze, also

    1110
AND 1000
________
    1000b = 8d != 0

Das erste Bit ist also gesetzt. Dann verschieben wir die Maske nach rechts (shift):

mask = mask >> 1;

Und bekommen wieder eine 1. Dann nochmals. Und dann kommt eine 0. Also genau die binäre Darstellung. Cool, oder?

NEIN. Ist es nicht. Generell ist ALLES bei den Computern ein bisschen https://xkcd.com/927/.
Da gibt es MSB, LSB, Big-/Little-/Middle- Endian, und verschiedene Datentypen wie unsigned (also die natürlichen Zahlen), sign/magnitude (das MSB sagt, ob die Zahl negativ oder positiv ist), one's-complement (Die negativen Zahlen sind das Gegenteil der positiven Zahlen, also 2d = 010b, -2d = 101b), two's-complement (one's complement + 1, also 2d = 010b, -2d = 110b) und dann gibt es noch die Kommazahlen, die komplett anders funktionieren.

Darum: Nimm den bitweisen Weg, wenn du Performance brauchst, denn dieser Weg ist so ziemlich das Schnellste, was du bekommen kannst.

Für deine Übung: Nimm den oben beschriebenen "händischen" Weg. Er mag mühsamer sein, aber er stimmt (meine Beschreibung davon hoffentlich auch ) immer.

Gruss
cwriter

 

[ComFreek]

Darum: Nimm den bitweisen Weg, wenn du Performance brauchst, denn dieser Weg ist so ziemlich das Schnellste, was du bekommen kannst.

Ich verstehe den Sinn deines bitweisen Wegs nicht. Wenn die Ausgangszahl bereits binär vorliegt, ist doch nichts zu tun?
Beim Fragesteller liegt die Zahl in ASCII bzw. BCD (jede Ziffer minus (int) '0') vor.

 

[cwriter]

Ich verstehe den Sinn deines bitweisen Wegs nicht. Wenn die Ausgangszahl bereits binär vorliegt, ist doch nichts zu tun?

Tatsächlich ist das die Umrechnung Dezimal -> Binär, mea culpa.

Ich schätze mal, meine Verwirrung kommt von hier:

Danach soll eine schleife kommen die zum einen zahl duch 10 und zum anderen die berrechnung vornimmt.

Aber vielleicht ist damit einfach / 2 bzw >> 1 gemeint(?). Oder aber... SaraL hat die Zahl per scanf("%d", &zahl) eingelesen.

Spoiler: code

int zahl = 0;
scanf("%d", &zahl);
for(size_t i = 0; i < 10; i++)
{
    if(zahl % 10 == 0) break;
    if(zahl % 10 == 1) ret += (1 << i);
    zahl /= 10;
}
//Ausgabe.

Beim Fragesteller liegt die Zahl in ASCII bzw. BCD (jede Ziffer minus (int) '0') vor.

Sicher?

Von daher: Ohne weitere Informationen ist das eher heiteres Rätselraten

Gruss
cwriter