我怎样才能乘以和仅使用位移和添加？

我怎样才能乘以和仅使用位移和添加？

为了在加法和移位方面相乘，你想用两个幂来分解其中的一个数字，如下所示： 

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表示基数2）

正如你所看到的，乘法可以分解为加法和移位再回来。 这也是为什么乘法需要比位移或加法更长的时间 – 它是O（n ^ 2）而不是位数O（n）。 真正的计算机系统（与理论计算机系统相反）具有有限的位数，所以乘法运算的时间与加法和移位相比是恒定的倍数。 如果我记得正确的话，现代处理器，如果stream水线正确的话，可以通过处理器中的ALU（算术单元）的利用来达到乘法的速度。

安德鲁·图卢兹的答案可以扩展到分工。

Henry S.Warren在书“Hacker's Delight”（ISBN 9780201914658）中详细考虑了整数常量的划分。

实行分工的第一个想法是写出基数二的分母的反值。

例如， 1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....

所以，对于32位算术， a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30)

通过明显地组合这些术语，我们可以减less操作的数量：

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

b += (b >> 4)

b += (b >> 8)

b += (b >> 16)

有更多令人兴奋的方法来计算分裂和剩余。

EDIT1：

如果OP意味着任意数的乘法和除法，而不是一个常数的除法，那么这个线程可能是有用的： https : //stackoverflow.com/a/12699549/1182653

EDIT2：

用整数常量除法的最快方法之一是利用模块化algorithm和蒙哥马利减法： 将整数除以3的最快方法是什么？

X * 2 = 1位左移
X / 2 = 1位右移
X * 3 =左移1位，然后添加X.

  1. 左移1位就类似于乘以2.右移类似于除以2。
  2. 你可以添加一个循环来繁殖。 通过正确select循环variables和加法variables，可以限制性能。 一旦你探索了，你应该使用农民增殖

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

您可以使用这些class次来执行任何乘法操作。 例如：

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

除以2的非幂次除数，我不知道任何简单的方法，除非你想要实现一些低级逻辑，使用其他二进制操作，并使用某种forms的迭代。

我将Python代码翻译为C.给出的例子有一个小缺陷。 如果所有32位的股利价值，转移将失败。 我只是在内部使用64位variables来解决这个问题： 

 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; }

拿两个数字，让我们说9和10，把它们写成二进制–1001和1010。

从结果开始，R为0。

取其中一个数字1010，在这种情况下，我们将它称为A，并将其右移一位，如果您移出一个数字，则添加第一个数字，我们将其称为B。

现在将B移到一位，并重复，直到所有位都移出A位。

如果你看到它发生了，那么看看会发生什么更容易，这就是例子： 

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

从这里采取。

这只是划分： 

 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; }

这应该适用于乘法： 

 .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

下面的方法是考虑到两个数字都是正数的情况下二进制分割的实现。 如果减法是一个问题，我们可以使用二元运算符来实现。

码 

 -(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); }

乘法： 

 -(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; }

使用移位和相加的整数除法的程序可以从小学时的小数点分手中直接推导出来。 每个商位的select被简化，因为数字是0和1：如果当前余数大于或等于除数，则部分商的最低有效位为1。

就像十进制分手一样，红利的数字从最重要到最不重要，一次一个数字。 这很容易通过二元分割中的左移来完成。 此外，通过将当前商位左移一个位置，然后附加新商位来收集商位。

在经典的安排中，这两个左移组合成一个寄存器对的左移。 上半部分持有现金余额，下半部分初始持有分红。 当分数位通过左移传送到余数寄存器时，下半部分的未使用的最低有效位用来累加商位。

下面是这个algorithm的x86汇编语言和C实现。 移位和加法除法的这种特定变体有时被称为“不执行”变体，因为除非余数大于或等于除数，否则不执行除数与当前余数的除法。 在C中，寄存器对中的汇编版本没有使用进位标志的概念。 相反，基于观察，模仿2n的结果可以更小，或者只有在进行时才join。 

 #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

对于任何对16位x86解决scheme感兴趣的人来说， JasonKnight在这里有一段代码（他还包括一个我没有testing过的有符号的乘法片）。 但是，该代码有大量input的问题，其中“add bx，bx”部分溢出。

固定版本： 

 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

或者在GCC内联汇编中也是一样的： 

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

尝试这个。 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])
    Interesting Posts

    在Python中创build重复n次单项的列表

    Python列表乘法：] * 3使3个列表相互镜像时修改

    除法结果始终为零

    bsxfun在matrix乘法中的实现

    快速平方平方计算

    奇怪的C＃小数乘法行为

    如何将Python中的所有项目与Python一起使用？

    NumPy Matrix与Array类的乘法有何不同？

    向量乘以matrix的行？

    为什么这两个乘法运算有不同的结果？