Wie kann ich mit nur Bitverschiebung und Addition multiplizieren und dividieren?

86

Wie kann ich mit nur Bitverschiebung und Addition multiplizieren und dividieren?

Spidfire
quelle
20
Wie Sie es in der Mittelschule auf Papier tun würden, nur mit Binär anstelle von Dezimal.
Pascal Cuoq
1
@mtk: Was fehlt in dieser Antwort ? Suchen Sie nach einer C- oder Assembly-Implementierung, bestimmten Operandenbreiten, einer bestimmten Teilungsmethode (z. B. Wiederherstellen oder Nicht-Wiederherstellen)?
Njuffa
Ist die Subtraktion in Ordnung? Alles scheint abgedeckt zu sein
mksteve
Was ist die Notwendigkeit hinter dieser Frage? CPUs übersetzen Multiplikations- und Divisionsoperationen bereits in Bitverschiebung und Addition oder Subtraktion, und wenn dies der Fall ist, hat der Compiler dies noch nicht getan.
Kelly S. French
@ KellyS.French Nur Neugierde, es ist eher eine Möglichkeit, sich vorzustellen, wie ein Compiler mit einem eingeschränkten Befehlssatz arbeiten kann.
Spidfire

Antworten:

74

Um in Bezug auf das Addieren und Verschieben zu multiplizieren, möchten Sie eine der Zahlen durch Zweierpotenzen wie folgt 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)

( _2bedeutet Basis 2)

Wie Sie sehen können, kann die Multiplikation in Addieren und Verschieben und wieder zurück zerlegt werden. Dies ist auch der Grund, warum die Multiplikation länger dauert als das Verschieben oder Addieren von Bits - es ist O (n ^ 2) anstelle von O (n) in der Anzahl der Bits. Reale Computersysteme (im Gegensatz zu theoretischen Computersystemen) haben eine endliche Anzahl von Bits, so dass die Multiplikation im Vergleich zum Addieren und Verschieben ein konstantes Vielfaches der Zeit in Anspruch nimmt. Wenn ich mich richtig erinnere, können moderne Prozessoren, wenn sie richtig geleitet werden, die Multiplikation genauso schnell wie die Addition durchführen, indem sie mit der Verwendung der ALUs (arithmetischen Einheiten) im Prozessor herumspielen.

Andrew Toulouse
quelle
4
Ich weiß, dass es eine Weile her ist, aber können Sie ein Beispiel mit Teilung geben? Danke
GniruT
42

Die Antwort von Andrew Toulouse kann auf die Teilung ausgedehnt werden.

Die Division durch ganzzahlige Konstanten wird im Buch "Hacker's Delight" von Henry S. Warren (ISBN 9780201914658) ausführlich behandelt.

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

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

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

Indem wir die Begriffe auf offensichtliche 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, Division und Rest zu berechnen.

EDIT1:

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

EDIT2:

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

Viktor Latypov
quelle
Vielen Dank für die Hacker's Delight Referenz!
Alecxe
2
Ähm ja, diese Antwort (Division durch Konstante) ist nur teilweise richtig. Wenn Sie versuchen, '3/3' zu machen, erhalten Sie 0. In Hacker's Delight erklären sie tatsächlich, dass es einen Fehler gibt, den Sie kompensieren müssen. In diesem Fall: b += r * 11 >> 5mit r = a - q * 3. Link: hackersdelight.org/divcMore.pdf Seite 2+.
atlaste
29

X * 2 = 1 Bit Verschiebung nach links
X / 2 = 1 Bit Verschiebung nach rechts
X * 3 = Verschiebung um 1 Bit nach links und addiere dann X.

Kelly S. Französisch
quelle
4
Meinst du add Xfür den letzten?
Mark Byers
1
Es ist immer noch falsch - die letzte Zeile sollte lauten: "X * 3 = 1 Bit nach links verschieben und dann X hinzufügen"
Paul R
1
"X / 2 = 1-Bit-Verschiebung nach rechts", nicht vollständig, rundet auf unendlich ab und nicht auf 0 (für negative Zahlen), was die übliche Implementierung der Division ist (zumindest soweit ich gesehen habe).
Leif Andersen
24

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

Mit diesen Verschiebungen können Sie jede Multiplikationsoperation ausführen. Beispielsweise:

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 teilen, ist mir kein einfacher Weg bekannt, es sei denn, Sie möchten eine Logik auf niedriger Ebene implementieren, andere binäre Operationen verwenden und eine Form der Iteration verwenden.

