Erste Schritte x*y*z mit Shift Operator moeglich?

[ocsme]

Guten Tag,
wir sollen ein Programm schreiben das x*y*z berechnet ohne *.
Ich habe das ganze natürlich einfach so runter gerechnet 😛

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 😀

Kennt da jemand eine Idee?

Danke im voraus 🙂

LG

 

[Tarrew]

Also wenn man "a" und "b" ganz einfach mit Bitshifts multiplizieren will, klappt das nur, wenn entweder a oder b eine Zweierpotenz ist.

Beispiel:

        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:

        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 😉

 

[mihe7]

denke ich man brauch die Binärwerte von x,y und z

?!?

x*y*z = a*z mit a = x*y

Wir können das Problem also auf die Multiplikation zweier Zahlen reduzieren.

Schauen wir uns mal x*y für den Fall x = 5 an: Das wäre (2^2 + 2^0) * y, also 2^2 * y + 2^0 * y und damit (y << 2) + y.

Für x = 6 wäre (2^2 + 2^1) * y = 2^2*y + 2^1*y, also (y << 2) + (y << 1).

Für positive(!) Zahlen folgt:

    int mult(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;
    }

 

[Senftube]

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).

http://www.inf.fu-berlin.de/lehre/SS99/ALP2/material/folienalp2-2.pdf

 

[mihe7]

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.

 

[ocsme]

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 🙁

  int mult(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 ?

LG

 

[Robat]

(a & 1) == 1

Schaut einfach nur ob a ungerade ist 🙂 Bei ungeraden Zahlen ist das 0. Bit immer gesetzt 🙂

 

[mihe7]

@ocsme s. Antwort von @Robat. Du kannst stattdessen z. B. auch (a % 2) != 0 verwenden, wenn Du das darfst.

 

[Xyz1]

int mult(int a, int b) {

@mihe7 woher stammen a und b bei gleichzeitiger Vermeidung der Multiplikation sowie Addition?

 

[mihe7]

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.

Am Beispiel der 6

110 & 001 == 000 == 0
110 & 010 == 010 != 0
110 & 100 == 100 != 0
      ^^^
      links-Shift

110 & 001 == 000 == 0
011 & 001 == 001 != 0
001 & 001 == 001 != 0
^^^
rechts-Shift

Wie man sieht, kommt in beiden Fällen am Ende das gleiche raus.

 

[mihe7]

woher stammen a und b bei gleichzeitiger Vermeidung der Multiplikation sowie Addition?

Ich verstehe die Frage nicht. Das sind einfach zwei Faktoren.

 

[Xyz1]

Ahhhhh, schon verstanden, mult(x,mult(y,z))....

Allerdings hast Du immernoch eine Akkumulierungsinkremtierungsaddition dabei, diese lässt sich auch nich vermeiden. 🙁 (Oder?)

 

[Xyz1]

Ich sollte mir angewöhnen auch mal längere postings zu lesen😀😀

Verständnisproblem meinerseits.... Im sorry

 

[mihe7]

Akkumulierungsinkremtierungsaddition

LOL - wie viel vom guten Zeug hast Du heute schon intus? 😀

 

[Xyz1]

wie viel vom guten Zeug hast Du heute schon intus

Sag ich nicht😛
und nacht

 

[ocsme]

So wollte mich nur nochmal melden und mich Schluss endlich bedanken 🙂
Habe jetzt insgesamt 3 Arten die Aufgabe zu lösen Danke =)