Unlimited Unsigned Integer in C++

For a while now I have been working through Project Euler to keep both my mind sharp and to maintain and improve my C++ skills. C++ is by no means necessary for Project Euler problems, but I have chosen to do all of the problems in C++ when possible for this reason. Anyways, there is a Power Digit Sum question--actually there are several-- and the brute force way of attacking the problem is using an unbounded integer: which the c++ standard library does not implement. So, I set about implementing my own. This is also a very common data structures and algorithms question, so I figured I would go ahead and write my own for the fun of it.  Feel free to reuse this code and improve upon it. If you improve it, however, please submit the patch to me so that I can update my version.

NOTE: It is unethical and against the rules to post solutions to Project Euler problems on any public site. This is not a solution to any Project Euler problems that I know of and is merely a tool that I used in my actual algorithm to solve the problem. 

The design is pretty straight forward. First, I model the data as a simple linked list with the head node as the most significant 32 bits and the tail being the least significant. Then, I implemented all of the bitwise operators. After this, I defined addition using only bit operations, and subtraction using two's complement and addition. Division uses the optimized bit shifts algorithm with subtraction. Multiplication is implemented using peasant multiplication.

Here is the code:

/*
 *Author: Jonathan M. Henson
 *Date: 4/20/2013
 *Description: Linkedlist implementation of an Unlimited Unsigned Integer.
 *
 *This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 */
 
#ifndef LIMITLESS_UNSIGNED_H
#define LIMITLESS_UNSIGNED_H
 
#include <cstdlib>
#include <cstdio>
#include <list>
#include <string>
 
class LimitlessUnsigned
{
public:
  LimitlessUnsigned();
  LimitlessUnsigned(const char* strNumber);
  LimitlessUnsigned(unsigned number);
  LimitlessUnsigned(const LimitlessUnsigned&);
  
  LimitlessUnsigned& operator = (const LimitlessUnsigned&);
  LimitlessUnsigned& operator += (const LimitlessUnsigned&);
  LimitlessUnsigned& operator -= (const LimitlessUnsigned&);
  LimitlessUnsigned& operator *= (const LimitlessUnsigned&);
  LimitlessUnsigned& operator /= (const LimitlessUnsigned&);
  
  LimitlessUnsigned operator << (unsigned) const;
  LimitlessUnsigned operator >> (unsigned) const;
  LimitlessUnsigned operator |  (const LimitlessUnsigned&) const;
  LimitlessUnsigned operator & (const LimitlessUnsigned&) const;
  LimitlessUnsigned operator ^ (const LimitlessUnsigned&) const;
  bool operator > (const LimitlessUnsigned&) const;
  bool operator < (const LimitlessUnsigned&) const;
  bool operator == (const LimitlessUnsigned&) const;
  bool operator <= (const LimitlessUnsigned&) const;
  bool operator >= (const LimitlessUnsigned&) const;
  bool operator != (const LimitlessUnsigned&) const;
  LimitlessUnsigned operator + (const LimitlessUnsigned&) const;
  LimitlessUnsigned operator - (const LimitlessUnsigned&) const;
  LimitlessUnsigned operator * (const LimitlessUnsigned&) const;
  LimitlessUnsigned operator / (const LimitlessUnsigned&) const;
  LimitlessUnsigned operator % (const LimitlessUnsigned&) const;
  LimitlessUnsigned& operator ++ ();
  LimitlessUnsigned operator ++ (int);
  LimitlessUnsigned& operator -- ();
  LimitlessUnsigned operator --(int);
  
  std::string ToString(char format);
  
public:
  std::list<unsigned> integerList;
    
private:
  void ShiftLeft(unsigned shifts, bool allowRegisterLoss = false);
  void ShiftRight(unsigned shifts);
  void LogicalOr(const LimitlessUnsigned&);
  void LogicalAnd(const LimitlessUnsigned&);
  void XOR(const LimitlessUnsigned&);
  void Not();
  void TwosComp();
  bool IsLessThan(const LimitlessUnsigned&) const;
  bool IsGreaterThan(const LimitlessUnsigned&) const;
  bool Equals(const LimitlessUnsigned&) const;
  void Add(const LimitlessUnsigned&, bool allowRegisterLoss = false);
  void Sub(const LimitlessUnsigned&);
  void Mul(const LimitlessUnsigned&);
  void Div(const LimitlessUnsigned&);
  
