Welche Wege gibt es noch binäre Zahlen zu multiplizieren?
Also um binäre Zahlen zu multiplizieren kann man ja zum Beispiel die Standard-Multiplikationsmethode verwenden.
Beispiel: 1111 * 1 0000 0000
Aber gibt es da noch andere Methoden? Etwas was schneller geht? Kann man es vielleicht auch nicht schon irgendwie so ablesen?
1 Antwort
So richtig kommst du an dem wiederholten addieren nicht vorbei. Du musst dir klar machen, wie multiplizieren funktioniert und welche Eigenschaften Binärzahlen haben... Wahrscheinlich wird meine Erklärung alleine nicht zum verstehen ausreichen.
Im Binärsystem ist eine Multiplikation mit 2 das gleiche wie eine Null anhängen, beziehungsweise die Zahl um eine Stelle nach links zu schieben. Alle Potenzen von 2 funktionieren so. Also x*2^n = x000000 mit n Nullen. Vergleiche mit dem Dezimalsystem: Wenn du mit 10 Multiplizierst, werden einfach nur Nullen angehangen.
Was du also machen kannst, ist eine der Multiplikanden in eine Summe aus 2er Potenzen zerlegen (du brauchst nur die 1en). Aus 100101 wird also:
2^0 + 2^2 + 2^5. Die Multiplikation x * 100101 = x* (2^0 + 2^2+2^5) = x*2^0 + x*2^2 + x*2^5...
anders dargestellt:
x
+ x00
+ x00000
x kann eine mehrstellige Zahl sein, hier ist nur die niedrigste Stelle angegeben. So wirklich unterscheidet sich die Rechnung nicht von deiner oberen, aber du kannst die Reihen mit 0en weglassen. Mehr abkürzen ist mir nicht bekannt.
Interessanterweise bedient sich die "Russische Bauernmultiplikation" indirekt des Prinzips. Der eine Muliplikand wird immer verdoppelt (also im Binärsystem eine 0 angehangen), der andere Multiplikand wird indirekt in eine Binärzahl zerlegt...