nicht angemeldet
Hallo Daniel!
- 5 Schritte für den Bitshift
- 1 Schritt für die and-Verknüpfung (oder sind das 32, weil alle Bits verglichen werden?)
Prozessorinstruktionen werden das wohl 2 sein. Ich habe das mal kurz für x86 nachgeguckt. Dort gibt es Shift-Anweisungen, um mehrere Bits weit zu shiften. Der Prozessor muss da natürlich mehrere Schritte durchführen (Ein Schieberegister mehrmals ein Bit weiter setzen oder sowas). Im Vergleich zu Operationen wie einer Multiplikation ist das aber noch ziemlich einfach.
Im konkreten Fall stellen die Bitzugriffe einen wesentlichen Teil der Anweisungen da, sodass die Effizienz der verwendeten Shifts durchaus von Bedeutung ist.
Evtl. kann man auch ein Schieberegister bauen, das mehrere Bit weit in einem Schritt schieben kann, aber solche Überlegungen sind für's Programmieren uninteressant. Selbst auf Maschinensprachebene geht das "in einem Schritt".
Das stimmt, dem Programmierer kann's egal sein. Möglicherweise wäre es aber interessant, ein solches Schieberegister zu haben, wenn man damit enorme Zeitvorteile erzielen kann. Mir geht es ja um die Zeitkomplexität -- kann man also sagen, dass eine Verschiebung über mehrere Positionen in O(1) gelöst werden kann (also unabhängig von der Länge der Zahl)?
2.)
Der Compiler erkennt solche Konstrukte und ersetzt sie durch einen direkten Zugriff auf das Bit. Zur Laufzeit ist das also 1 Schritt (unabhängig vom zu betrachtenden Bit).
Wenn der Prozessor so ein Kommando hat, könnte er das tun. Ich würde jetzt aber vermuten, dass es so etwas idR. nicht gibt und da normalerweise genau die zwei Kommandos "shift" und "&" beim Prozessor auch ankommen.
Ein solches Kommando ist vermutlich einfacher in einen Prozessor zu implementieren als das o.g. Schieberegister ... gibt es solche Prozessoren?
Danke,
Peter
Der Martin