  static void SetMatchingWidth(std::list<unsigned>&, std::list<unsigned>&);
  static void TrimFront(std::list<unsigned>&);
  
  static LimitlessUnsigned Divide(const LimitlessUnsigned& dividend, const LimitlessUnsigned& divisor);
  static LimitlessUnsigned EfficientBigMod(const LimitlessUnsigned& dividend, const LimitlessUnsigned& divisor);
  
};
 
#endif
 
/*
 *Author: Jonathan M. Henson
 *Date: 4/20/2013
 *Description: Linkedlist implementation of an Unlimited Unsigned Integer.
 *
 *This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. 
 */
 
#include "LimitlessUnsigned.h"
#include <sstream>
#include <iomanip>
 
unsigned CARRY_INT = 0x00000001;
unsigned CARRY_INT_HIGH = 0x80000000;
#define ZERO 0
 
LimitlessUnsigned::LimitlessUnsigned()
{
  unsigned first32 = 0;
  integerList.push_back(first32);
}
 
LimitlessUnsigned::LimitlessUnsigned(const char* strNumber)
{  
  LimitlessUnsigned temp;
  integerList = temp.integerList;
  
  if(!strNumber)
    return;
     
  while(char val = *strNumber++)
  {
    if(val == '-' || val == '+')
      continue;
      
    temp = temp * 10u + ((*strNumber) - '0');
  }
  
  integerList = temp.integerList;
}
 
LimitlessUnsigned::LimitlessUnsigned(unsigned number)
{
  unsigned first32 = number;
  integerList.push_back(first32);
}
 
LimitlessUnsigned::LimitlessUnsigned(const LimitlessUnsigned& other)
{
  integerList = other.integerList;
}
 
LimitlessUnsigned& LimitlessUnsigned::operator = (const LimitlessUnsigned& other)
{
  integerList = other.integerList;
  return *this;
}
 
LimitlessUnsigned& LimitlessUnsigned::operator += (const LimitlessUnsigned& other)
{
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(integerList, tmpOther.integerList);
  Add(tmpOther);
  TrimFront(integerList);
  return *this;
}
 
LimitlessUnsigned& LimitlessUnsigned::operator -= (const LimitlessUnsigned& other)
{
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(integerList, tmpOther.integerList);
  Sub(tmpOther);
  TrimFront(integerList);
  return *this;
}
  
LimitlessUnsigned& LimitlessUnsigned::operator *= (const LimitlessUnsigned& other)
{
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(integerList, tmpOther.integerList);
  Mul(other);
  TrimFront(integerList);
  return *this;
}
  
LimitlessUnsigned& LimitlessUnsigned::operator /= (const LimitlessUnsigned& other)
{
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(integerList, tmpOther.integerList);
  Div(other);
  TrimFront(integerList);
  return *this;
}
 
LimitlessUnsigned LimitlessUnsigned::operator << (unsigned shifts) const
{
  LimitlessUnsigned temp = *this;
  temp.ShiftLeft(shifts, false);
  TrimFront(temp.integerList);
  return temp;
}
 
LimitlessUnsigned LimitlessUnsigned::operator >> (unsigned shifts) const
{
  LimitlessUnsigned temp = *this;
  temp.ShiftRight(shifts);
  TrimFront(temp.integerList);
  return temp;
}
 
LimitlessUnsigned LimitlessUnsigned::operator |  (const LimitlessUnsigned& other) const
{
  LimitlessUnsigned temp = *this;
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(temp.integerList, tmpOther.integerList);
  temp.LogicalOr(tmpOther);
  TrimFront(temp.integerList);
  return temp;
}
 
