c++ - 无限无符号整数链表实现。减法不起作用

Question

因此，我已经使用链表为我正在处理的项目 Euler 问题实现了一个完整的无限制无符号整数类。我已经验证了所有逻辑位操作都是正确的(如果你想看的话我可以发布)。我已经实现了所有运营商和操作。但是，减法(以及所有使用它的东西，即除法和模数)不起作用。当我运行以下测试时，这就是我得到的:

  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

我好像漏掉了减法和补码的定义。该代码一直有效，直到我需要添加额外的 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

Answer 1

在取二进制补码后添加，当宽度不相等时使用零扩展。当您将减数(现在是加数)扩展为与被减数一样宽时，您需要使用符号扩展，而不是零扩展。这是因为在这种情况下需要将二进制补码值视为负数(尽管其他地方的所有内容都是无符号的)。或者(也许更符合整体设计)，减数和被减数的宽度必须相同，然后才能开始补码业务。

你正在做这样的事情:

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