当前位置： 文江博客话题详情

如何仅使用位移位和加法进行乘法和除法？

发布于 2024-08-31 19:44:58 字数 26 浏览 8 评论 0原文

如何仅使用位移位和加法进行乘法和除法？

原文

How can I multiply and divide using only bit shifting and adding?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（15）

囍笑 2024-09-07 19:44:58

要以加法和移位的方式进行乘法，您需要将其中一个数字分解为 2 的幂，如下所示：（

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)。真实的计算机系统（与理论计算机系统相反）的位数是有限的，因此与加法和移位相比，乘法需要恒定倍数的时间。如果我没记错的话，现代处理器如果流水线处理得当，通过扰乱处理器中 ALU（算术单元）的利用率，可以像加法一样快地执行乘法。

To multiply in terms of adding and shifting you want to decompose one of the numbers by powers of two, like so:

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 means base 2)

As you can see, multiplication can be decomposed into adding and shifting and back again. This is also why multiplication takes longer than bit shifts or adding - it's O(n^2) rather than O(n) in the number of bits. Real computer systems (as opposed to theoretical computer systems) have a finite number of bits, so multiplication takes a constant multiple of time compared to addition and shifting. If I recall correctly, modern processors, if pipelined properly, can do multiplication just about as fast as addition, by messing with the utilization of the ALUs (arithmetic units) in the processor.

回复 原文
裂开嘴轻声笑有多痛 2024-09-07 19:44:58

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

Henry S. Warren 所著的《Hacker's Delight》（ISBN 9780201914658）一书中详细讨论了整数常量除法。

实现除法的第一个想法是在基数 2 中写出分母的倒数。

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

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

通过以明显的方式组合这些项，我们可以减少运算次数：

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

b += (b >> 4)

b += (b >> 8)

b += (b >> 16)

还有更多精彩计算除法和余数的方法。

EDIT1：

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

编辑2：

除以整数常量的最快方法之一是利用模算术和蒙哥马利约简：将整数除以 3 的最快方法是什么？

The answer by Andrew Toulouse can be extended to division.

The division by integer constants is considered in details in the book "Hacker's Delight" by Henry S. Warren (ISBN 9780201914658).

The first idea for implementing division is to write the inverse value of the denominator in base two.

E.g.,
1/3 = (base-2) 0.0101 0101 0101 0101 0101 0101 0101 0101 .....

So,
a/3 = (a >> 2) + (a >> 4) + (a >> 6) + ... + (a >> 30)
for 32-bit arithmetics.

By combining the terms in an obvious manner we can reduce the number of operations:

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

b += (b >> 4)

b += (b >> 8)

b += (b >> 16)

There are more exciting ways to calculate division and remainders.

EDIT1:

If the OP means multiplication and division of arbitrary numbers, not the division by a constant number, then this thread might be of use: https://stackoverflow.com/a/12699549/1182653

EDIT2:

One of the fastest ways to divide by integer constants is to exploit the modular arithmetics and Montgomery reduction: What's the fastest way to divide an integer by 3?

回复 原文
不顾 2024-09-07 19:44:58

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

X * 2 = 1 bit shift left
X / 2 = 1 bit shift right
X * 3 = shift left 1 bit and then add X

回复 原文
纵山崖 2024-09-07 19:44:58

<代码>x << k == x 乘以 2 的 k 次方
x>> k == x 除以 2 的 k 次方

您可以使用这些移位来执行任何乘法运算。例如：

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

要将数字除以 2 的非幂，我不知道有什么简单的方法，除非您想实现一些低级逻辑，使用其他二进制运算并使用某种形式的迭代。

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

You can use these shifts to do any multiplication operation. For example:

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

To divide a number by a non-power of two, I'm not aware of any easy way, unless you want to implement some low-level logic, use other binary operations and use some form of iteration.

