-1

バイナリ演算用の 3 つの関数を作成する必要がある課題を完了しようとしています。badd() が提供されたので、それを使用して bsub() および bmult() 関数を記述しました。ただし、bdiv() 関数を実行する方法を理解するのに苦労しています。右シフトと bsubb() 関数を使用してビットを反復処理する必要があることはわかっていますが、それを実装する方法がわかりません。以下は、これまでに作成した関数です。私がそれら (bsub() と bmult() を意味する) を書いているときに間違いに気づいたら、私に知らせてください。ありがとう。

/** This function adds the two arguments using bitwise operators. Your      
* implementation should not use arithmetic operators except for loop
* control. Integers are 32 bits long.  This function prints a message
* saying "Overflow occurred\n" if a two's complement overflow occurs
* during the addition process. The sum is returned as the value of
* the function.
*/
int badd(int x,int y){

int i;

char sum;
char car_in=0;
char car_out;
char a,b;

unsigned int mask=0x00000001;
int result=0;

for(i=0;i<32;i++){

  a=(x&mask)!=0;
  b=(y&mask)!=0;
  car_out=car_in & (a|b) |a&b;
  sum=a^b^car_in;

  if(sum) {
     result|=mask;
  }

  if(i!=31) {
     car_in=car_out;
  } else {
     if(car_in!=car_out) {
 printf("Overflow occurred\n");
     }
  }

  mask<<=1;
}

 return result;
 }

// subracts two integers by finding the compliemnt
// of "y", adding 1, and using the badd() function
// to add "-y" and "x"
int bsub(int x, int y){

return badd(x, badd(~y, 1));
}


//add x to total for however many y
int bmult(int x,int y){

int total;
int i;
for(i=0; i < = y; i++)
{
 total = badd(total,x)
}
 return total;
}

// comment me
unsigned int bdiv(unsigned int dividend, unsigned int divisor){

// write me
return 0;
}
4

3 に答える 3

3

ここで言うことはあまりありませんが、基数 2 の基本的な計算にすぎません。

unsigned int bmult(unsigned int x, unsigned int y)
{
    int total = 0;
    int i;

    /* if the i-th bit is non-zero, add 'x' to total */
    /* Multiple total by 2 each step */
    for(i = 32 ; i >= 0 ; i--)
    {
        total <<= 1;
        if( (y & (1 << i)) >> i )
        {
            total = badd(total, x);
        }
    }

    return total;
}

unsigned int bdiv(unsigned int dividend, unsigned int divisor)
{
    int i, quotient = 0, remainder = 0;

    if(divisor == 0) { printf("div by zero\n"); return 0; }

    for(i = 31 ; i >= 0 ; i--)
    {
        quotient <<= 1;
        remainder <<= 1;
        remainder |= (dividend & (1 << i)) >> i;

        if(remainder >= divisor)
        {
            remainder = bsub(remainder, divisor);
            quotient |= 1;
        }
    }

    return quotient;
}

これらのサンプルをコーディングするには、次の 2 つの記事で十分です: DivとMul。

于 2012-10-02T22:48:46.513 に答える
1

次のコードでは、質問と同じ考え方を使用して加算と減算を実装します。唯一の実際的な違いは、私の実装では、これら 2 つの関数もキャリーイン/ボローイン ビットを取り込み、キャリーアウト/ボローアウト ビットを生成することです。

キャリーイン ビットは、加算による減算を実装するために使用されます。このビットは、キャリーアウト ビットとボローアウト ビットの正しい値を取得するのに役立ちます。基本的には、ステータス レジスタのキャリー フラグを使用して、一般的な CPU のような加算と減算を実装します。

次に、キャリー/ボロー ビットを使用して、減算による比較を実装します。演算子を使用せずに比較を実装し>=ます。これは、ビット単位の性質ではないため、算術も考慮します。復元除算アルゴリズムを使用するため、除算関数には比較関数が必要です。

!また、演算子の使用を避け、^1代わりに使用します。

除算関数は、除数を 2 としてunsigned ints、その最上位部分と最下位部分をとります。最後に、最も重要な部分を余りで置き換え、最も重要でない部分を商で置き換えます。したがって、除算とモジュロの両方を実行し、典型的な CPU のような方法 (x86DIV命令など) で実行します。この関数は、成功すると 1 を返し、オーバーフローまたは 0 による除算で 0 を返します。

メイン関数は簡単なテストを行います。除算関数の結果を直接除算の結果と比較し、不一致の場合はエラー メッセージで終了します。

