3

C で符号なし固定小数点除算を行うアルゴリズムが必要です。最大 32 ビット ワードを使用できます。

[0..15] の範囲の数値を使用できるようにしながら、整数部分を表すために必要なビット数を最小限に抑えたいと考えています。どうやら最小ビット数は4です。問題は、私が思いついたアルゴリズムが5ビットでしか動作しないことです。剰余を除数と比較し、除数よりも大きくなるまで剰余をシフトするため、除数の最上位ビットが 1 の場合、アルゴリズムは剰余をシフトするだけです (大きくなることはありません)。コードは次のとおりです。

int divu(int a, int b){
   int pt_int, r, pt_frac=0;
   int i;

   pt_int = ((unsigned) a/b) << BITS_FRAC;
   r = (unsigned) a%b;

   for (i=BITS_FRAC; i>=0; i--){
      if ((unsigned) r < b)
         r <<= 1;
      else{
         r -= b;
        pt_frac += 01 << i;
        r <<= 1;
      }
   }
   return pt_int + pt_frac;
}

解決策はあるがコードを理解したくない場合は、投稿してください。:)

例：

1.5 を 2 で割ると、0.75 になります。整数部に 4 ビット、小数部に 28 ビットを使用しているとします。したがって、数字は16進数です。

1.5:    0x18000000
2:      0x20000000
result: 0x0c000000
4

2 に答える 2

3

4.28 の固定小数点数があり、4.28 の数値で割りたいとします。除算後の精度は、分母から分子の精度を引くことで得られるため、単純除算では 4.28 - 4.28 = 0 となり、有効ビットはありません。明らかにこれはうまくいきません。

     1.5  [4.28] 0x18000000 
   / 2.0  [4.28] 0x20000000 
   =  0?  [0.00] 0x00000000

これを行う理想的な方法は、分子を 8.56 に昇格させ (2^28 を掛けて)、64 ビットの除算を行うことです。

                     .   .   .   .
     1.5  [8.56] 0x180000000000000
   / 2.0  [4.28]        0x20000000 
   = 0.75 [4.28]        0x0c000000

本当に 64 ビットの数値を使用できない場合、唯一の選択肢は分母を減らすことです。たとえば、2^14 で除算することにより、半分の精度を使用できます。

     1.5  [4.28] 0x18000000 
   / 2.0  [2.14]     0x8000
   = 0.75 [2.14]     0x3000

次に、結果に同じ係数を掛けて 4.28 の数値に戻すことができます。 0x3000 *(1<<14) = 0x0c000000

この方法では精度がいくらか失われますが、より大きな分子を使用しないと避けられません。たとえば 5.0/3.0 = 1.66667 = 0x1AAAAAA [4.28]、
((5.0<<28)/(3<<14))<<14 = 0x1AAA8000 [4.28] = 1.66662

于 2011-12-14T19:38:17.873 に答える
1

ここで指摘されているように（例：整数に定数の逆数を掛ける）、逆数を掛けることで除算を再実装できます。その後、整数部分を4ビットで表すことができるようになります。

于 2011-12-14T15:30:44.237 に答える