Wie kann ich multiplizieren und dividieren, indem ich nur Bitverschiebung und Addition verwende?

Wie kann ich multiplizieren und dividieren, indem ich nur Bitverschiebung und Addition verwende?

Um in Bezug auf Addieren und Verschieben zu multiplizieren, möchten Sie eine der Zahlen wie folgt in Zweierpotenzen zerlegen:

21 * 5 = 10101_2 * 101_2             (Initial step)
       = 10101_2 * (1 * 2^2  +  0 * 2^1  +  1 * 2^0)
       = 10101_2 * 2^2 + 10101_2 * 2^0 
       = 10101_2 << 2 + 10101_2 << 0 (Decomposed)
       = 10101_2 * 4 + 10101_2 * 1
       = 10101_2 * 5
       = 21 * 5                      (Same as initial expression)

(_2 bedeutet Basis 2)

Wie Sie sehen können, kann die Multiplikation in Addition und Verschiebung und wieder zurück zerlegt werden. Aus diesem Grund dauert die Multiplikation auch länger als das Verschieben oder Addieren von Bits – es ist O (n ^ 2) und nicht O (n) in der Anzahl der Bits. Reale Computersysteme (im Gegensatz zu theoretischen Computersystemen) haben eine endliche Anzahl von Bits, sodass die Multiplikation im Vergleich zur Addition und Verschiebung ein konstantes Vielfaches an Zeit in Anspruch nimmt. Wenn ich mich richtig erinnere, können moderne Prozessoren bei richtiger Pipeline Multiplikation genauso schnell wie Addition durchführen, indem sie mit der Auslastung der ALUs (Arithmetikeinheiten) im Prozessor herumspielen.

Die Antwort von Andrew Toulouse kann auf Division ausgedehnt werden.

Die Division durch ganzzahlige Konstanten wird ausführlich in dem Buch “Hacker’s Delight” von Henry S. Warren (ISBN 9780201914658) behandelt.

Die erste Idee zur Implementierung der Division besteht darin, den Kehrwert des Nenners in die Basis zwei zu schreiben.

Z.B,
1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....

So,
a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30)
für 32-Bit-Arithmetik.

Indem wir die Begriffe auf naheliegende Weise kombinieren, können wir die Anzahl der Operationen reduzieren:

b = (a >> 2) + (a >> 4)

b += (b >> 4)

b += (b >> 8)

b += (b >> 16)

Es gibt aufregendere Möglichkeiten, Divisionen und Reste zu berechnen.

EDIT1:

Wenn das OP Multiplikation und Division beliebiger Zahlen bedeutet, nicht die Division durch eine konstante Zahl, dann könnte dieser Thread von Nutzen sein: https://stackoverflow.com/a/12699549/1182653

EDIT2:

Eine der schnellsten Möglichkeiten, durch ganzzahlige Konstanten zu dividieren, besteht darin, die modulare Arithmetik und die Montgomery-Reduktion auszunutzen: Was ist der schnellste Weg, eine ganze Zahl durch 3 zu teilen?

X * 2 = 1-Bit-Verschiebung nach links
X / 2 = 1-Bit-Verschiebung nach rechts
X * 3 = 1 Bit nach links verschieben und dann X hinzufügen

x << k == x multiplied by 2 to the power of k
x >> k == x divided by 2 to the power of k

Sie können diese Verschiebungen verwenden, um jede Multiplikationsoperation durchzuführen. Zum Beispiel:

x * 14 == x * 16 - x * 2 == (x << 4) - (x << 1)
x * 12 == x * 8 + x * 4 == (x << 3) + (x << 2)

Um eine Zahl durch eine Zweierpotenz zu dividieren, ist mir kein einfacher Weg bekannt, es sei denn, Sie möchten eine Low-Level-Logik implementieren, andere binäre Operationen verwenden und eine Form der Iteration verwenden.

1. Eine Linksverschiebung um 1 Stelle entspricht einer Multiplikation mit 2. Eine Rechtsverschiebung entspricht einer Division durch 2.
2. Sie können eine Schleife hinzufügen, um zu multiplizieren. Indem Sie die Schleifenvariable und die Additionsvariable richtig auswählen, können Sie die Leistung begrenzen. Sobald Sie das erforscht haben, sollten Sie verwenden Bauernvermehrung

Ein Verfahren zur Division ganzer Zahlen, das Verschiebungen und Additionen verwendet, kann auf einfache Weise von der dezimalen handschriftlichen Division abgeleitet werden, wie sie in der Grundschule gelehrt wird. Die Auswahl jeder Quotientenziffer wird vereinfacht, da die Ziffer entweder 0 oder 1 ist: Wenn der aktuelle Rest größer oder gleich dem Divisor ist, ist das niedrigstwertige Bit des Teilquotienten 1.

Genau wie bei der Dezimaldivision werden die Ziffern des Dividenden von der höchsten bis zur niedrigsten Ziffer betrachtet. Dies wird leicht durch eine Linksverschiebung in der binären Division erreicht. Außerdem werden Quotientenbits gesammelt, indem die aktuellen Quotientenbits um eine Position nach links verschoben werden und dann das neue Quotientenbit angehängt wird.

In einer klassischen Anordnung werden diese beiden Linksverschiebungen zu einer Linksverschiebung eines Registerpaares kombiniert. Die obere Hälfte enthält den aktuellen Rest, die untere Hälfte initial den Dividenden. Da die Dividendenbits durch Linksverschiebung in das Restregister übertragen werden, werden die unbenutzten niedrigstwertigen Bits der unteren Hälfte verwendet, um die Quotientenbits zu akkumulieren.

Nachfolgend finden Sie die x86-Assemblersprache und C-Implementierungen dieses Algorithmus. Diese spezielle Variante einer Shift & Add-Division wird manchmal als “nicht funktionierende” Variante bezeichnet, da die Subtraktion des Divisors vom aktuellen Rest nicht durchgeführt wird, es sei denn, der Rest ist größer oder gleich dem Divisor (Otto Spaniol, „Computerarithmetik: Logik und Design.“ Chichester: Wiley 1981, S. 144). In C gibt es keine Vorstellung von dem Carry-Flag, das von der Assembler-Version in der Linksverschiebung des Registerpaars verwendet wird. Stattdessen wird es emuliert, basierend auf der Beobachtung, dass das Ergebnis einer Addition modulo 2 istⁿ kann nur dann kleiner als jeder Summand sein, wenn es einen Übertrag gab.

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define USE_ASM 0

#if USE_ASM
uint32_t bitwise_division (uint32_t dividend, uint32_t divisor)
{
    uint32_t quot;
    __asm {
        mov  eax, [dividend];// quot = dividend
        mov  ecx, [divisor]; // divisor
        mov  edx, 32;        // bits_left
        mov  ebx, 0;         // rem
    $div_loop:
        add  eax, eax;       // (rem:quot) << 1
        adc  ebx, ebx;       //  ...
        cmp  ebx, ecx;       // rem >= divisor ?
        jb  $quot_bit_is_0;  // if (rem < divisor)
    $quot_bit_is_1:          // 
        sub  ebx, ecx;       // rem = rem - divisor
        add  eax, 1;         // quot++
    $quot_bit_is_0:
        dec  edx;            // bits_left--
        jnz  $div_loop;      // while (bits_left)
        mov  [quot], eax;    // quot
    }            
    return quot;
}
#else
uint32_t bitwise_division (uint32_t dividend, uint32_t divisor)
{
    uint32_t quot, rem, t;
    int bits_left = CHAR_BIT * sizeof (uint32_t);

    quot = dividend;
    rem = 0;
    do {
            // (rem:quot) << 1
            t = quot;
            quot = quot + quot;
            rem = rem + rem + (quot < t);

            if (rem >= divisor) {
                rem = rem - divisor;
                quot = quot + 1;
            }
            bits_left--;
    } while (bits_left);
    return quot;
}
#endif

Ich habe den Python-Code in C übersetzt. Das angegebene Beispiel hatte einen kleinen Fehler. Wenn der Dividendenwert alle 32 Bits belegt, würde die Verschiebung fehlschlagen. Ich habe gerade intern 64-Bit-Variablen verwendet, um das Problem zu umgehen:

int No_divide(int nDivisor, int nDividend, int *nRemainder)
{
    int nQuotient = 0;
    int nPos = -1;
    unsigned long long ullDivisor = nDivisor;
    unsigned long long ullDividend = nDividend;

    while (ullDivisor <  ullDividend)
    {
        ullDivisor <<= 1;
        nPos ++;
    }

    ullDivisor >>= 1;

    while (nPos > -1)
    {
        if (ullDividend >= ullDivisor)
        {
            nQuotient += (1 << nPos);
            ullDividend -= ullDivisor;
        }

        ullDivisor >>= 1;
        nPos -= 1;
    }

    *nRemainder = (int) ullDividend;

    return nQuotient;
}