Dezimalzahlen in Binärdarstellung - Meine Idee

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
ne0h
User
Beiträge: 115
Registriert: Samstag 16. Februar 2008, 11:35

Beitragvon ne0h » Montag 19. Mai 2008, 19:11

Hallo sehbaer,

dabei handelt es sich um eine sogen. "Bitverschiebung".

Code: Alles auswählen

n >> 1
bedeutet in diesem Fall, dass der Inhalt von "n" um eine Bitstelle nach rechts verschoben wird.

So zumindest kenne ich diese Schreibweise.

Man korrigiere mich bitte, falls ich es falsch erklärt habe.


ne0h
Benutzeravatar
sehbaer
User
Beiträge: 39
Registriert: Sonntag 30. März 2008, 17:26
Wohnort: Kölle

bitshift, Bitverschiebung

Beitragvon sehbaer » Montag 19. Mai 2008, 19:45

Danke! Hatte ich schon ein wenig vermutet und nun auch gefunden:
http://docs.python.org/ref/shifting.html
Nach solchen Zeichen ist leider immer ganz übel zu suchen...
...es sind ganz bestimmt mehr Nullen als Einsen.
ne0h
User
Beiträge: 115
Registriert: Samstag 16. Februar 2008, 11:35

Beitragvon ne0h » Montag 19. Mai 2008, 20:22

Hm... könnte mir Jemand diese Lösung von "sma" Schritt für Schritt erläutern?

Code: Alles auswählen

def d2b(n):
  return d2b(n / 2) + "01"[n % 2] if n else ""



Ich komme damit nicht ganz zurecht, auch wenn es einwandfrei läuft. Irgendwie fehlt mir da das Verständnis, warum ich auf das "return" diese Addition durchführe bzw. warum überhaupt eine Addition und dann mit diesem Ausdruck:

Code: Alles auswählen

+ "01"[n % 2]



ne0h
Benutzeravatar
sehbaer
User
Beiträge: 39
Registriert: Sonntag 30. März 2008, 17:26
Wohnort: Kölle

concat

Beitragvon sehbaer » Montag 19. Mai 2008, 20:46

Ich versuche mich da mal: Das ist eher eine Concatenation als eine Addition. Da wird eine Zeichenkette zusammengetüdelt. Aus der Zeichenkette "01" wird abhängig davon, ob n gerade oder ungerade ist eine "0" oder "1" "herausindiziert" und solange aneindandergetüdelt, bis n = 0 (False) ist. Ich finde Rekursionen immer so schlimm zu beschreiben und hoffe ich habe mich da einigermaßen verständlich ausgedrückt.
...es sind ganz bestimmt mehr Nullen als Einsen.
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

Beitragvon audax » Montag 19. Mai 2008, 20:46

Code: Alles auswählen

"01"[n % 2]


das entspricht:

Code: Alles auswählen

if n % 2 == 0:
    return '0'
else:
    return '1'


Es wird also n % 2 als Index für den String "01" benutzt.
ne0h
User
Beiträge: 115
Registriert: Samstag 16. Februar 2008, 11:35

Beitragvon ne0h » Montag 19. Mai 2008, 21:12

Danke Euch beiden,

das habe ich jetzt verstanden.

Aber trotzdem verstehe ich das nun syntaktisch noch nicht so ganz.

Wie genau wird denn aus dieser Zeichenkette "01" die 0 oder die 1 gefiltert bzw. errechnet, dahinter ist doch ein Ausdruck in einer Liste, oder?

Also das n % 2 steht doch in der Liste []. Wie ist da genau der Bezug zu dem String "01", welcher direkt davor steht?

Ich "sehe" da einfach nicht, wie die Berechnung der Liste auf den String einwirkt.

Hoffe, man versteht, was ich meine.

Gruß

ne0h
EyDu
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Montag 19. Mai 2008, 21:18

Das ist keine Liste, das ist ein Index. Ein Blick ins Tutorial würde vielleicht helfen ;-)
Benutzeravatar
sehbaer
User
Beiträge: 39
Registriert: Sonntag 30. März 2008, 17:26
Wohnort: Kölle

Beitragvon sehbaer » Montag 19. Mai 2008, 21:19

gehste in den Interpreter und machste 'huhu'[3] oder so. Dann wird es klar, denke ich.
...es sind ganz bestimmt mehr Nullen als Einsen.
Zap
User
Beiträge: 533
Registriert: Freitag 13. Oktober 2006, 10:56

Beitragvon Zap » Montag 19. Mai 2008, 21:19

Du kannst ja per Index auf einen String zugreifen und das wird hier gemacht,
erst wird der Modulo ausgerechnet und dieser als Index genutzt

Code: Alles auswählen

>>>3 % 2
1
>>>4 % 2
0
>>>"AB"[0]
"A"
>>>"AB"[1]
"B"
Benutzeravatar
Trundle
User
Beiträge: 591
Registriert: Dienstag 3. Juli 2007, 16:45

Beitragvon Trundle » Montag 19. Mai 2008, 21:21

Das ist einfach die Indizierung eines Strings. Siehe auch Tutorial (3.1.2 Strings).

Code: Alles auswählen