無限ループに陥ることなくunsigned long longdivisor= をテストできるように、テスト部分で使用します。UINT_MAX被除数と除数の値の範囲全体をテストするには時間がかかりすぎる場合がありますUINT_MAX。

コード：

#include <stdio.h>
#include <limits.h>

unsigned add(unsigned a, unsigned b, unsigned carryIn, unsigned* carryOut)
{
  unsigned sum = a ^ b ^ carryIn;
  unsigned carryOuts = a & b | (a | b) & carryIn;
  *carryOut = 0;
  if (sum & (carryOuts << 1))
    sum = add(sum, carryOuts << 1, 0, carryOut);
  else
    sum |= carryOuts << 1;
  *carryOut |= (carryOuts & (UINT_MAX / 2 + 1)) >> (sizeof(unsigned) * CHAR_BIT - 1); // +-*/ are OK in constants
  return sum;
}

unsigned sub(unsigned a, unsigned b, unsigned borrowIn, unsigned* borrowOut)
{
  unsigned diff = add(a, ~b, borrowIn ^ 1, borrowOut);
  *borrowOut ^= 1;
  return diff;
}

unsigned less(unsigned a, unsigned b)
{
  unsigned borrowOut;
  sub(a, b, 0, &borrowOut);
  return borrowOut;
}

int udiv(unsigned* dividendh, unsigned* dividendl, unsigned divisor)
{
  int i;
  unsigned tmp;

  if (less(*dividendh, divisor) ^ 1/* *dividendh >= divisor */)
    return 0; // overflow

  for (i = 0; i < sizeof(unsigned) * CHAR_BIT; i++)
  {
    if (less(*dividendh, UINT_MAX / 2 + 1) ^ 1/* *dividendh >= 0x80...00 */)
    {
      *dividendh = (*dividendh << 1) | (*dividendl >> (sizeof(unsigned) * CHAR_BIT - 1));
      *dividendl <<= 1;

      *dividendh = sub(*dividendh, divisor, 0, &tmp);/* *dividendh -= divisor; */
      *dividendl |= 1;
    }
    else
    {
      *dividendh = (*dividendh << 1) | (*dividendl >> (sizeof(unsigned) * CHAR_BIT - 1));
      *dividendl <<= 1;

      if (less(*dividendh, divisor) ^ 1/* *dividendh >= divisor */)
      {
        *dividendh = sub(*dividendh, divisor, 0, &tmp);/* *dividendh -= divisor; */
        *dividendl |= 1;
      }
    }
  }

  return 1;
}

int udiv2(unsigned* dividendh, unsigned* dividendl, unsigned divisor)
{
  unsigned long long dividend =
    ((unsigned long long)*dividendh << (sizeof(unsigned) * CHAR_BIT)) | *dividendl;

  if (*dividendh >= divisor)
    return 0; // overflow

  *dividendl = (unsigned)(dividend / divisor);
  *dividendh = (unsigned)(dividend % divisor);

  return 1;
}


int main(void)
{
  unsigned long long dividend, divisor;

  for (dividend = 0; dividend <= /*UINT_MAX*/0xFFFF; dividend++)
    for (divisor = 0; divisor <= /*UINT_MAX*/0xFF; divisor++)
    {
      unsigned divh = 0, divl = (unsigned)dividend, divr = (unsigned)divisor;
      unsigned divh2 = 0, divl2 = (unsigned)dividend;

      printf("0x%08X/0x%08X=", divl, divr);

      if (udiv(&divh, &divl, divr))
        printf("0x%08X.0x%08X", divl, divh);
      else
        printf("ovf");

      printf(" ");

      if (udiv2(&divh2, &divl2, divr))
        printf("0x%08X.0x%08X", divl2, divh2);
      else
        printf("ovf");

      if ((divl != divl2) || (divh != divh2))
      {
        printf(" err");
        return -1;
      }

      printf("\n");
    }

  return 0;
}
于 2012-10-03T00:58:05.070 に答える
0
  1. while 被除数 < 除数 商の小数点の後にゼロを追加し、被除数を 1 だけ右にシフトします
  2. ここで、除数のビット数が被除数のビット数と等しいかどうかを確認し、そうでない場合は、被除数のビット数が除数のビット数と等しくなるまで除数を左にシフトします。
  3. ここで、被除数、除数を減算し、商に 1 を追加します。適切な位置に商に 1 があることを確認してください (小数点以下の位置など)。

被除数が 0 または 1 になるまでこのプロセスを繰り返します。

于 2012-10-02T21:02:12.307 に答える