2

我正在尝试编写以下指令：

交流 <--交流 / 3。

我知道我可以使用算术右移来执行除以 2，但是如何仅使用微程序控制中的可能指令（微指令）执行奇数除法。

谢谢

4

3 回答 3

3

支持 Ira 和 mbratch，我只是在扩展他们的答案，以了解它的工作原理和原因。

它基本上是小学的东西……记住以 10 为底的乘法：

  1234
*   11
=======
  1234  (1*1234)
+12340  (10*1234)
=======
 13574

二进制使这更容易，因为数字只能是 1 或 0 没有 2、3、4 等...

  1111
*   11
=========
  1111 (1*1111)
+11110 (10*1111)
====== 
101101

所以如果我有一些通用位 xyz，然后乘以 5

   xyz
*  101
========
   xyz
+xyz00
=======

因为 5 = 4+1 = 2^2 + 2^0 = 1<<2 + 1<<0 那么一些变量 n*5 = (n<<2) + (n<<0)

1/3 的二进制是多少？那么为什么不使用小学的长除法呢？

      0.01010101
     -----------
   11)1.00000000
      1          bring down the 1
     -0          0 times 3 first digit is a 0
    ==== 
       10        bring down the 0
      -00        0 times 3, second digit is 0
      ====
       100       bring down the 0
      - 11       1 times 3, next digit is a 1
      ====
         10      result 1, bring down 0
        - 0      0 times 3, next digit is a 0
        === 
         100     result is 2, bring down the 0
        - 11     1 times 3, next digit is a 1
        ==== 
           10

并且模式开始重复 0.01010101 ...

因此，如果乘以 5 表示二进制 101*n = (n<<2) + (n<<0)，因为非零位位于 2^0 和 2^2 位置。然后，如果您像我们在上面对 5 所做的那样进行乘法运算，那么是否有小数位并不重要。0.1 是 2 的 -1 次方，0.01 是 2 的 -2 次方，依此类推，二进制 1.01 乘以 N 将是 (n<<0) + (n>>2)。

最后乘以 1/3 近似为 0.0101010101 .... 这意味着

result = (n>>2) + (n>>4) + (n>>6) + ...

正如其他人指出的那样，您可以循环执行此操作，类似于以下内容。

result = 0;
while(n)
{
   n>>=2;
   result+=n;
}

就像在以 10 为底的情况一样，当您除以其中包含因数为 3 的事物时，您会得到一个无限重复的数字，在以 2 为底的情况下，您也会遇到同样的问题，即无限重复的数字。就像以 10 为底的那样，有时您希望 0.6666666 为 0.666667，具体取决于位数，但不是舍入 0.333333，您可能希望舍入除数并在其中有额外的位 0.0101011 或类似的东西。

divthree.c

