Die Multiplikation zweier (positiver) Ganzzahlen mithilfe von Zweierpotenzen

In diesem Blogeintrag beschäftige ich mich mal mit der Multiplikation von Ganzzahlen.
[infobox]Der Blogeintrag hier ist hauptsächlich an diejenigen gerichtet, denen Mathematik Spaß macht und die auch gerne mal etwas anschauen das sie in der Schule nicht unbedingt lernen.
Die (Hobby-)Programmierer unter uns könnte das übrigens auch interessieren. Und wenn es nur ist um ein wenig mit Code zu spielen :whistling:[/infobox]


[infobox]Hier geht es ausschließlich um die Multiplikation von Ganzzahlen. Kommazahlen werden nicht berücksichtigt.[/infobox]


[infobox]Ich verwende als Multiplikationszeichen das x, da ich gemerkt habe, dass einige das * als Multiplikationszeichen eher verwirrend finden.[/infobox]


Die Multiplikation zweier positiver Ganzzahlen mithilfe von Zweierpotenzen
Das klingt jetzt kompliziert - so kompliziert ist es aber gar nicht.


Das Prinzip
Man hat zwei Faktoren, a und b.
In jedem Schritt schaut man ob b ungerade ist. Falls ja, dann zählt man a zum Ergebnis hinzu. (Das Ergebnis ist am Anfang 0)
Egal ob b gerade oder ungerade - man halbiert b (wobei der Rest wegfällt) und verdoppelt a.



Ein Beispiel
Faktor 1: a = 4
Faktor 2: b = 3
Ergebnis = 0


1) Ist b (3) ungerade? (Ja)
2) Ergebnis = 0 + a = 0 + 4 = 4
3) a = a x 2 = 4 x 2 = 8
4) b = b / 2 = 3 / 2 = 1,5 --> abrunden, b = 1
Wiederholung der Schritte:
5) Ist b (1) ungerade? (Ja)
6) Ergebnis = 4 + a = 4 + 8 = 12
7) a = a x 2 = 8 x 2 = 16
8) b = b / 2 = 1 / 2 = 0,5 --> abrunden, b = 0 --> Ende, da b = 0


4 x 3 = 12



Ein zweites Beispiel
Faktor 1: a = 5
Faktor 2: b = 9
Ergebnis = 0


1) Ist b (9) ungerade? (Ja)
2) Ergebnis = 0 + a = 0 + 5 = 5
3) a = a x 2 = 5 x 2 = 10
4) b = b / 2 = 9 / 2 = 4,5 --> abrunden, b = 4
Wiederholung der Schritte:
5) Ist b (4) ungerade? (Nein)
6) Ergebnis = Ergebnis
7) a = a x 2 = 10 x 2 = 20
8) b = b / 2 = 4 / 2 = 2
Wiederholung der Schritte:
9) Ist b (2) ungerade? (Nein)
10) Ergebnis = Ergebnis
11) a = a x 2 = 20 x 2 = 40
12) b = b / 2 = 2 / 2 = 1
Wiederholung der Schritte:
13) Ist b (1) ungerade? (Ja)
14) Ergebnis = 5 + a = 5 + 40 = 45
15) a = a x 2 = 40 x 2 = 80
16) b = b / 2 = 1 / 2 = 0,5 --> abrunden, b = 0 --> Ende, da b = 0


5 x 9 = 45



Das binäre Zahlensystem
Jetzt wird es etwas komplizierter. Aber eigentlich nicht zu kompliziert.


Unser Zahlensystem basiert auf der Basis 10. Das binäre Zahlensystem auf der Basis 2. Im Bamboo-Club gibt es einen Beitrag von mir in dem das ausführlicher erklärt wird. Wen es interessiert, der kann ja mal dort vorbei schauen: Klick mich


Für den Rest gibt es jetzt einfach mal eine Tabelle:



Noch ein Beispiel
Es folgt wieder ein Beispiel, an dem dann ersichtlich sein sollte wie die Multiplikation funktioniert.


Faktor 1: a = 4 (--> 100)
Faktor 2: b = 5 (--> 101)
Ergebnis = 0


[table='4']
[*] Schritt
[*] Dezimaländerung
[*] Binäränderung
[*] Kommentar


