Schnelle Operation < Sonstiges < Hochschule < Informatik < Vorhilfe
|
Hi!
Ich betrachte 32 Bit Integers.
Ich habe einen Integer x. Z.B. x = 100110000000000000000
Und ich habe einen Integer y. Z.B. y = 1100111
Ich möchte nun y sooft nach links shiften (von rechts kommen nullen) bis y >= x und y möglichst klein. Ich könnte natürlich sagen:
while (y < x) {
y <<= 1;
}
Mein Frage: Kann man das irgendwie schneller machen? Vielleicht über irgendeine Maske o.ä. aber mir ist nichts eingefallen. Letztendlich werde ich den Code in Assembler umsetzen, insofern bezieht sich schnell dann auf die Assembler-Implementierung.
Hat jemand eine Idee?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:37 Mi 12.05.2010 | | Autor: | felixf |
Hallo!
> Ich betrachte 32 Bit Integers.
> Ich habe einen Integer x. Z.B. x =
> 100110000000000000000
> Und ich habe einen Integer y. Z.B. y = 1100111
> Ich möchte nun y sooft nach links shiften (von rechts
> kommen nullen) bis y >= x und y möglichst klein. Ich
> könnte natürlich sagen:
> while (y < x) {
> y <<= 1;
> }
Wenn man annimmt, dass eine solche Darstellung mit 32-bit-Zahlen moeglich ist, dann liefert dieser Programmcode das richtige Ergebnis.
> Mein Frage: Kann man das irgendwie schneller machen?
Was heisst schneller? Genauer: wie misst du Geschwindigkeit?
> Vielleicht über irgendeine Maske o.ä. aber mir ist nichts
> eingefallen. Letztendlich werde ich den Code in Assembler
> umsetzen, insofern bezieht sich schnell dann auf die
> Assembler-Implementierung.
Hier fehlen eine Menge informationen. Was fuer Assembler? Was kann die CPU (Befehlssatz samt Cycle counts, Wortbreite, Optimierungen wie Pipelining, ...)? Wie genau ist die Eingabe spezifiziert (unsigned? signed?)? Ist vorher schon etwas ueber die Daten bekannt?
Ich vermute, du brauchst das hier in einem anderen Kontext, den du uns nicht verraten willst -- aber, falls wir ihn denn kennen wuerden, der uns helfen wuerde deine Frage besser zu beantworten.
LG Felix
|
|
|
| |
|
So als Beispiel:
Assembler hängt immer davon ab, was die Hardware unterstüzt. Ich arbeite mit Microchips die in harware ausschließlich um 1 nach rechts/links shiften können. Selbst, wenn man wüßte, daß man 3x shiften muß, so muß man den Befehl immernoch 3x ausführen.
Rein mathematisch gibt der Logarithmus dir die Info über die Länge der Zahlen, der wird aber kaum in hardware und damit assembler verfügbar sein.
|
|
|
|
