0

そのため、私が取り組んでいるプロジェクト オイラー問題のリンク リストを使用して、Unlimited Unsigned 整数クラス全体を実装しました。すべての論理ビット操作が正しいことを確認しました (見たい場合は投稿できますが)。私はすでにすべての演算子と操作を実装しています。ただし、減算 (およびそれを使用するすべてのもの、つまり除算と剰余) は機能しません。次のテストを実行すると、次のようになります。

  LimitlessUnsigned limitless = 0x88888888u;
  limitless = limitless << 4;

  LimitlessUnsigned tester = 0x88888884u;
  tester = tester << 4;

  //limitless = limitless >> 5;
  LimitlessUnsigned another = limitless - tester;

デバッガーから次の値を取得します。

    another LimitlessUnsigned   
integerList std::__1::list<unsigned int, std::__1::allocator<unsigned int> >    
[0] unsigned int    0b11111111111111111111111111111111
[1] unsigned int    0b00000000000000000000000001000000
limitless   LimitlessUnsigned   
integerList std::__1::list<unsigned int, std::__1::allocator<unsigned int> >    
[0] unsigned int    0b00000000000000000000000000001000
[1] unsigned int    0b10001000100010001000100010000000
tester  LimitlessUnsigned   
integerList std::__1::list<unsigned int, std::__1::allocator<unsigned int> >    
[0] unsigned int    0b00000000000000000000000000001000
[1] unsigned int    0b10001000100010001000100001000000

引き算の定義と2の褒め言葉で何かを見落としていたようです。余分な 32 ビットを追加する必要があるまで、コードは機能します。最初の 32 から次の 32 までのオーバーフローを説明しています。明らかに、私はこれを正しく行っていません。以下は関連するソースコードです。

void LimitlessUnsigned::Sub(const LimitlessUnsigned& other)
{
  if(*this <= other)
  {
    *this = 0u;
    return;
  }

  LimitlessUnsigned temp = other;  

  while(temp.integerList.size() > integerList.size())
    integerList.push_front(0u);

  while(integerList.size() > temp.integerList.size())
  temp.integerList.push_front(0u);  

  temp.TwosComp();  
  Add(temp, true);
}
void LimitlessUnsigned::Add(const LimitlessUnsigned& other, bool allowRegisterLoss)
{
  LimitlessUnsigned carry = *this & other;
  LimitlessUnsigned result = *this ^ other;

  while(carry != 0u)
  {
    carry.ShiftLeft(1, allowRegisterLoss);
    LimitlessUnsigned shiftedcarry = carry;
    carry = result & shiftedcarry;
    result = result ^ shiftedcarry;
  }

 *this = result;
}


void LimitlessUnsigned::Not()
{  
  for(std::list<unsigned>::iterator iter = integerList.begin(); iter != integerList.end(); ++iter)
   {      
      *iter = ~*iter;      
   }   
}

void LimitlessUnsigned::TwosComp()
{
  Not();
  Add(1u, true);
}

void LimitlessUnsigned::ShiftLeft(unsigned shifts, bool allowRegisterLoss)
{
  unsigned carry = 0u;
  bool front_carry = false;

  while(shifts > 0u)
  {    
    if((integerList.front() & CARRY_INT_HIGH) == CARRY_INT_HIGH)
      front_carry = true;     

    for(std::list<unsigned>::reverse_iterator iter = integerList.rbegin(); iter != integerList.rend(); ++iter)
    {      
     unsigned temp = *iter;

      *iter = *iter << 1;
      *iter = *iter | carry;       

      if((temp & CARRY_INT_HIGH) == CARRY_INT_HIGH)
        carry = CARRY_INT;
      else
        carry = 0u;
    }

    carry = 0u;

    if(front_carry && !allowRegisterLoss)
    {
      front_carry = false;
      integerList.push_front(1u);
    }

    --shifts;    
  }
}

更新 私は最終的に問題を解決しました。これが私のブログ投稿とソースコードです。

http://memmove.blogspot.com/2013/04/unlimited-unsigned-integer-in-c.html

4

2 に答える 2

3

2 の補数を取った後、追加します。幅が等しくない場合はゼロ拡張を使用します。減数 (現在は加数) を被減数と同じ幅に拡張する場合は、ゼロ拡張ではなく、符号拡張を使用する必要があります。これは、このコンテキストでは 2 の補数値を負の数として扱う必要があるためです (他の場所ではすべてが符号なしであるにもかかわらず)。あるいは (そしておそらく全体的な設計に合わせて)、2 の補数ビジネスを開始する前に、減数と被減数を同じ幅にする必要があります。

あなたはこのようなことをしています:

0110 - 10 = 0110 + (~(10) + 1)
          = 0110 + (01 + 1)
          = 0110 + 10
          = 0110 + 0010
          = 1000

それがいつあるべきか：

0110 - 10 = 0110 + (~(10) + 1)
          = 0110 + (01 + 1)
          = 0110 + 10
          = 0110 + 1110  <= sign-extended subtrahend
          = 0100

または代わりに：

0110 - 10 = 0110 - 0010  <= widths equalized
          = 0110 + (~(0010) + 1)
          = 0110 + (1101 + 1)
          = 0110 + 1110
          = 0100
于 2013-04-18T03:32:52.803 に答える
0

昔々、Control Data Corporation (CDC) の何人かのエンジニアがシングル サイクル加算器を発明し (それ以前は、加算器はキャリーを伝搬するビットごとに 1 サイクルを要していました)、CDC はこの発明の特許を取得しました。その後、エンジニアは Cray に雇われ、高速加算器が必要になりました。そのため、賢いエンジニアがボロー減算器の背後にある高速ルックを発明し、Cray が特許を取得しました。

話のモラルは足し算と引き算は同じものであり、引き算のコードは足し算のコードとほとんど同じに見えるはずです。

于 2013-04-18T17:12:49.700 に答える