[*] 1
[*] -
[*] -
[*] Ist b (5 ; 101) ungerade? (Ja)


[*] 2
[*] Ergebnis = 0 + a = 0 + 4 = 4
[*] Ergebnis = 100
[*] -


[*] 3
[*] a = a x 2 = 4 x 2 = 8
[*] a = 1000
[*] -


[*] 4
[*] b = b / 2 = 5 / 2 = 2,5 --> abrunden, b = 2
[*] b = 10
[*] -


[*] -
[*] -
[*] -
[*] Wiederholen der Schritte


[*] 5
[*] -
[*] -
[*] Ist b (2 ; 10) ungerade? (Nein]


[*] 6
[*] -
[*] -
[*] Ergebnis bleibt gleich


[*] 7
[*] a = a x 2 = 8 x 2 = 16
[*] a = 10000
[*] -


[*] 8
[*] b = b / 2 = 2 / 2 = 1
[*] b = 1
[*] -


[*] -
[*] -
[*] -
[*] Wiederholen der Schritte


[*] 9
[*] -
[*] -
[*] Ist b (1 ; 1) ungerade? (Ja)


[*] 10
[*] Ergebnis = Ergebnis + a = 4 + 16 = 20
[*] Ergebnis = 10100
[*] -


[*] 11
[*] a = a x 2 = 16 x 2 = 32
[*] a = 100000
[*] -


[*] 12
[*] b = b / 2 = 1 / 2 = 0,5 --> abrunden, b = 0
[*] b = 0
[*] Ende, da b = 0
[/table]


Wie man sehen kann, werden die Ziffern in der binären Darstellung immer um eine Stelle nach rechts (Division durch 2) bzw. links (Multiplikation mit 2) verschoben.
Oder anders - man schaut welche Stelle der binären Darstellung 1 und welche 0 ist.



[infobox]Der Teil ist jetzt hauptsächlich an Programmierer gerichtet[/infobox]


In der Programmierung - bitweise Operatoren
Die meisten höheren Programmiersprachen stellen sogenannte bitweise Operatoren zur Verfügung:


Bitweises Oder:
Setzt alle Bits einer Zahl auf 1 die in einer der beiden verglichenen Zahlen auf 1 gesetzt sind.


Beispiel:

Code
  1. var a = 5 | 9;


In der Variablen steht die Zahl 13, da:

Code
  1. 5 = 0101
  2. 9 = 1001
  3. 13 = 1101



Bitweises Und:
Setzt alle Bits einer Zahl auf 1 die in beiden verglichenen Zahlen auf 1 gesetzt sind.


Beispiel:

Code
  1. var a = 5 & 9


In der Variablen steht die Zahl 1, da:

Code
  1. 5 = 0101
  2. 9 = 1001
  3. 1 = 0001



Bitweises exklusives Oder:
Setzt alle Bits einer Zahl auf 1 die in genau einer der beiden erglichenen Zahlen auf 1 gesetzt sind.


Beispiel:

Code
  1. var a = 5 ^ 9


In der Variablen steht die Zahl 12, da:

Code
  1. 5 = 0101
  2. 9 = 1001
  3. 12 = 1100



Shift:
Verschiebt alle Bits einer Zahl um die angegebenen Stellen nach links oder rechts.


Beispiel:

Code
  1. var a = 5 << 1
  2. var b = 9 >> 1


In der Variablen a steht 10 und in der Variablen b 4, da:

Code
  1. 5 = 0101
  2. 10 = 1010
  3. 9 = 1001
  4. 4 = 0100



Multiplikation in C++, Perl und Python
Gleich vorweg: Ich habe eigentlich noch nie zuvor etwas in C++ geschrieben. Seht mir also bitte Unsauberkeiten nach xD


C++:



Perl:



Python:


Der Python-Code kommt von Farumi



Ja... ich gebe zu... das ist nur Spielerei xD
Aber wenigstens ist es mathematisch interessant :whistling:



Und ich habe auch nichts dagegen wenn mir jemand sagen kann wozu - wenn nicht für Verschlüsselungen, Flags, Spielereien und Prüfen auf ungerade Zahlen - man bitweise Operatoren brauchen kann.

Falls Fragen zu Themen wie der Beitragserstellung bestehen kann man sich gerne an mich wenden :)


Kommentare 4