Wie kann ich multiplizieren und dividieren mit nur Bit-Shifting und Addieren?

Wie kann ich multiplizieren und dividieren mit nur Bit-Shifting und Addieren?

   

    Um mit Addieren und Verschieben zu multiplizieren, wollen Sie eine der Zahlen durch 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 Addieren und Verschieben und wieder zurück zerlegt werden. Dies ist auch der Grund, warum die Multiplikation länger dauert als Bit-Verschiebungen oder Additionen - es ist O (n ^ 2) und nicht O (n) in der Anzahl der Bits. Echte Computersysteme (im Gegensatz zu theoretischen Computersystemen) haben eine endliche Anzahl von Bits, so dass die Multiplikation im Vergleich zu Addition und Verschiebung ein konstantes Vielfaches der Zeit benötigt. Wenn ich mich recht erinnere, können moderne processoren, wenn sie richtig pipelined sind, eine Multiplikation fast so schnell wie eine Addition durchführen, indem sie mit der Verwendung der ALUs (arithmetischen Einheiten) im processor herumspielen.

    Die Antwort von Andrew Toulouse kann auf die Division ausgeweitet werden.

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

    Die erste Idee zum Implementieren der Division besteht darin, den inversen Wert des Nenners in der zweiten Basis zu schreiben.

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

    Durch die Kombination der Begriffe in einer offensichtlichen Weise 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 Methoden, um Spaltungen und Reste zu berechnen.

    EDIT1:

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

    EDIT2:

    Eine der schnellsten Methoden zur Division durch Integer-Konstanten besteht darin, die modulare Arithmetik und die Montgomery-Reduktion auszunutzen: Was ist der schnellste Weg, um eine ganze Zahl durch 3 zu teilen?

    X * 2 = 1 Bit Verschiebung nach links
    X / 2 = 1 Bit Verschiebung nach rechts
    X * 3 = verschiebe 1 Bit nach links und füge dann X hinzu

    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 eine Multiplikation durchzufü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 Nicht-Potenz von Zwei zu teilen, ist mir keine einfache Möglichkeit bekannt, es sei denn, Sie möchten eine Low-Level-Logik implementieren, andere binäre Operationen verwenden und eine Art von Iteration verwenden.

    1. Eine Verschiebung nach links um 1 Position ist analog zur Multiplikation mit 2. Eine Verschiebung nach rechts ist analog zur Division durch 2.
    2. Sie können eine Schleife zum Multiplizieren hinzufügen. Indem Sie die Schleifenvariable und die Additionsvariable korrekt auswählen, können Sie die performance begrenzen. Sobald du das erforscht hast, solltest du Bauernvervielfachung verwenden

    Ich übersetzte den Python-Code nach C. Das angegebene Beispiel hatte einen kleinen Fehler. Wenn der Dividendenwert alle 32 Bits aufnahm, würde die Verschiebung fehlschlagen. Ich habe intern nur 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; } 

    Nimm zwei Zahlen, sagen wir 9 und 10, schreibe sie als Binärzahlen – 1001 und 1010.

    Beginnen Sie mit einem Ergebnis, R, von 0.

    Nimm eine der Zahlen, 1010 in diesem Fall, wir nennen es A, und verschiebe es um ein Bit nach rechts, wenn du eine Eins verschiebst, füge die erste Zahl hinzu, wir nennen es B, zu R.

    Verschiebe nun B um ein Bit nach links und wiederhole, bis alle Bits aus A herausgeschoben sind.

    Es ist einfacher zu sehen, was vor sich geht, wenn man es ausgeschrieben sieht, das ist das Beispiel:

      0 0000 0 10010 1 000000 0 1001000 1 ------ 1011010 

    Ein Verfahren zum Dividieren von Ganzzahlen, das Verschiebungen und Additionen verwendet, kann in einfacher Weise aus der Dezimal-Langhand-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 Dezimal- Longhanddivision werden die Ziffern der Dividende von höchst signifikant zu niedrigstwertig, jeweils eine Ziffer, berücksichtigt. Dies wird leicht durch eine Linksverschiebung in der Binärdivision 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 zwei Linksverschiebungen zur Linksverschiebung eines Registerpaares kombiniert. Die obere Hälfte hält den aktuellen Rest, die untere Hälfte hält die Dividende. Wenn die Dividendenbits durch Linksverschiebung zu dem Restregister übertragen werden, werden die unbenutzten niedrigstwertigen Bits der unteren Hälfte verwendet, um die Quotientenbits zu akkumulieren.

    Im Folgenden finden Sie x86-Assembler und C-Implementierungen dieses Algorithmus. Diese spezielle Variante einer Verschiebung & Add Division wird manchmal als “No-Performing” Variante bezeichnet, da die Subtraktion des Divisors vom aktuellen Rest nicht ausgeführt wird, es sei denn, der Rest ist größer oder gleich dem Divisor. In C gibt es keine Vorstellung von dem Übertrags-Flag, das von der Assembly-Version in dem Registerpaar Linksverschiebung verwendet wird. Stattdessen wird es emuliert, basierend auf der Beobachtung, dass das Ergebnis einer Addition modulo 2 n kleiner sein kann, als dass es nur dann addieren würde, wenn es einen Übertrag gab.

     #include  #include  #include  #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 

    Von hier genommen .

    Dies ist nur für die 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; } 

    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 

    Die folgende Methode ist die Implementierung der binären Teilung, wenn beide Zahlen positiv sind. Wenn Subtraktion ein Problem ist, können wir das auch mit binären Operatoren 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> (numbeMaxBit - bits); } 

    Für die 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; i0) { mulResult += (num1 < < i); } } if (isNegativeSign) { mulResult = ((~mulResult)+1); } return mulResult; } 

    Für alle, die sich für eine 16-Bit-x86-Lösung interessieren, gibt es hier ein Stück Code von JasonKnight 1 (er enthält auch ein signiertes Multiplikat, das ich nicht getestet habe). Dieser Code weist jedoch Probleme mit großen Eingängen 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 das Gleiche in GCC Inline-Assembly:

     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" ); 

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