IVlad
quelle
@IVlad: Wie würden Sie die oben genannten Operationen kombinieren, um beispielsweise durch 3 zu teilen?
Paul R
@ Paul R - stimmt, das ist schwieriger. Ich habe meine Antwort klargestellt.
IVlad
Die Division durch eine Konstante ist nicht zu schwierig (multiplizieren Sie mit der magischen Konstante und dividieren Sie dann durch die Potenz von 2), aber die Division durch eine Variable ist etwas schwieriger.
Paul R
1
sollte nicht x * 14 == x * 16 - x * 2 == (x << 4) - (x << 2) wirklich (x << 4) - (x << 1) sein, da x < <1 multipliziert mit x mit 2?
Alex Spencer
17
  1. Eine Verschiebung nach links um 1 Position entspricht dem Multiplizieren mit 2. Eine Verschiebung nach rechts entspricht dem Teilen durch 2.
  2. Sie können eine Schleife hinzufügen, um sie zu multiplizieren. Wenn Sie die Schleifenvariable und die Additionsvariable richtig auswählen, können Sie die Leistung einschränken. Sobald Sie dies untersucht haben, sollten Sie die Bauernmultiplikation verwenden
Yann Ramin
quelle
9
+1: Aber die Linksverschiebung ist nicht nur analog von 2 zu multiplizieren Es wird von 2. Mindestens bis Überlauf multipliziert ...
Don Roby
Die Schichtteilung liefert falsche Ergebnisse für negative Zahlen.
David
6

Ich habe den Python-Code in C übersetzt. Das angegebene Beispiel hatte einen kleinen Fehler. Wenn der Dividendenwert alle 32 Bits beanspruchen würde, würde die Verschiebung fehlschlagen. Ich habe nur 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;
}
user2954726
quelle
Was ist mit einer negativen Zahl? Ich habe -12345 mit 10 mit Eclipse + CDT getestet, aber das Ergebnis war nicht so gut.
Kenmux
5

Ein Verfahren zum Teilen von ganzen Zahlen, das Verschiebungen und Additionen verwendet, kann auf einfache Weise aus der dezimalen Langhandteilung 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 dezimalen Langhanddivision werden die Ziffern der Dividende eine Ziffer nach der anderen von der signifikantesten zur niedrigstwertigen betrachtet. Dies wird leicht durch eine Verschiebung der binären Teilung nach links erreicht. Außerdem werden Quotientenbits gesammelt, indem die aktuellen Quotientenbits um eine Position nach links verschoben und dann das neue Quotientenbit angehängt werden.

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

Unten finden Sie die x86-Assemblersprache und C-Implementierungen dieses Algorithmus. Diese spezielle Variante einer Shift & Add-Division wird manchmal als "No-Performing" -Variante bezeichnet, da die Subtraktion des Divisors vom aktuellen Rest nur durchgeführt wird, wenn der Rest größer oder gleich dem Divisor ist. In C gibt es keine Vorstellung von dem Übertragsflag, das von der Baugruppenversion in der Linksverschiebung des Registerpaars verwendet wird. Stattdessen wird es emuliert, basierend auf der Beobachtung, dass das Ergebnis eines Additionsmoduls 2 n kleiner sein kann, das entweder nur addiert, wenn es eine Ausführung 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
Njuffa
quelle
@greybeard Danke für den Zeiger, Sie haben Recht, ich habe die Dividende mit dem Quotienten verwechselt. Ich werde es reparieren.
Njuffa
4

Nehmen Sie zwei Zahlen, sagen wir 9 und 10, und schreiben Sie sie als Binärzahlen - 1001 und 1010.

Beginnen Sie mit einem Ergebnis R von 0.

Nehmen Sie eine der Zahlen, in diesem Fall 1010, wir nennen sie A und verschieben sie um ein Bit nach rechts. Wenn Sie eine Eins herausschieben, fügen Sie die erste Zahl hinzu, wir nennen sie B zu R.

Verschieben Sie nun B um ein Bit nach links und wiederholen Sie den Vorgang, bis alle Bits aus A heraus verschoben wurden.

Es ist einfacher zu sehen, was los ist, wenn Sie es ausgeschrieben sehen. Dies ist das Beispiel:

      0
   0000      0
  10010      1
 000000      0
1001000      1
 ------
1011010
Jimmeh
quelle
Dies scheint am schnellsten zu sein, erfordert nur ein wenig zusätzliche Codierung, um die Bits der kleinsten Zahl zu durchlaufen und das Ergebnis zu berechnen.
Hellonearthis
2

Von hier genommen .

Dies ist nur zur Teilung:

int add(int a, int b) {
        int partialSum, carry;
        do {
            partialSum = a ^ b;
            carry = (a & b) << 1;
            a = partialSum;
            b = carry;
        } while (carry != 0);
        return partialSum;
}

int subtract(int a, int b) {
    return add(a, add(~b, 1));
}

int division(int dividend, int divisor) {
        boolean negative = false;
        if ((dividend & (1 << 31)) == (1 << 31)) { // Check for signed bit
            negative = !negative;
            dividend = add(~dividend, 1);  // Negation
        }
        if ((divisor & (1 << 31)) == (1 << 31)) {
            negative = !negative;
            divisor = add(~divisor, 1);  // Negation
        }
        int quotient = 0;
        long r;
        for (int i = 30; i >= 0; i = subtract(i, 1)) {
            r = (divisor << i);
           // Left shift divisor until it's smaller than dividend
            if (r < Integer.MAX_VALUE && r >= 0) { // Avoid cases where comparison between long and int doesn't make sense
                if (r <= dividend) { 
                    quotient |= (1 << i);    
                    dividend = subtract(dividend, (int) r);
                }
            }
        }
        if (negative) {
            quotient = add(~quotient, 1);
        }
        return quotient;
}
Ashish Ahuja
quelle
1

Dies sollte für die Multiplikation funktionieren:

.data

.text
.globl  main

main:

# $4 * $5 = $2

    addi $4, $0, 0x9
    addi $5, $0, 0x6

    add  $2, $0, $0 # initialize product to zero

Loop:   
    beq  $5, $0, Exit # if multiplier is 0,terminate loop
    andi $3, $5, 1 # mask out the 0th bit in multiplier
    beq  $3, $0, Shift # if the bit is 0, skip add
    addu $2, $2, $4 # add (shifted) multiplicand to product

Shift: 
    sll $4, $4, 1 # shift up the multiplicand 1 bit
    srl $5, $5, 1 # shift down the multiplier 1 bit
    j Loop # go for next  

Exit: #


EXIT: 
li $v0,10
syscall
Melsi
quelle
Welcher Geschmack der Montage?
Keith Pinson
1
Es ist eine MIPS-Baugruppe, wenn Sie dies wünschen. Ich glaube, ich habe MARS verwendet, um es zu schreiben / auszuführen.
Melsi
1

Die folgende Methode ist die Implementierung der binären Division, wenn beide Zahlen positiv sind. Wenn die Subtraktion ein Problem darstellt, können wir dies auch mithilfe von Binäroperatoren implementieren.

Code

-(int)binaryDivide:(int)numerator with:(int)denominator
{
    if (numerator == 0 || denominator == 1) {
        return numerator;
    }

    if (denominator == 0) {

        #ifdef DEBUG
            NSAssert(denominator==0, @"denominator should be greater then 0");
        #endif
        return INFINITY;
    }

    // if (numerator <0) {
    //     numerator = abs(numerator);
    // }

    int maxBitDenom = [self getMaxBit:denominator];
    int maxBitNumerator = [self getMaxBit:numerator];
    int msbNumber = [self getMSB:maxBitDenom ofNumber:numerator];

    int qoutient = 0;

    int subResult = 0;

    int remainingBits = maxBitNumerator-maxBitDenom;

    if (msbNumber >= denominator) {
        qoutient |=1;
        subResult = msbNumber - denominator;
    }
    else {
        subResult = msbNumber;
    }

    while (remainingBits > 0) {
        int msbBit = (numerator & (1 << (remainingBits-1)))>0?1:0;
        subResult = (subResult << 1) | msbBit;
        if(subResult >= denominator) {
            subResult = subResult - denominator;
            qoutient= (qoutient << 1) | 1;
        }
        else{
            qoutient = qoutient << 1;
        }
        remainingBits--;

    }
    return qoutient;
}

-(int)getMaxBit:(int)inputNumber
{
    int maxBit = 0;
    BOOL isMaxBitSet = NO;
    for (int i=0; i<sizeof(inputNumber)*8; i++) {
        if (inputNumber & (1<<i)) {
            maxBit = i;
            isMaxBitSet=YES;
        }
    }
    if (isMaxBitSet) {
        maxBit+=1;
    }
    return maxBit;
}


-(int)getMSB:(int)bits ofNumber:(int)number
{
    int numbeMaxBit = [self getMaxBit:number];
    return number >> (numbeMaxBit - bits);
}

Zur Multiplikation:

