0

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

  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

4

2 回答 2

3

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

你正在做这样的事情：

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

曾几何时，控制数据公司 (CDC) 的一些工程师发明了单周期加法器（在此之前，加法器需要一个周期来传播进位）并且 CDC 为该发明申请了专利。然后工程师被 Cray 雇佣，他们想要一个快速加法器。所以聪明的工程师发明了借位减法器背后的快速外观，克雷为此申请了专利。

故事的精神是加法和减法是一回事，你的减法代码应该和你的加法代码看起来几乎一样。

于 2013-04-18T17:12:49.700 回答