unsigned int divthree ( unsigned int x )
{
    unsigned int y;

    y=0;
    x<<=16;
    while(x)
    {
        x>>=2;
        y+=x;
    }

// y+=0x8000; //围捕？y>>=16；返回（y）；}

主程序 

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

extern unsigned int divthree ( unsigned int );
unsigned int next_prand ( unsigned int x )
{
    if(x&1)
    {
        x=x>>1;
        x=x^0xBF9EC099;
    }
    else
    {
        x=x>>1;
    }
    return(x);
}
int main ( void )
{
    unsigned int ra,rb,rc,rd,re;
    unsigned int p;

    unsigned int prand;

    prand=0x12345;

    for(ra=0;ra<20;ra++)
    {
        prand=next_prand(prand);
        p=prand&0xFFFF;
        rb=p/3;
        rc=divthree(p);
        rd=divthree(p+1);
        re=divthree(p+2);

        printf("%u %u ",p,rb);
        printf("(%u %d) ",rc,rc-rb);
        printf("(%u %d) ",rd,rd-rb);
        printf("(%u %d) ",re,re-rb);
        printf("\n");
    }
    return(0);
}

所以运行上面，不做四舍五入......

6931 (6931 0) (6931 0) (6932 1) 
19798 (19798 0) (19798 0) (19799 1) 
20822 (20821 -1) (20822 0) (20822 0) 
10411 (10410 -1) (10411 0) (10411 0) 
21640 (21640 0) (21640 0) (21640 0) 
16241 (16241 0) (16241 0) (16242 1) 
13627 (13627 0) (13627 0) (13628 1) 
12224 (12223 -1) (12224 0) (12224 0) 
6112 (6111 -1) (6112 0) (6112 0) 
3056 (3055 -1) (3056 0) (3056 0) 
12450 (12450 0) (12450 0) (12451 1) 
6225 (6225 0) (6225 0) (6225 0) 
3112 (3112 0) (3112 0) (3113 1) 
1556 (1556 0) (1556 0) (1556 0) 
6274 (6274 0) (6274 0) (6274 0) 
8563 (8563 0) (8563 0) (8563 0) 
4281 (4281 0) (4281 0) (4282 1) 
7642 (7642 0) (7642 0) (7642 0) 
20170 (20169 -1) (20170 0) (20170 0) 
10085 (10084 -1) (10085 0) (10085 0)

到目前为止，第二组 divthree(n+1) 是正确的...

为了改进这个无理数的乘法，请注意除法例程如何提供更高的精度（不需要那么极端）假设使用 32 位数学运算的 16 位数字。

不这样做

unsigned int divthree ( unsigned int x )
{
    unsigned int y;

    y=0;
    //x<<=16;
    while(x)
    {
        x>>=2;
        y+=x;
    }
    //y+=0x8000;
    //y>>=16;
    return(y);
}

并不像人们希望的那样准确。

20795 6931 (6928 -3) (6929 -2) (6929 -2) 
59396 19798 (19796 -2) (19796 -2) (19796 -2) 
62466 20822 (20819 -3) (20819 -3) (20820 -2) 
31233 10411 (10408 -3) (10408 -3) (10408 -3) 
64921 21640 (21635 -5) (21635 -5) (21635 -5) 
48725 16241 (16237 -4) (16237 -4) (16237 -4) 
40883 13627 (13622 -5) (13623 -4) (13623 -4) 
36672 12224 (12221 -3) (12221 -3) (12221 -3) 
18336 6112 (6109 -3) (6109 -3) (6109 -3) 
9168 3056 (3053 -3) (3053 -3) (3053 -3) 
37352 12450 (12447 -3) (12447 -3) (12447 -3) 
18676 6225 (6222 -3) (6222 -3) (6222 -3) 
9338 3112 (3109 -3) (3109 -3) (3110 -2) 
4669 1556 (1553 -3) (1553 -3) (1553 -3) 
18823 6274 (6271 -3) (6272 -2) (6272 -2) 
25690 8563 (8560 -3) (8560 -3) (8561 -2) 
12845 4281 (4278 -3) (4278 -3) (4278 -3) 
22927 7642 (7638 -4) (7640 -2) (7640 -2) 
60510 20170 (20165 -5) (20165 -5) (20167 -3) 
30255 10085 (10080 -5) (10082 -3) (10082 -3)

（可以开始欣赏浮点单元为您做什么或不做什么）。

如果您尝试换档，1 后 2 后 3 后 4 档，这与上方的 16 档相匹配。

unsigned int divthree ( unsigned int x )
{
    unsigned int y;

    y=0;
    x<<=4;
    while(x)
    {
        x>>=2;
        y+=x;
    }
    y>>=4;
    return(y);
}

根据您的数字或指令集/寄存器，您将需要额外的 4 位空间。

因此，任何时候您想乘以（或除以）一个在编译时/之前已知的常数，您都可以使用这种简单的移位和加法方法。但是如果除法是无理数，则必须处理准确性。

于 2013-09-15T22:25:32.063 回答
3

另一个答案建议除以二，乘以 2/3。

如果您可以乘以 2/3，则可以轻松乘以 1/3（1/3 = .0101010101.. 二进制）并跳过除以 2。

要乘以 1/3，您可以将被除数右移两个位置（对应于乘以 0.01！）并添加到累加器。重复乘法（呃，右移两次，乘以 0.0001，.000001，...）并根据需要添加尽可能多的次数，以处理您期望被除数具有的最大位数。小心“落到最后”的股息位；您要么需要一个双精度移位器/累加器，要么需要在开始避免精度损失之前将除数按与位数相对应的 2 的正幂来缩放，假设您有足够的备用位。

除以其他常数可以通过乘以构成它们倒数的位来完成。它不是很整洁，但想法是一样的。您可以找出一个变体，它在除以常数后计算模（余数）。这两个也是编译器生成的代码中的常见技巧。

于 2013-09-15T21:10:12.577 回答
3

要除以 3，2首先除以，然后乘以2/3。在二进制中，2/3是0.101010101.... 如果您具有转接携带能力，您可以：

  1. Q <- 红利 SHR 2（红利除以 2）
  2. 将值 Q 乘以 1010101010101010 乘以移位/加法循环，得到 32 位 Q 值（顶部 16 位字和底部 16 位字）
  3. 测试低 16 位字的高位。如果是1，则添加1到 Q 的高 16 位字
  4. 的商Dividend/3是 Q 的前 16 位字

不过，这有点转移和添加。此外，您可能需要1010101010101011而不是1010101010101010由于四舍五入。我在 Ruby 中快速建模了这个方法，它似乎适用于几个简单的案例。

您也许还可以对二进制运行直接除法算法（通过进位、比较、减法...）11转换为Dividend. 为此，您需要几个备用寄存器。但它可用于任何除数，而不仅仅是3. div这只是对指令进行微编码。

于 2013-09-15T19:02:42.440 回答