回复 原文
送舟行 2024-09-07 19:44:58
  1. 左移 1 位类似于乘以 2。右移类似于除以 2。
  2. 您可以在循环中添加来进行乘法。通过正确选择循环变量和加法变量，您可以限制性能。一旦你探索了这一点，你应该使用农民乘法
  1. A left shift by 1 position is analogous to multiplying by 2. A right shift is analogous to dividing by 2.
  2. You can add in a loop to multiply. By picking the loop variable and the addition variable correctly, you can bound performance. Once you've explored that, you should use Peasant Multiplication
回复 原文
与他有关 2024-09-07 19:44:58

使用移位和加法的整数除法过程可以直接从小学中教授的十进制普通除法导出。每个商位的选择都得到了简化，因为该位要么是 0，要么是 1：如果当前余数大于或等于除数，则部分商的最低有效位为 1。

与十进制普通除法一样，股息的数字按从最高有效位到最低有效位的顺序考虑，一次一位数字。这可以通过二进制除法的左移轻松完成。此外，通过将当前商位左移一位，然后附加新的商位来收集商位。

在经典布置中，这两个左移被组合成一对寄存器的左移。上半部分保存当前余额，下半部分初始保存股息。当被除数位通过左移传送到余数寄存器时，下半部分未使用的最低有效位用于累加商位。

下面是该算法的 x86 汇编语言和 C 实现。这种特殊的转变和变体加除法有时被称为“非执行”变体，因为除非余数大于或等于除数，否则不会执行从当前余数中减去除数的操作（Otto Spaniol，“计算机算术：逻辑与设计”） ” Chichester：Wiley 1981，第 144 页）。在 C 语言中，寄存器对左移中没有汇编版本使用的进位标志的概念。相反，它是基于以下观察进行模拟的：仅当存在进位时，模 2n 的加法结果才能小于任一加数。

#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

A procedure for dividing integers that uses shifts and adds can be derived in straightforward fashion from decimal longhand division as taught in elementary school. The selection of each quotient digit is simplified, as the digit is either 0 and 1: if the current remainder is greater than or equal to the divisor, the least significant bit of the partial quotient is 1.

Just as with decimal longhand division, the digits of the dividend are considered from most significant to least significant, one digit at a time. This is easily accomplished by a left shift in binary division. Also, quotient bits are gathered by left shifting the current quotient bits by one position, then appending the new quotient bit.

In a classical arrangement, these two left shifts are combined into left shifting of one register pair. The upper half holds the current remainder, the lower half initial holds the dividend. As the dividend bits are transferred to the remainder register by left shift, the unused least significant bits of the lower half are used to accumulate the quotient bits.

Below is x86 assembly language and C implementations of this algorithm. This particular variant of a shift & add division is sometimes referred to as the "non-performing" variant, as the subtraction of the divisor from the current remainder is not performed unless the remainder is greater than or equal to the divisor (Otto Spaniol, "Computer Arithmetic: Logic and Design." Chichester: Wiley 1981, p. 144). In C, there is no notion of the carry flag used by the assembly version in the register pair left shift. Instead, it is emulated, based on the observation that the result of an addition modulo 2n can be smaller that either addend only if there was a carry out.

#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
回复 原文
小草泠泠 2024-09-07 19:44:58

我将 Python 代码翻译成 C。给出的示例有一个小缺陷。如果被除数值占用了全部32位，则移位会失败。我只是在内部使用 64 位变量来解决这个问题：

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

I translated the Python code to C. The example given had a minor flaw. If the dividend value that took up all the 32 bits, the shift would fail. I just used 64-bit variables internally to work around the problem:

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;
}
回复 原文
独﹏钓一江月 2024-09-07 19:44:58

取两个数字，比如 9 和 10，将它们写为二进制 - 1001 和 1010。

从结果 R 开始，为 0。

取其中一个数字，在本例中为 1010，我们将其称为 A，然后将其移位右移一位，如果移出一个 1，则添加第一个数字，我们将其称为 B，到 R。

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

更容易看到如果你看到它写出来，发生了什么事，这是例子：

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

Take two numbers, lets say 9 and 10, write them as binary - 1001 and 1010.

Start with a result, R, of 0.

