Bitweiser Zugriff

[Peter Thomassen]

Hallo Daniel,

Ein solches Kommando ist vermutlich einfacher in einen Prozessor zu implementieren als das o.g. Schieberegister ... gibt es solche Prozessoren?
Keine Ahnung. In den meisten Anwendungen sind wahrscheinlich keine Shift-Operationen das Problem sondern Operationen wie Floatingpoint-Operationen, die viel aufwendiger sind.
Machst Du Dir auch immer Gedanken, wenn Du zwei Zahlen multiplizierst, ob das jetzt O(1) O(n) oder gar O(n²) ist? ;-)

Wenn ich nur multiplizieren würde, wäre mir schon daran gelegen, das möglichst effizient zu tun. Es hat sich wohl auch jemand Gedanken über die Addition gemacht, als er das Carry-Lookahead-Verfahren erfand ;-)

Auf dieser Ebene ist die O-Notation sowieso nicht mehr besonders hilfreich. So lang Deine Argumente beschränkt sind (Du shiftest ja maximal um 31 oder 63 Bit), hast Du immer O(1).

Wieso nun das? Martin schrieb: "Bei der klassischen Intel-Architektur ist aber der Zeitaufwand für eine Schiebeoperation tatsächlich proportional zur Anzahl der Bitpositionen."

Es kommt also auf den Gesammtalgorithmus an, wie Deine asymptothische Laufzeit aussieht. Wenn es Dir nicht nur um eine rein akademische Diskussion geht, solltest Du Deine Anwendung beschreiben.

Hm, ich möchte den Zweck der ganzen Sache gerne noch ein wenig für mich behalten, bis die Sache ein wenig weiter gereift ist. Ich komme mir recht blöd vor, solches hier zu schreiben, weil ich euch damit die Chance nehme, zu verstehen, worum es geht. Ich ahne, dass das ein k.o.-Kriterium für diesen Thread ist :-(

Eigentlich wollte ich aber weder eine akademische Diskussion (die ich sehr interessant finde!) noch eine über die Anwendung anzetteln, sondern einfach die Frage stellen, wie schnell ein einzelnes Bit gezielt gelesen werden kann :-) Daher bleibt die Frage, ob es Prozessoren gibt, die dies mittels eines Kommandos explizit unterstützen.

Wenn Du wirklich darauf angewiesen bist, die Geschwindigkeit deines Programmes auf dieser ebene zu optimieren, solltest Du erstmal eine compilierte Sprache nehmen und gucken, was das bringt. Das muss nicht C sein, selbst etwas wie Java oder eine .NET-Sprache wäre ein schritt.
Wenn Du wirklich über Prozessorbefehle nachdenken musst (was ich nicht glaube), solltest Du dann zu C oder gar Assembler wechseln.

Wie gesagt, der Algorithmus ist noch etwas unausgegoren, deswegen bin ich momentan nicht an einer idealen Implementierung interessiert. Ich wollte vielmehr unabhängig von der verwendeten Programmiersprache ausloten, inwieweit die Bitzugriffe die Laufzeit beeinflussen werden. Meine Überlegungen haben nämlich ergeben, dass die Laufzeit proportional zur Anzahl der Bitzugriffe, und damit natürlich zu deren Laufzeit ist. Dazu wollte ich eben wissen, ob sie in konstanter Zeit stattfinden können.

Sollte es Prozessoren geben, die einen gezielten Bitzugriff in konstanter Zeit erlauben, sollte ich wirklich mal über C mit Inline-Assembler nachdenken. (Die Schwierigkeit ist, dass ich C zwar einigermaßen lesen kann, aber noch nie was C geschrieben habe. Bisher nur PHP und Shell.)

Bye,
Peter