In [23]: "Spam"[0]
Out[23]: 'S'

In [24]: "Spam"[1]
Out[24]: 'p'


etc.

Edit: einhändig ist man eben doch viel zu lahm.
ne0h
User
Beiträge: 115
Registriert: Samstag 16. Februar 2008, 11:35

Beitragvon ne0h » Montag 19. Mai 2008, 21:28

:lol:


Ok, alles klar. Ich starre heute schon zu lange auf den Bildschirm und habe gerade die ganze Zeit wie ein Vollidiot darüber nachgedacht, wie die Liste da hinter dem String was damit zu tun hat.

Jetzt seh ichs auch, nach Euren Hinweisen, dass da einfach nur der Index des Strings berechnet wird.

Manchmal verrene ich mich echt in so komplizierte Gedanken, wie, was, warum, dass ich das offensichtlichste garnicht mehr erkenne.


Danke, ich geh ins Bett. :wink:


ne0h
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Montag 19. Mai 2008, 23:08

ne0h hat geschrieben:Also diese rekursiven Aufrufe will ich jetzt gleich mal angehen.

Ja, uhm, Rekursion ist ein nicht ganz triviales Problem, weil es eben doch recht ungewohnt ist.

ne0h hat geschrieben:Was genau ist das für eine Sprache, in der Deine verlinkten Beispiele sind? Bzw.: Was hat das Ganze mit den von Dir gerade geschriebenen Beispielen zu tun?

Die Beispiele sind in Scheme einer Sprache von der Python viele Konzepte geerbt hat und die ich grad lerne. Ich wollte eben sehen wie so ein Binärkonverter in Scheme aussieht die ich die Sprache auch erst lerne und mich nach Beispielen umsehe, die ich mir zutrauen kann, so ähnlich wie du in Python. Außerdem starten hier manchmal kleine spontane Wettbewerbe, irgendwelche Probleme in allen möglichen Sprachen zu Lösen und sie dann mit der Python-Lösung zu vergleichen.

Übrigens: ``(number->string 21 2)`` wäre natürlich die naheliegendste Lösung gewesen :)
My god, it's full of CARs! | Leonidasvoice vs Modvoice
ne0h
User
Beiträge: 115
Registriert: Samstag 16. Februar 2008, 11:35

Beitragvon ne0h » Dienstag 20. Mai 2008, 16:15

Hallo,

Ok, Scheme sagt mir was (nur vom Namen her :wink: ). Sieht mir grade aber etwas zu "geklammert" aus.


Ähm, dieses Beispiel hier:

(number->string 21 2)


stammt ja von der ertsen Seite. Läuft das denn nun intern per Rekursion oder greift dies auf Bitverschiebungen zurück. Oder besser gefragt:

Welche Variante ist denn nun effizienter in der Ausführungsgeschwindigkeit? (Nicht dass es wirklich von Bedeutung für mich wäre im Moment, aber es interessiert mich nun doch.).


Gruß


ne0h
BlackJack

Beitragvon BlackJack » Dienstag 20. Mai 2008, 20:10

@ne0h: In Python, zumindest in CPython, dürften iterative Lösungen immer schneller sein, als Rekursive. Weil Funktionsaufrufe in CPython relativ teuer sind und keine Tail-Call-Optimization gemacht wird.

Wenn es sich um Endrekursion handelt, kann man von einem Scheme-Compiler erwarten, das der das als effiziente Schleife in Maschinensprache übersetzt. Wobei es in Scheme selbst auch gar keine iterativen Schleifen gibt, da *muss* man also Rekursion als Ausdrucksmittel wählen.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 21. Mai 2008, 00:58

ne0h hat geschrieben:Welche Variante ist denn nun effizienter in der Ausführungsgeschwindigkeit? (Nicht dass es wirklich von Bedeutung für mich wäre im Moment, aber es interessiert mich nun doch.).

Also, die Codes die ich teste:

Code: Alles auswählen

def d2b(n):
  d = ""
  while n:
    d += "01"[n & 1]
    n >>= 1
  return d[::-1]

print d2b(21)

und
[code=](display (string-append (number->string 21 2) "\n"))[/code]
Simpler, synthetischer Benchmark mit 100 Wiederholungen:
[code=]$ time eval 'i=0; while [ $i -lt 100 ]; do python2.5 d2.py > /dev/null ; i=$(($i + 1)); done'
real 0m1.301s
user 0m0.944s
sys 0m0.424s
$ time eval 'i=0; while [ $i -lt 100 ]; do mzscheme -r d2.scm > /dev/null ; i=$(($i + 1)); done'
real 0m3.010s
user 0m2.596s
sys 0m0.400s[/code]
Python läuft schneller, allerdings läuft der Scheme-Code auch im Interpreter (und PLT-Scheme ist nicht wirklich schnell). Kompiliert siehts wohl anders aus, die zahlen liefere ich nach.

Eine rekursive Python-Lösung wäre sicherlich langsamer, als die iterative. Allerdings ist ``number->string`` in PLT auch in C interpretiert, also eigentlich genauso iterativ.
My god, it's full of CARs! | Leonidasvoice vs Modvoice

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder