Unlimited Unsigned Integer linked-list implementation. Subtraction not working

Question

So, I have implemented an entire Unlimited Unsigned integer class using a linked-list for a project Euler problem I am working on. I have verified that all of the logical bit operations are correct (though I can post if you want to see them). I have already implemented all operators and operations. However, subtraction (and everything using it, i.e. division and modulus) doesn't work. When I run the following test, this is what I get:

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

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

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

I get the following values from the debugger:

    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

It seems that I have missed something with the definition of subtraction and two's compliment. The code works until I need to add an extra 32 bits. I am accounting for the overflow, from the first 32 to the next 32. However, I am discarding the overflow on the highest bit (as I thought I should). Obviously, I am not doing this correctly. Below is the relevant source code.

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;    
  }
}

Update I finally solved the problem. Here is my blog post along with the source code:

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

Answer 1

After taking two's complement you are adding, which uses zero extension when the widths are not equal. When you extend the subtrahend (now the addend) to be as wide as the minuend, you need to use sign extension, not zero extension. This is because the two's complement value needs to be treated in this context as a negative number (despite everything being unsigned elsewhere). Alternatively (and perhaps more in keeping with the overall design), the subtrahend and minuend must be the same width before starting with the two's complement business.

You're doing something like this:

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

when it should be:

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

or alternatively:

0110 - 10 = 0110 - 0010  <= widths equalized
          = 0110 + (~(0010) + 1)
          = 0110 + (1101 + 1)
          = 0110 + 1110
          = 0100

Answer 2

Once upon a time some engineers at Control Data Corporation (CDC) invented the single cycle adder (before then an adder took one cycle per bit propagating the carry) and CDC patented the invention. Then the engineers were hired by Cray and they wanted a fast adder. So the clever engineers invented the fast look behind borrow subtractor and Cray patented that.

The morale of the story is addition and subtraction are the same thing, and your subtract code should look almost the same as your addition code.