LimitlessUnsigned LimitlessUnsigned::operator & (const LimitlessUnsigned& other) const
{  
  LimitlessUnsigned temp = *this;
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(temp.integerList, tmpOther.integerList);
  temp.LogicalAnd(tmpOther);
  TrimFront(temp.integerList);
  
  return temp;
}
 
LimitlessUnsigned LimitlessUnsigned::operator ^ (const LimitlessUnsigned& other) const
{
  LimitlessUnsigned temp = *this;
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(temp.integerList, tmpOther.integerList);
  temp.XOR(other);
  TrimFront(temp.integerList);
  
  return temp;
}
 
bool LimitlessUnsigned::operator > (const LimitlessUnsigned& other) const
{
  LimitlessUnsigned temp = *this;
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(temp.integerList, tmpOther.integerList);
  return temp.IsGreaterThan(tmpOther);
}
 
bool LimitlessUnsigned::operator < (const LimitlessUnsigned& other) const
{
  LimitlessUnsigned temp = *this;
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(temp.integerList, tmpOther.integerList);
  return temp.IsLessThan(tmpOther);
}
 
bool LimitlessUnsigned::operator == (const LimitlessUnsigned& other) const
{
  LimitlessUnsigned temp = *this;
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(temp.integerList, tmpOther.integerList);
  return temp.Equals(tmpOther);
}
 
bool LimitlessUnsigned::operator <= (const LimitlessUnsigned& other) const
{
  return *this < other || *this == other;
}
 
bool LimitlessUnsigned::operator >= (const LimitlessUnsigned& other) const
{
  return *this > other || *this == other;  
}
  
bool LimitlessUnsigned::operator != (const LimitlessUnsigned& other) const
{
  return !(*this == other);
}
 
LimitlessUnsigned LimitlessUnsigned::operator + ( const LimitlessUnsigned& other) const
{
  LimitlessUnsigned temp = *this;
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(temp.integerList, tmpOther.integerList);
  temp.Add(tmpOther, false);
  TrimFront(temp.integerList);
  return temp;
}
 
LimitlessUnsigned LimitlessUnsigned::operator * (const LimitlessUnsigned& other) const
{
  LimitlessUnsigned temp = *this;
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(temp.integerList, tmpOther.integerList);
  temp.Mul(tmpOther);
  TrimFront(temp.integerList);
  return temp;
}
 
LimitlessUnsigned LimitlessUnsigned::operator / ( const LimitlessUnsigned& other) const
{
  LimitlessUnsigned temp = *this;
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(temp.integerList, tmpOther.integerList);  
  temp.Div(tmpOther);
  TrimFront(temp.integerList);
  return temp;
}
 
LimitlessUnsigned LimitlessUnsigned::operator % (const LimitlessUnsigned& other) const
{
  LimitlessUnsigned temp = *this;
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(temp.integerList, tmpOther.integerList);
  LimitlessUnsigned retVal = EfficientBigMod(temp, tmpOther);
  TrimFront(temp.integerList);
  
  return retVal;
}
 
LimitlessUnsigned LimitlessUnsigned::operator - (const LimitlessUnsigned& other) const
{
  LimitlessUnsigned temp = *this;
  LimitlessUnsigned tmpOther = other;
  SetMatchingWidth(temp.integerList, tmpOther.integerList);
  temp.Sub(tmpOther);
  TrimFront(temp.integerList);
  
  return temp;
}
 
LimitlessUnsigned& LimitlessUnsigned::operator ++ ()
{  
  *this = *this + 1u;
  return *this;
}
 
LimitlessUnsigned LimitlessUnsigned::operator ++ (int)
{
  LimitlessUnsigned temp = *this;
  *this = *this + 1u;
  
  return temp;
}
 
LimitlessUnsigned& LimitlessUnsigned::operator -- ()
{
  *this = *this - 1u;
  return *this; 
}
  
LimitlessUnsigned LimitlessUnsigned::operator --(int)
{
  LimitlessUnsigned temp = *this;
  *this = *this - 1u;
  
  return temp;
}
 
std::string LimitlessUnsigned::ToString(char format)
{
  std::stringstream ss;    
  
  if(format == 'x' || format == 'h')
  {
      for(std::list<unsigned>::iterator iter = integerList.begin(); iter != integerList.end(); iter++)
      {
        if(format == 'x' || format == 'h')
        {
          ss << std::hex << std::setfill('0') << std::setw (8);
          ss << *iter;
        }
      }
  
    ss.str("0x" + ss.str());
    return ss.str();
  }  
  
  LimitlessUnsigned temp = *this;
  std::string buffer;
  while(temp > 0u)
  {
    buffer = (char)((temp % 10u).integerList.back() + '0') + buffer;
    temp = temp / 10u;  
  }
  
  
  return buffer;
}
 
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;    
  }
}
 
void LimitlessUnsigned::ShiftRight(unsigned shifts)
{
  int carry = 0u;
  
  while(shifts > 0u)
  {
    for(std::list<unsigned>::iterator iter = integerList.begin(); iter != integerList.end(); ++iter)
    {  
      unsigned temp = *iter;
      *iter = *iter >> 1;
      *iter = *iter | carry;
          
      if((temp & CARRY_INT) == CARRY_INT)
        carry = CARRY_INT_HIGH;
      else
        carry = 0u;
    }
    
    --shifts;  
  }
}
 
void LimitlessUnsigned::LogicalOr(const LimitlessUnsigned& other)
{
   std::list<unsigned> cpyOtherList = other.integerList;
    
   std::list<unsigned>::reverse_iterator thisIter = integerList.rbegin();
   
   for(std::list<unsigned>::reverse_iterator iter = cpyOtherList.rbegin(); iter != cpyOtherList.rend(); ++iter)
   {
      *thisIter = *thisIter | *iter;
      ++thisIter;
   }
}
 
void LimitlessUnsigned::LogicalAnd(const LimitlessUnsigned& other)
{
  std::list<unsigned> cpyOtherList = other.integerList;
  
  std::list<unsigned>::reverse_iterator thisIter = integerList.rbegin();
   
   for(std::list<unsigned>::reverse_iterator iter = cpyOtherList.rbegin(); iter != cpyOtherList.rend(); ++iter)
   {
      *thisIter = *thisIter & *iter;
      ++thisIter;
   }  
    
}
 
void LimitlessUnsigned::XOR(const LimitlessUnsigned& other)
{
  std::list<unsigned> cpyOtherList = other.integerList;
  
  std::list<unsigned>::reverse_iterator thisIter = integerList.rbegin();
  
   for(std::list<unsigned>::reverse_iterator iter = cpyOtherList.rbegin(); iter != cpyOtherList.rend(); ++iter)
   {
      *thisIter = *thisIter ^ *iter;
      ++thisIter;
   }
}
 
void LimitlessUnsigned::Not()
{  
  for(std::list<unsigned>::iterator iter = integerList.begin(); iter != integerList.end(); ++iter)
   {      
      *iter = ~*iter;      
   }   
}
 
void LimitlessUnsigned::TwosComp()
{
  LimitlessUnsigned temp = 1u;
  
  SetMatchingWidth(temp.integerList, integerList);
  
  Not();
  Add(temp, true);
}
 
bool LimitlessUnsigned::IsGreaterThan(const LimitlessUnsigned& other) const
{
  if(Equals(other))
    return false;
  
  std::list<unsigned> listCpy = integerList;
  std::list<unsigned>::iterator thisIter = listCpy.begin();
  
  for(std::list<unsigned>::const_iterator iter = other.integerList.begin(); iter != other.integerList.end(); ++iter)
  {
    if(*thisIter > *iter)
      return true;
  
    if(*thisIter < *iter)
      return false;
    
    ++thisIter;
  }
  
  return false;
}
 
