RadixSortteilproblem

[McSnoop]

Folgende Aufgabe raff ich nicht so ganz:

Sie stammt aus dem Buch von Robert Sedgewick: Algorithmen in Java Kapitel 10 Radixsort Aufgabe 10.1

Wieviele Ziffern ergeben sich, wenn eine 32-Bit-Größe als Zahl zur Basis 256 betrachtet wird? Beschreiben Sie, wie die einzelnen Ziffern zu extrahieren sind. Beantworten Sie die gleiche Frage für die Basis 2^16.

Hat einer ne Idee wie die Aufgabe zu verstehen íst?

mfg
Snoop

 

[byte]

Die Aufgabe ist in der Tat etwas komisch formuliert. Ich nehme einmal an, mit Ziffern ist die Anzahl an stellen gemeint. Also:

Eine 32-Bit Zahl ist eine Zahl, die binär 32 Stellen hat. Betrachtet man Zahlen zur Basis 256, dann bedeutet dies, dass man die (dezimalen) Zahlen von 0 bis 255 mit nur einer Stelle darstellen kann (falls das unklar ist: vergleiche Dezimalsystem 0-9 Zahlen pro Stelle oder Hexadezimalsystem 0-15 Zahlen pro Stelle). Daraus folgt (256 = 2^8), dass eine 32-Bit Zahl im Zahlensystem zur Basis 256 vier Stellen hat (32 / 8 = 4). Dementsprechend hat eine 32-Bit Zahl im Zahlensystem zur Basis 2^16 zwei Stellen (32 / 16 = 2). Im Hexadezimalsystem (2^4) hingegen wären es 8 Stellen (32 / 4 = 8).

Die einzelnen Ziffern kannst Du berechnen, indem Du die 32-Bit Zahl jeweils in vier 8-Bit Blöcke einteilst. Jeden dieser 8-Bit Blöcke kannst Du dann in eine Ziffer der Zahl zur Basis 256 umrechnen.

Mit dem Hexadezimalsystem (Zahl zur Basis 16) lässt sich das besser veranschaulichen. Da sind es statt 8-Bit dann 4-Bit Blöcke. Beispiel:

Binär: (1111)(1111)(1111)(1111)
Hexa:  (  F )(  F )(  F )(  F )

 

[McSnoop]

gut das haben wir so auch im irc durchgekaut, aber trotzdem thx schonmal.

Wenn ich nun eine Zahl habe die 32 Bit länge hat, sprich 32 Stellen und die zur Basis 256 nehme, dann habe ich ja folgendes konstrukt:

256^32+256^31+....+256^1+256^0

oder sehe ich das falsch?

da im weiteren in der Aufgabenstellung im 2ten teil von einer Basis 2^16 die Rede ist 2^16-->65536 müsste das ganze ja nun so ausschaun:

65536^32+65536^31+....+65536^1+65536^0

wenn man aber die größe der Zahlen betrachtet bekommt man keine 32 stellen voll ohne einen Überlauf zu erwischen.

Hab ich da nen Denkfehler drinnen?

 

[byte]

Wenn ich nun eine Zahl habe die 32 Bit länge hat, sprich 32 Stellen und die zur Basis 256 nehme, dann habe ich ja folgendes konstrukt:

256^32+256^31+....+256^1+256^0

oder sehe ich das falsch?

Das siehst Du falsch. 32 Bit Länge bezieht sich doch immer nur auf die Binärdarstellung einer Zahl. Eine binäre Zahl mit 32 Stellen ist eine 32-Bit Zahl, also:

2^31 + 2^30 + 2^29 + ... + 2^1 + 2^0 = 2^32 - 1 = 4294967295

Wenn Du das ganze nun ins Zahlensystem zur Basis 256 umrechnest, dann hat diese Zahl natürlich nicht mehr 32 Stellen sondern, wie ich oben beschrieben habe, nur noch vier:

256^3 + 256^2 + 256^1 + 256^0 = 256^4 - 1 = 4294967295

Und zur Basis 2^16 siehts dann halt so aus:

65536^2 - 1 = 4294967295

 

[McSnoop]

gut gerafft und nun teil2:

Beantworten Sie die gleiche Frage für die Basis 2^16.

wenn hier nun die rede von der Basis ist, was im ersten Teil die 256 war , müsste diese wenn es nun heißt die Basis ist 2^16 gleich 65536 sein.

65536^n+65536^n-1+...+65536^1+65536^0

da aber schon 65536^2 = 4294967295 ist ist die maximale darstellung der zahl sozusagen: 100 zur basis 2^16

das sollte eigentlich richtig sein wenn man davon ausgeht das die basis 2^16 ist. oder?

 

[McSnoop]

Des Weiteren bleibt immernoch zu klären:

Wieviele Ziffern ergeben sich, wenn eine 32-Bit-Größe als Zahl zur Basis 256 betrachtet wird?

Ist damit die reine Stellenanzahl gemeint, also max 4 eigentlich schon oder?

 

[McSnoop]

dieser post kann ignoriert werden. Hab gerade selber den fehler gefunden und den inhalt hier entfernt bevor es einer liest . =)

 

[byte]

da aber schon 65536^2 = 4294967295 ist ist die maximale darstellung der zahl sozusagen: 100 zur basis 2^16

das sollte eigentlich richtig sein wenn man davon ausgeht das die basis 2^16 ist. oder?

Das verstehe ich jetzt nicht so ganz. Warum 100 zur Basis 2^16?

Nochmal zum Verständnis: Man kann Zahlen in unterschiedlichen Zahlensystemen darstellen. Die Zahl bleibt im Prinzip immer dieselbe, egal in welchem Zahlensystem ich sie darstelle, es ändert sich lediglich die Darstellung der Zahl. Also eine 13 ist eine 13, egal ob ich sie nun zur Basis 2, 8, 10, 16 oder 256 darstelle. Sie sieht halt nur je nach Zahlensystem anders aus.

Wenn ich mich nun im Zahlensystem zur Basis 256 bewege, dann bedeutet dies, dass mein Zahlensystem 256 unterschiedliche Ziffern besitzt, um Zahlen darzustellen. Im Vergleich dazu: Das normale Dezimalsystem hat 10 Ziffern, um Zahlen darzustellen und das Binärsystem hat 2. Das bedeutet für das System zur Basis 256, dass ich die (Dezimal-)Zahlen 0 - 255 mit nur einer Ziffer (also einer Stelle) in diesem System darstellen kann. Ab 256 sind es dann zwei Ziffern und so weiter.

Des Weiteren bleibt immernoch zu klären:

Wieviele Ziffern ergeben sich, wenn eine 32-Bit-Größe als Zahl zur Basis 256 betrachtet wird?

Ist damit die reine Stellenanzahl gemeint, also max 4 eigentlich schon oder?

Also dieser Teil ist etwas unklar. Ziffern sind ja eigentlich die einstelligen Zahlen, mit denen man eine Zahl darstellen kann im jeweiligen Zahlensystem. Also im Dezimalsystem haben wir die Ziffern 0 - 9. Wie oben beschrieben gibt es im Zahlensystem zur Basis 256 eben 256 verschiedene Ziffern zur Zahlendarstellung (ist etwas schwierig vorstellbar, da es keine vernünftige Darstellung dafür gibt). Ich glaube aber, der Aufgabensteller meint eher die Anzahl benötigter Stellen. Und das sind in diesem Fall vier und (zur Basis 2^16) zwei.