-(int)multiplyNumber:(int)num1 withNumber:(int)num2
{
    int mulResult = 0;
    int ithBit;

    BOOL isNegativeSign = (num1<0 && num2>0) || (num1>0 && num2<0);
    num1 = abs(num1);
    num2 = abs(num2);


    for (int i=0; i<sizeof(num2)*8; i++)
    {
        ithBit =  num2 & (1<<i);
        if (ithBit>0) {
            mulResult += (num1 << i);
        }

    }

    if (isNegativeSign) {
        mulResult =  ((~mulResult)+1);
    }

    return mulResult;
}
Maulkorb
quelle
Was ist diese Syntax? -(int)multiplyNumber:(int)num1 withNumber:(int)num2?
SS Anne
0

Für alle , in einer Lösung , 16-Bit - x86 interessiert, es ist ein Stück Code , der von JasonKnight hier 1 (er enthält auch eine Multiplikation mit Vorzeichen Stück, das habe ich nicht getestet). Dieser Code weist jedoch Probleme mit großen Eingaben auf, bei denen der Teil "add bx, bx" überlaufen würde.

Die feste Version:

softwareMultiply:
;    INPUT  CX,BX
;   OUTPUT  DX:AX - 32 bits
; CLOBBERS  BX,CX,DI
    xor   ax,ax     ; cheap way to zero a reg
    mov   dx,ax     ; 1 clock faster than xor
    mov   di,cx
    or    di,bx     ; cheap way to test for zero on both regs
    jz    @done
    mov   di,ax     ; DI used for reg,reg adc
@loop:
    shr   cx,1      ; divide by two, bottom bit moved to carry flag
    jnc   @skipAddToResult
    add   ax,bx
    adc   dx,di     ; reg,reg is faster than reg,imm16
@skipAddToResult:
    add   bx,bx     ; faster than shift or mul
    adc   di,di
    or    cx,cx     ; fast zero check
    jnz   @loop
@done:
    ret

Oder dasselbe in der GCC-Inline-Montage:

asm("mov $0,%%ax\n\t"
    "mov $0,%%dx\n\t"
    "mov %%cx,%%di\n\t"
    "or %%bx,%%di\n\t"
    "jz done\n\t"
    "mov %%ax,%%di\n\t"
    "loop:\n\t"
    "shr $1,%%cx\n\t"
    "jnc skipAddToResult\n\t"
    "add %%bx,%%ax\n\t"
    "adc %%di,%%dx\n\t"
    "skipAddToResult:\n\t"
    "add %%bx,%%bx\n\t"
    "adc %%di,%%di\n\t"
    "or %%cx,%%cx\n\t"
    "jnz loop\n\t"
    "done:\n\t"
    : "=d" (dx), "=a" (ax)
    : "b" (bx), "c" (cx)
    : "ecx", "edi"
);
axic
quelle
0

es multipliziert und dividiert im Grunde genommen mit der Grundleistung 2

nach links verschieben = x * 2 ^ y

nach rechts verschieben = x / 2 ^ y

shl eax, 2 = 2 * 2 ^ 2 = 8

shr eax, 3 = 2/2 ^ 3 = 1/4

Karim Baidar
quelle
eaxkann einen Bruchwert wie nicht halten 1/4. (Es sei denn, Sie verwenden einen Festpunkt anstelle einer Ganzzahl, aber das haben Sie nicht angegeben.)
Peter Cordes
-1

Versuche dies. https://gist.github.com/swguru/5219592

import sys
# implement divide operation without using built-in divide operator
def divAndMod_slow(y,x, debug=0):
    r = 0
    while y >= x:
            r += 1
            y -= x
    return r,y 


# implement divide operation without using built-in divide operator
def divAndMod(y,x, debug=0):

    ## find the highest position of positive bit of the ratio
    pos = -1
    while y >= x:
            pos += 1
            x <<= 1
    x >>= 1
    if debug: print "y=%d, x=%d, pos=%d" % (y,x,pos)

    if pos == -1:
            return 0, y

    r = 0
    while pos >= 0:
            if y >= x:
                    r += (1 << pos)                        
                    y -= x                
            if debug: print "y=%d, x=%d, r=%d, pos=%d" % (y,x,r,pos)

            x >>= 1
            pos -= 1

    return r, y


if __name__ =="__main__":
    if len(sys.argv) == 3:
        y = int(sys.argv[1])
        x = int(sys.argv[2])
     else:
            y = 313271356
            x = 7

print "=== Slow Version ...."
res = divAndMod_slow( y, x)
print "%d = %d * %d + %d" % (y, x, res[0], res[1])

print "=== Fast Version ...."
res = divAndMod( y, x, debug=1)
print "%d = %d * %d + %d" % (y, x, res[0], res[1])
swguru.net
quelle
5
Das sieht aus wie Python. Die Frage wurde für die Versammlung und / oder C. gestellt
ungültig