Guten Tag,
wir sollen ein Programm schreiben das x*y*z berechnet ohne *.
Ich habe das ganze natürlich einfach so runter gerechnet
Java:
int x=5;int y=40;int z=3;int erg1=0;int erg2=0;while(y>0){
erg1+=x;
y--;}while(z>0){
erg2+=erg1;
z--;}System.out.println(erg2);
Natürlich tut es was es soll doch ich bin unzufrieden wir haben den Shift Operator behandelt und ich würde sehr gerne wissen wie man sowas mit diesem Operator hin bekommt?
Hab schon einiges versucht doch vor allem denke ich man brauch die Binärwerte von x,y und z. Wenn man diese im Programm erst berechnen muss und hin und her umwandeln muss mit Schleifen dann lasse ich es wie es ist das wird ja dann noch mehr als ich jetzt schon habe
Also wenn man "a" und "b" ganz einfach mit Bitshifts multiplizieren will, klappt das nur, wenn entweder a oder b eine Zweierpotenz ist.
Beispiel:
Java:
int a =5;int b =16;System.out.println(a*b);System.out.println(a<<(int)(Math.log(b)/Math.log(2)));
Da ein Liniksshift um 1 i.d.R einer Multiplikation mit 2 entspricht.
Ansonsten kann man auch jede Multiplikation als Division umschreiben:
Java:
int a =5, b =16, c =2;System.out.println(a /(1/(double) b)/(1/(double) c));
Gibt auch noch andere Algorithmen zur Multiplikation - Stichwort "Russische Bauernmultiplikation" etc - die man mit Hilfe von Bitshifts implementieren kann, aber den einen einfachen Bitshift für so eine Multiplikation gibt es nicht
Wenn ihr gerade das shiften besprochen habt ist das obige alles vorzuziehen.
Es gibt auch noch eine sog. ägytische Multiplikation auch Bauernmuliplikation genannt
die das allein durch Addieren macht: (wie gesagt nicht als Lösung in der Schule verwenden).
Wenn ich das richtig sehe, ist das sogar fast genau das, was ich geschrieben habe; ich wusste gar nicht, dass das einen Namen hat
Der Unterschied besteht darin, dass sich mein "Akkumulator" auf das shift bezieht, das Verdoppeln/Halbieren eben via Shift-Operator gelöst wird und der Modulo-Operator über ein bitweises Und ersetzt wurde.
WOW vielen Dank für die super schnellen Antworten werde mir nun eins nach dem anderen genauer anschauen
Doch leider denke ich das wir diesen netten algorithmus nicht benutzen dürfen
Java:
intmult(int a,int b){int shift =0;int c =0;while(a >0){if((a &1)==1){
c +=(b << shift);}
shift++;
a >>=1;}return c;}
Da wir die Binären Operatoren mit &, | etc noch nicht hatten Ich verstehe auch nicht was das hier überhaupt macht? (a & 1) == 1
Prüft man da binär ab ob das derzeitige Bit eine 1 ist? anderes kann ich mir nicht vorstellen nur wieso ?
Wenn Du Dir das Beispiel von oben ansiehst, brauchen wir ja die gesetzten Bits einzeln.
Wir könnten jetzt also hergehen und einfach die 1 (2^0) in jeder Iteration um eine stelle nach links verschieben (2^1, 2^2, 2^3, ...) und dann mit Hilfe einer binären UND-Verknüpfung feststellen, ob in der Zahl das entsprechende Bit gesetzt ist.
Genauso gut kann man aber auch die 1 fix lasen und die Zahl nach rechts verschieben.