Take one of the numbers, 1010 in this case, we'll call it A, and shift it right by one bit, if you shift out a one, add the first number, we'll call it B, to R.

Now shift B left by one bit and repeat until all bits have been shifted out of A.

It's easier to see what's going on if you see it written out, this is the example:

      0
   0000      0
  10010      1
 000000      0
1001000      1
 ------
1011010
回复 原文
維他命╮ 2024-09-07 19:44:58

摘自此处。

这仅适用于除法：

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

Taken from here.

This is only for division:

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;
}
回复 原文
梦在夏天 2024-09-07 19:44:58

这应该适用于乘法：

.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

This should work for multiplication:

.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
回复 原文
与之呼应 2024-09-07 19:44:58

下面的方法是考虑到两个数字都是正数的二进制除法的实现。如果需要考虑减法，我们也可以使用二元运算符来实现。

代码：

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

The below method is the implementation of binary divide considering both numbers are positive. If subtraction is a concern we can implement that as well using binary operators.

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

For multiplication:

-(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;
}
回复 原文
黯然 2024-09-07 19:44:58

它基本上是与基数幂 2 相乘和除法 2

左移 = x * 2 ^ y

右移 = x / 2 ^ y

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

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

it is basically multiplying and dividing with the base power 2

shift left = x * 2 ^ y

shift right = x / 2 ^ y

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

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

回复 原文
终陌 2024-09-07 19:44:58

对于任何对 16 位 x86 解决方案感兴趣的人，这里有一段由 JasonKnight 编写的代码1 （他还包括一个带符号的乘法片段，我还没有测试过）。但是，该代码在处理大输入时存在问题，其中“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"
);

For anyone interested in a 16-bit x86 solution, there is a piece of code by JasonKnight here1 (he also includes a signed multiply piece, which I haven't tested). However, that code has issues with large inputs, where the "add bx,bx" part would overflow.

The fixed 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

Or the same 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"
);
回复 原文
≈。彩虹 2024-09-07 19:44:58

您可以使用以下公式将某些*乘法/除法语句转换为位移位运算：

x * y = x << log2(y)
x / y = x >> log2(y)

* 假设 y 是 2 的幂

示例：

4 * 16    = 4 << 4
2000 / 4  = 2000 >> 2
288 / 32  = 288 >> 5

You can convert some* multiplication/division statements to bit shift operations using the formulae:

x * y = x << log2(y)
x / y = x >> log2(y)

* Assuming y is a power of 2

Examples:

4 * 16    = 4 << 4
2000 / 4  = 2000 >> 2
288 / 32  = 288 >> 5
回复 原文
嘿咻 2024-09-07 19:44:58

因此，要获得变量除法所需的位，需要除法本身。

它是 MSB/DIVIDER - 是转移除法所需的权力位，它最终是一个先有鸡还是先有蛋的问题。

这有点奇怪，但是->

如果将系统中的所有其他数字相乘，实际上就是将其中一个数字除以其他数字。

然后，如果您在最低有效位处有任何零填充，则将整个系统移回原位。

也就是说，如果你不能忍受其中有条件的除法，如果你的方程只有不到 5 个数字，你的运行还不错，但我知道它还不是最好的解决方案......但我会保留思维。

So to get the bits required for the variable divide requires a divide itself.

its the msb/DIVIDER - is the bits of the powers required for the shifting of the divide, and it ends being a chicken and egg problem.

Its a bit strange but->

If you multiply all the other numbers of your system, you've essentially divided that one number compared to the rest.

then just shift the whole system back if you got any zero padding at the lsb's.

Thats if u cant stand the division method with the condition in it, if theres only less than 5 numbers to your equation your running its not too bad to do, but I know its not the best solution yet... but i'll keep thinking.

回复 原文
~没有更多了~

关于作者

心头的小情儿

暂无简介

0 文章
0 评论
22 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

烙印

文章 0 评论 0

singlesman

文章 0 评论 0

给自己一个微笑

文章 0 评论 0

独孤求败

文章 0 评论 0

晨钟暮鼓

文章 0 评论 0

我是自愿种绣球花的

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文