bool LimitlessUnsigned::IsLessThan(const LimitlessUnsigned& other) const
{
  if(Equals(other))
    return false;
  
  std::list<unsigned> listCpy = integerList;
  std::list<unsigned>::iterator thisIter = listCpy.begin();  
  
  for(std::list<unsigned>::const_iterator iter = other.integerList.begin(); iter != other.integerList.end(); ++iter)
  {
    if(*thisIter < *iter)
      return true;
    
    if(*thisIter > *iter)
      return false;
    
    ++thisIter;
  }
  
  return false;
}
 
bool LimitlessUnsigned::Equals(const LimitlessUnsigned& other) const
{
  
  std::list<unsigned> listCpy = integerList;
  std::list<unsigned>::iterator thisIter = listCpy.begin();
  
  for(std::list<unsigned>::const_iterator iter = other.integerList.begin(); iter != other.integerList.end(); ++iter)
  {
    if(*thisIter != *iter)
      return false;
    
    ++thisIter;
  }
  
  return true;
}
 
void LimitlessUnsigned::Add(const LimitlessUnsigned& other, bool allowRegisterLoss)
{
  LimitlessUnsigned carry = *this;
  carry = carry & other;
  LimitlessUnsigned result = *this ^ other;
  
  SetMatchingWidth(carry.integerList, result.integerList);
  while(carry != 0u)
  {
    carry.ShiftLeft(1, allowRegisterLoss);
    LimitlessUnsigned shiftedcarry = carry;
    carry = result & shiftedcarry;    
    result = result ^ shiftedcarry;
    SetMatchingWidth(carry.integerList, result.integerList);
  }
  
 *this = result;
}
 
void LimitlessUnsigned::Sub(const LimitlessUnsigned& other)
{
  if(*this <= other)
  {
    *this = 0u;
    return;
  }
  
  LimitlessUnsigned temp = other;  
  
  temp.TwosComp();
  Add(temp, true);
}
  
void LimitlessUnsigned::Mul(const LimitlessUnsigned& other)
{
  LimitlessUnsigned tempOther = other;  
  LimitlessUnsigned prod = 0u;
  
  while(*this > 0u)
  {
    if((*this & 1u) == 1u)
      prod += tempOther;
    
    *this = *this >> 1;
    tempOther = tempOther << 1;
  }
  
  *this = prod;
}
  
void LimitlessUnsigned::Div(const LimitlessUnsigned& other)
{
  *this = Divide(*this, other);
}
 
void LimitlessUnsigned::SetMatchingWidth(std::list<unsigned>& listA, std::list<unsigned>& listB)
{
  while(listA.size() > listB.size())
  {
    listB.push_front(0);
  }
  
  while(listB.size() > listA.size())
  {
    listA.push_front(0);
  }
}
void LimitlessUnsigned::TrimFront(std::list<unsigned>& list)
{
  while(list.size() > 1 && list.front() == 0)
  {
    list.pop_front();
  }
}
 
LimitlessUnsigned LimitlessUnsigned::Divide(const LimitlessUnsigned& dividend, const LimitlessUnsigned& divisor)
{
  LimitlessUnsigned quotient = 1u;
  LimitlessUnsigned temp = divisor;
  
  if(dividend < temp)
  {
    return 0u;
  }
  else if(temp == dividend)
  {
    return 1u;
  }
  
  while(temp <= dividend)
  {
    temp = temp << 1;
    quotient = quotient << 1;
  }
  
  temp = temp >> 1;
  quotient = quotient >> 1;
  
  
  return quotient += Divide(dividend - temp, divisor);
}
 
LimitlessUnsigned LimitlessUnsigned::EfficientBigMod(const LimitlessUnsigned& dividend, const LimitlessUnsigned& divisor)
{
  LimitlessUnsigned quotient = 1u;
  LimitlessUnsigned temp = divisor;
  
  if(dividend < temp)
    return dividend;
  else if(temp == dividend)
    return 0u;
  
  while(temp <= dividend)
  {
    temp = temp << 1;
  }
  
  temp = temp >> 1;
  
  return EfficientBigMod(dividend - temp, divisor);
}