Beobachtung bzw. Annahme
Der Trick lohnt sich nur, wenn es eine Folge von 1 Bits der Länge n gibt
(deren rechtestest das LSB ist, wobei ich aus dem Stegreif raus noch
nicht sagen kann, ob das eine echt Einschränkung ist, oder ob man die
los wird.)
Dann geht es doch darum, die Multiplikation mit einer derartigen Folge
von n Stück 1 Bist derart abzuwägen, ob
1 | reg2 = reg1
|
2 |
|
3 | wiederhole n-1 mal {
|
4 | reg1 <<= 1
|
5 | reg2 += reg1
|
6 | }
|
weniger Instruktionen benötigt, als
1 | reg2 = reg1
|
2 | reg2 <<= n
|
3 | reg2 -= reg1
|
(unter der Annahme, dass alle Instruktionen gleich lang dauern bzw. die
sonstigen Umstände ... bla, bla, bla))
Hmm. auf den ersten Blick scheint das bei 2 nebeeinander liegenden 1
Bits bereits zielführend zu sein.
Jetzt erhebt sich 'nur noch' die Frage, wie verallgemeinert das, wenn
die Folge von 1 Bits nicht beim LSB endet.