clb79a

#ifndef BIGINT_H
#define BIGINT_H

#include <iostream>
#include <sstream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <boost/dynamic_bitset.hpp>
#include <stdexcept>

/*
The BigInt class provides an extension of the built-in integral types to integers
of arbitrary size.  Constructors are implemented from the built-in integral
types together with a string constructor.  The format for a valid string is

    "[ base identifier ][ sign ] number "

    base identifiers can be:

        'b' or 'B' for binary
        'x' or 'X' for hex
        'd' or 'D' for decimal

    sign can be '+' or '-'

A string with no base identifier defaults to decimal and no sign defaults
to positive.  The internal storage mode is binary using Boost dynamic_bitset.

A fairly full set of assignment, compound assignment and comparison operators
has been implemented together with overloads of the output and input operators.
The following maniputlators have been defined for the output operator:

    bigintbin
    bigintdec
    biginthex
    bigintupper
    bigintlower
    bigintshowbase
    bigintnoshowbase
    bigintdefault

The default is bigintnoshowbase bigintdecimal.


Manipulators for the input operator are:

    bigintbin
    bigintdec
    biginthex
    bigintdefault

The default is decimal.  The input manipulators only affect the treatment of
a string with no base identifier.  Formatted strings  that include a base
identifier can be correctly input without regard to any maniputlators set.

Exceptions:

The string constructor will throw std::invalid_argument if passed an invalid
string.  The offending string is incorporated into the what() message.
Strings can be tested by calling the function isValidBigIntString().
The assignment operator which takes a string for lhs may also throw because
it call the BigInt string constructor implicitly.

An attempted to divide by zero will throw std::domain_error.
*/


class BigInt
{
public:
    BigInt();
    BigInt( unsigned long n );
    BigInt( signed long n );
    BigInt( int n );
    BigInt( const std::string& s );

    // assignment operators
    BigInt&   operator= ( const unsigned long& rhs );
    BigInt&   operator= ( const signed long& rhs );
    BigInt&   operator= ( const int& rhs );
    BigInt&   operator= ( const std::string& rhs );
    BigInt&   operator= ( const char*& rhs );

    // unary operators
    BigInt  operator+ () const;
    BigInt  operator- () const;

    // compound assignment operators
    const BigInt& operator+= ( const BigInt& rhs );
    const BigInt& operator-= ( const BigInt& rhs );
    const BigInt& operator*= ( const BigInt& rhs );
    const BigInt& operator/= ( const BigInt& rhs );
    const BigInt& operator%= ( const BigInt& rhs );

    void divisionAndRemainder( const BigInt& divisor, BigInt& quotient, BigInt& remainder ) const;

    // increment and decrement operators
    BigInt& operator++ ();
    BigInt  operator++ ( int );
    BigInt& operator-- ();
    BigInt  operator-- ( int );

    void swap( BigInt& bi );

    // conversion functions
    // These conversion functions strip leading but not a terminal zero.  They
    // operate on strings not BigInts.  They should not contain a '+' or '-'.
    static std::string decToHex( const std::string& s );
    static std::string hexToDec( const std::string& s );

    static std::string decToBin( const std::string& s );
    static std::string binToDec( const std::string& s );

    static std::string hexToBin( const std::string& s );
    static std::string binToHex( const std::string& s );

    static void stripLeadingZeroesFromString( std::string& s );

    static bool isValidBigIntString( const std::string& s );

    static const long int getOutputWordIndex();
    static const long int getInputWordIndex();


private:
    boost::dynamic_bitset<> x_;
    bool negative_;

    // flags for manipulating input and output streams
    enum BigIntBase { def = 0, dec = 1, bin = 2, hex = 4, uppercase = 8, showbase = 15,
        nodec = 30, nobin = 29, nohex = 27, lowercase = 23, noshowbase = 16 };

        //  noshowbase uppercase  hex  bin  dec
        //      0          0       0    0    1     dec = 1
        //      0          0       0    1    0     bin = 2
        //      0          0       1    0    0     hex = 4            OR with outputWordIndex_
        //      0          1       0    0    0     uppercase = 8      or inputWordIndex_ to set
        //      1          0       0    0    0     noshowbase  = 16

        //      1          1       1    1    0     nodec = 30
        //      1          1       1    0    1     nobin = 29
        //      1          1       0    1    1     nohex = 27         AND with outputWordIndex_
        //      1          0       1    1    1     lowercase = 23     or inputWordIndex_ to clear
        //      0          1       1    1    1     showbase = 15

        //      0          0       0    0    0     def = 0 the default, interpreted as decimal and noshowbase
        //      0          0       0    0    1     equivalent to the default


    void stripLeadingZeroes( boost::dynamic_bitset<>& db );
    void compoundAddAssignIgnoreSign( const BigInt& rhs, boost::dynamic_bitset<>::size_type startIndex = 0 );

    static const long int outputWordIndex_;
    static const long int inputWordIndex_;


    // friends
    friend bool operator<  ( const BigInt& lhs, const BigInt& rhs );
    friend bool operator<= ( const BigInt& lhs, const BigInt& rhs );
    friend bool operator== ( const BigInt& lhs, const BigInt& rhs );
    friend bool operator!= ( const BigInt& lhs, const BigInt& rhs );
    friend bool operator>= ( const BigInt& lhs, const BigInt& rhs );
    friend bool operator>  ( const BigInt& lhs, const BigInt& rhs );

    friend std::ostream& operator<< ( std::ostream& os, const BigInt& bi );
    friend std::istream& operator>> ( std::istream& is, BigInt& bi );

    // output stream manipulators
    friend std::ostream& bigintbin( std::ostream& os );
    friend std::ostream& bigintdec( std::ostream& os );
    friend std::ostream& biginthex( std::ostream& os );
    friend std::ostream& bigintupper( std::ostream& os );
    friend std::ostream& bigintlower( std::ostream& os );
    friend std::ostream& bigintshowbase( std::ostream& os );
    friend std::ostream& bigintnoshowbase( std::ostream& os );
    friend std::ostream& bigintdefault( std::ostream& os );

    // input stream manipulators
    friend std::istream& bigintbin( std::istream& is );
    friend std::istream& bigintdec( std::istream& is );
    friend std::istream& biginthex( std::istream& is );
    friend std::istream& bigintdefault( std::istream& is );

};

// comparison operators
bool operator<  ( const BigInt& lhs, const BigInt& rhs );
bool operator<= ( const BigInt& lhs, const BigInt& rhs );
bool operator== ( const BigInt& lhs, const BigInt& rhs );
bool operator!= ( const BigInt& lhs, const BigInt& rhs );
bool operator>= ( const BigInt& lhs, const BigInt& rhs );
bool operator>  ( const BigInt& lhs, const BigInt& rhs );


// binary arithmetic operators
BigInt operator+ ( const BigInt& lhs, const BigInt& rhs );
BigInt operator- ( const BigInt& lhs, const BigInt& rhs );
BigInt operator* ( const BigInt& lhs, const BigInt& rhs );
BigInt operator/ ( const BigInt& lhs, const BigInt& rhs );
BigInt operator% ( const BigInt& lhs, const BigInt& rhs );


std::ostream& operator<< ( std::ostream& os, const BigInt& bi );
std::istream& operator>> ( std::istream& is, BigInt& bi );

// output stream manipulators
std::ostream& bigintbin( std::ostream& os );
std::ostream& bigintdec( std::ostream& os );
std::ostream& biginthex( std::ostream& os );
std::ostream& bigintupper( std::ostream& os );
std::ostream& bigintlower( std::ostream& os );
std::ostream& bigintdefault( std::ostream& os );

// input stream manipulators
std::istream& bigintbin( std::istream& is );
std::istream& bigintdec( std::istream& is );
std::istream& biginthex( std::istream& is );
std::istream& bigintdefault( std::istream& is );


// BigInt Math functions
BigInt factorial( const BigInt& n );

#endif


// ******************  Begin BigInt.hpp  **************************

#include "BigInt.h"

const long int BigInt::outputWordIndex_ = std::ios::xalloc();
const long int BigInt::inputWordIndex_  = std::ios::xalloc();

const long int BigInt::getOutputWordIndex()
{
    return outputWordIndex_;
}

const long int BigInt::getInputWordIndex()
{
    return inputWordIndex_;
}



BigInt::BigInt() : x_( std::string( "0" ) ), negative_( false )
{
}


BigInt::BigInt( unsigned long n ) : x_( sizeof( unsigned long ) * 8, n ), negative_( false )
{
    stripLeadingZeroes( x_ );
}


BigInt::BigInt( signed long n ) : x_( sizeof( unsigned long ) * 8, ( n < 0 ? static_cast< unsigned long >( -( n + 1 )  ) + 1 : static_cast< unsigned long >( n ) ) ),
    negative_( n < 0 ? true : false )
{
    stripLeadingZeroes( x_ );
}


BigInt::BigInt( int n ) : x_( sizeof( int ) * 8, ( n < 0 ? static_cast< unsigned int >( -( n + 1 ) ) + 1  : static_cast< unsigned int >( n ) ) ),
    negative_( n < 0 ? true : false )
{
    stripLeadingZeroes( x_ );
}


BigInt::BigInt( const std::string& s ) : x_( std::string( "0" ) ), negative_( false )
{
    if ( ! BigInt::isValidBigIntString( s ) )
    {
        throw std::invalid_argument( "Invalid BigInt string=" + s );
    }

    if ( s.size() == 1 )
    {
        x_[ 0 ] = ( s[ 0 ] == '1' ? true : false );
        negative_ = false;
    }

    switch ( s[ 0 ] )
    {
    case 'b' :
    case 'B' :
        if ( s[ 1 ] == '+' || s[ 1 ] == '-' )
        {
            negative_ = ( s[ 1 ] == '-' ? true : false );
            x_ = boost::dynamic_bitset<>( s.substr( 2 ) );
        }
        else
        {
            negative_ = false;
            x_ = boost::dynamic_bitset<>( s.substr( 1 ) );
        }
        break;

    case 'd' :
    case 'D' :
        if ( s[ 1 ] == '+' || s[ 1 ] == '-' )
        {
            negative_ = ( s[ 1 ] == '-' ? true : false );
            x_ = boost::dynamic_bitset<>( decToBin( s.substr( 2 ) ) );
        }
        else
        {
            negative_ = false;
            x_ = boost::dynamic_bitset<>( decToBin( s.substr( 1 ) ) );
        }
        break;

    case 'x' :
    case 'X' :
        if ( s[ 1 ] == '+' || s[ 1 ] == '-' )
        {
            negative_ = ( s[ 1 ] == '-' ? true : false );
            x_ = boost::dynamic_bitset<>( hexToBin( s.substr( 2 ) ) );
        }
        else
        {
            negative_ = false;
            x_ = boost::dynamic_bitset<>( hexToBin( s.substr( 1 ) ) );
        }
        break;

    case '+' :
        negative_ = false;
        x_ = boost::dynamic_bitset<>( decToBin( s.substr( 1 ) ) );
        break;

    case '-' :
        negative_ = true;
        x_ = boost::dynamic_bitset<>( decToBin( s.substr( 1 ) ) );
        break;

    default :

        // no radix identifier or sign so this is a positive decimal
        negative_ = false;
        x_ = boost::dynamic_bitset<>( decToBin( s ) );
    }
    stripLeadingZeroes( x_ );
    if ( x_.size() == 1 && x_[ 0 ] == 0 )
    {
        // this number is zero so...
        negative_ = false;
    }
}





// assignment operators

BigInt&   BigInt::operator= ( const unsigned long& rhs )
{
    BigInt bi( rhs );
    x_        = bi.x_;
    negative_ = bi.negative_;
    return *this;
}


BigInt&   BigInt::operator= ( const signed long& rhs )
{
    BigInt bi( rhs );
    x_        = bi.x_;
    negative_ = bi.negative_;
    return *this;
}


BigInt&   BigInt::operator= ( const int& rhs )
{
    BigInt bi( rhs );
    x_        = bi.x_;
    negative_ = bi.negative_;
    return *this;
}


BigInt&   BigInt::operator= ( const std::string& rhs )
{
    BigInt bi( rhs );
    x_        = bi.x_;
    negative_ = bi.negative_;
    return *this;
}


BigInt&   BigInt::operator= ( const char*& rhs )
{
    BigInt bi( rhs );
    x_        = bi.x_;
    negative_ = bi.negative_;
    return *this;
}




// unary operators
BigInt BigInt::operator+ () const
{
    BigInt bi;
    bi = *this;
    return bi;
}

BigInt  BigInt::operator- () const
{
    BigInt bi;
    bi = *this;
    if ( x_.size() == 1 && x_[ 0 ] == 0 )
    {
        // this number is zero so do nothing
    }
    else
    {
        bi.negative_ = !negative_;
    }
    return bi;
}


// compound assignment operators
const BigInt& BigInt::operator+= ( const BigInt& rhs )
{
    unsigned long newSize =( x_.size() < rhs.x_.size()  ? rhs.x_.size() + 1 : x_.size() + 1 );
    if ( negative_ && rhs.negative_ || !negative_ && !rhs.negative_ )
    {
        // same sign for both numbers
        // resize *this to make sure that it is the largest with an extra bit in case of a final carry
        x_.resize( newSize );
        compoundAddAssignIgnoreSign( rhs );
    }
    else
    {
        // opposite signs
        // We would like to switch the negative number to two's complement
        // before performing the addition, however since rhs is const we
        // will treat *this  as the negative number and then change the sign
        // if necessary at the end.

        bool isResultSignNegative = false;
        // switch *this temporarily to the same sign as rhs so we can compare the
        // magnitude of the number.
        negative_ = rhs.negative_;
        if ( *this < rhs )
        {
            isResultSignNegative = false;
        }
        else
        {
            if ( rhs < *this )
            {
                isResultSignNegative = true;
            }
            else
            {
                // *this and rhs are same magnitude so the sum is zero
                negative_ = false;
                return ( *this = 0 );
            }
        }
        x_.resize( newSize );
        x_.flip();

        // note that high order bit of x_ is now 1 ( it's the sign bit for two's complement )

        // need to add one to *this
        BigInt one( 1 );
        compoundAddAssignIgnoreSign( one );
        compoundAddAssignIgnoreSign( rhs );

        // Check for a negative two's complement number and convert it back
        if ( x_[ x_.size() - 1 ] == 1 )
        {
            x_.flip();
            compoundAddAssignIgnoreSign( one );
        }
        x_.resize( newSize - 1 );
        negative_ = isResultSignNegative;
    }
    stripLeadingZeroes( x_ );
    return *this;
}


const BigInt& BigInt::operator-= ( const BigInt& rhs )
{
    *this += -rhs;
    return *this;
}



const BigInt& BigInt::operator*= ( const BigInt& rhs )
{
    if ( *this == 0 || rhs == 0 )
    {
        return ( *this = 0 );
    }

    BigInt thisCopy( *this );
    x_.reset();
    x_.resize( rhs.x_.size() + x_.size() );
    const BigInt& multiplicand = ( x_.size() < rhs.x_.size() ? rhs : thisCopy);
    const BigInt& multiplier   = ( x_.size() >= rhs.x_.size() ? rhs : thisCopy );

    boost::dynamic_bitset<>::size_type multiplierSize = multiplier.x_.size();
    boost::dynamic_bitset<>::size_type startIndex     = 0;

    for ( boost::dynamic_bitset<>::size_type i = 0; i < multiplierSize; ++i, ++startIndex )
    {
        if ( multiplier.x_[ i ] == 1 )
        {
            compoundAddAssignIgnoreSign( multiplicand, startIndex );
        }
    }

    if ( negative_ == rhs.negative_ )
    {
        negative_ = false;
    }
    else
    {
        negative_ = true;
    }
    stripLeadingZeroes( x_ );
    return *this;
}


const BigInt& BigInt::operator/= ( const BigInt& rhs )
{
    BigInt quotient;
    BigInt remainder;
    divisionAndRemainder( rhs, quotient, remainder );
    *this = quotient;
    return *this;
}


const BigInt& BigInt::operator%= ( const BigInt& rhs )
{
    BigInt quotient;
    BigInt remainder;
    divisionAndRemainder( rhs, quotient, remainder );
    *this = remainder;
    return *this;
}


void BigInt::divisionAndRemainder( const BigInt& divisor, BigInt& quotient, BigInt& remainder ) const
{

    /*
    This routine divides *this by divisor, calculating both the quotient and remainder.  We
    will use an algorithm based on the normal way humans calculate division.

    Size of quotient:  Consider multiplying a three bit number by a five bit number.  The
    minimum resulting size would be 100 * 10000 = 1000000 (a seven bit number).  The maximum
    resulting size would be 111 * 11111 = 10100001 (an eight bit number).  The resulting size
    will always be the sum of the two sizes or possibly one less.  Hence for division the
    size of the quotient will always be the difference between the two sizes or possibly
    one more ( assuming divisor's size is less than or equal to quotient ).  Thus setting
    the size of quotient to be the difference plus one will guarantee that it will be large
    enough to hold the result.

    The rationale for doing it this way is that in division the quotient bits are generated
    starting with the high order bit and ending with the low order bit.  By setting the
    size of quotient before we begin we can store the bits as they are generated from
    index quotient.size() - 1 down to zero.  If we stored   the bits in some container
    as generated we would later have the problem of reversing the bits which doing it
    this way avoids.

    We will also find it convenient to pad dividend with two leading zeroes and
    divisor with one leading zero.  Consider the example below of dividing
    10001101 by 111.  The first successful division will be 111 into 1000 or a four
    bit number divided by a three bit number.  But suppose we were dividing 111000 by
    111. Then the first successful division would be 111 into 111 or a 3 bit number
    into a three bit number, thus the first time through the loop would have to be
    handled differently.  By padding both dividend and divisor with a leading zero we
    can always divide a four bit number into a four bit number, thus simplifying the
    loop.  This may result in leading zeroes in quotient, but they  can be stripped
    later if necessary.  We also retain leading zeroes in remainder through out the
    loop so that divisor will always have the same number of bits.  This facilitates
    the lexical comparision of divisor and dividend to see which is bigger.  The
    second zero added to the left of dividend is to make sure dividend is big enough
    to handle any carry coming out of the call to compoundAddAssignIgnoreCase().
    (This may not be necessary, but it is benign and if not necessary will be
    stripped later.  We need to do a detailed analysis of all possible outcomes from
    calls to compoundAddAssignIgnoreCase() before eliminating this second added zero.)


    Algorithm:  Consider the following example:

        10001101 / 111 = 10100 + remainder of 1    ( 141 / 7 = 20 with remainder of 1 )

                start     end

                    ^     ^
                    |     |
                          0 0 0 0 0 0          quotient is initialized to all zeroes
                _____________________
        0 1 1 1 | 0 0 1 0 0 0 1 1 0 1          start and end are indexes into the dividend, initially set
                                                to define a range the same size as the divisor.

        Compare lexically 0111 and 0100  [start, end].   If 0111 were <= 0100 we could put a one in quotient at index end
                                                            and continue with the algorithm, but since 0111 > 0100 we put a
                                                            zero at index end and decrement start and end and try again.


                  start     end

                      ^     ^
                      |     |
                          0 1 0 0 0 0          quotient is 0 1 ? ? ? ?
                _____________________
        0 1 1 1 | 0 0 1 0 0 0 1 1 0 1        Compare 0111 and 1000 [start, end].  Since 0111 < 1000 we put a one
                      0 1 1 1                in quotient at index end and substract the divisor 0111 from 1000
                      -------                [start, end] in dividend.
                      0 0 0 1
                                            Since we no longer need the first four bits of dividend, but do need
                                            remainder for use in the next division we can safely overwrite the
                                            range [start, end] in dividend with remainder and decrement start and
                                            end.  Our new dividend is now the new start end.


                  start     end

                      ^     ^
                      |     |
                        0 1 0 0 0 0          quotient is 0 1 0 ? ? ?
              _____________________
        1 1 1 | 0 0 0 0 0 1 1 1 0 1          Compare 0111 and 0011 [start, end].  Since 0111 > 0011 we put a zero
                      0 1 1 1                in quotient at index end and decrement start and end.
                      -------



                      start     end

                          ^     ^
                          |     |
                          0 1 0 1 0 0        quotient is 0 1 0 1 ? ?
                _____________________
        0 1 1 1 | 0 0 0 0 0 1 1 1 0 1        Compare 0111 and 0111 [start, end].  Since 0111 <= 0111 we put a one
                          0 1 1 1            in quotient at index end and substract the divisor 0111 from 1000
                          -------            [start, end] in dividend.  The remainder 0000 is then written back
                          0 0 0 0            replacing the range [start, end] in dividend.
                                             Decrement start and end.


                        start     end

                            ^     ^
                            |     |
                          0 1 0 1 0 0        quotient is 0 1 0 1 0 ?
                ___________________
        0 1 1 1 | 0 0 0 0 0 0 0 0 0 1        Compare 0111 and 0000 [start, end].  Since 0111 > 0000 we put a zero
                            0 1 1 1          in quotient at index end and decrement start and end.
                            -------



                          start     end

                              ^     ^
                              |     |
                          0 1 0 1 0 0        quotient is 0 1 0 1 0 0
                _____________________
        0 1 1 1 | 0 0 0 0 0 0 0 0 0 1        Compare 0111 and 0000 [start, end].  Since 0111 > 0001 we put a zero
                              0 1 1 1        in quotient at index end and since end is at the zero index we
                              -------        are done. remainder is [start, end] of dividend which is 0001 or one.

        Note:  The process of overwriting dividend with remainder is done automatically by
        compoundAddAssignIgnoreSign() when performing the subtraction.
    */

    if ( divisor == 0 )
    {
        throw std::domain_error( "Division by zero" );
    }

    if ( divisor > *this )
    {
        quotient  = 0;
        remainder = *this;
        return;
    }
    else
    {
        if ( divisor == *this )
        {
            quotient  = 1;
            remainder = 0;
            return;
        }
    }

    // We know that divisor < *this so ...

    quotient.x_.reset();
    quotient.x_.resize( x_.size() - divisor.x_.size() + 1 );

    BigInt dividendPadded( *this );
    dividendPadded.x_.resize( dividendPadded.x_.size() + 2 );
    BigInt divisorPadded( divisor );
    divisorPadded.x_.resize( divisorPadded.x_.size() + 1 );

    BigInt twosCompDivisor( divisorPadded );
    twosCompDivisor.x_.resize( divisorPadded.x_.size() + 1 );
    twosCompDivisor.x_.flip();
    twosCompDivisor += 1;

    boost::dynamic_bitset<>::size_type divisorPaddedSize = divisorPadded.x_.size();

    boost::dynamic_bitset<>::size_type start = dividendPadded.x_.size() - 2;
    boost::dynamic_bitset<>::size_type end   = start - divisorPadded.x_.size() + 1;

    boost::dynamic_bitset<>::size_type quotientIndex = quotient.x_.size() - 1;

    // Note that we cannot test end >= 0 since end is an unsigned type and
    // decrementing past zero will roll over to a positive value, so
    // end >= 0 will never be false, so...
    unsigned long k = end + 1;
    while ( k > 0 )
    {
        // compare divisorPadded lexically with [start, end]
        bool isDivisorGreaterThanDividend = false;
        boost::dynamic_bitset<>::size_type j = start;
        for ( boost::dynamic_bitset<>::size_type i = divisorPaddedSize; i > 0; --i, --j )
        {
            if ( divisorPadded.x_[ i - 1 ] == dividendPadded.x_[ j ] )
            {
                continue;
            }
            else
            {
                if ( divisorPadded.x_[ i - 1 ] > dividendPadded.x_[ j ] )
                {
                    isDivisorGreaterThanDividend = true;
                    break;
                }
                else
                {
                    break;
                }

            }
        }
        if ( isDivisorGreaterThanDividend )
        {
            quotient.x_[ quotientIndex ] = 0;
            --quotientIndex;
            --start;
            --end;
            --k;
            continue;
        }

        // if we reach this far divisor is <= dividend
        quotient.x_[ quotientIndex ] = 1;
        dividendPadded.compoundAddAssignIgnoreSign( twosCompDivisor, end );
        --quotientIndex;
        --start;
        --end;
        --k;
    }
    quotient.stripLeadingZeroes( quotient.x_ );
    dividendPadded.x_.resize( divisorPaddedSize );
    dividendPadded.stripLeadingZeroes( dividendPadded.x_ );
    remainder = dividendPadded;

}


// increment and decrement operators
BigInt& BigInt::operator++ ()
{
    *this += 1;
    return *this;
}


BigInt BigInt::operator++ ( int )
{
    BigInt bi( *this );
    ++*this;
    return bi;
}


BigInt& BigInt::operator-- ()
{
    *this -= 1;
    return *this;
}

BigInt BigInt::operator-- ( int )
{
    BigInt bi( *this );
    --*this;
    return bi;
}


void BigInt::swap( BigInt& bi )
{
    x_.swap( bi.x_ );
    bool temp( negative_ );
    negative_ = bi.negative_;
    bi.negative_ = temp;
}


// conversion functions
std::string BigInt::decToHex( const std::string& s )
{
    /*
    Algorithm:

    Consider the example of converting 370 decimal to hex.

        First divide 370 by 16

                 2                   23
                ____                ____
            16 |370      -->    16 |370
                32                  32
                --                  ----
                 5                   50
                                     48
                                     --
                                      2

        The remainder of two is the least significant hex digit, i.e.,

                370d = 23 * 16^1 + 2 * 16^0

        We now take the new decimal value 23 and divide by 16 and look at the
        remainder to get the 16^1 hex digit.

                 1
                ___
            16 |23
                16
                --
                 7

        The remainer of 7 is the hex digit in the 16^1 column, i.e.,

                370d = 1 * 16^2 + 7 * 16^1 + 2 * 16^0


        Continuing, we take the new decimal value 1 and divide by 16 again.

                0
                __
            16 |1
                0
                -
                1

        The new decimal value of 0 tells us we are done and the remainder
        is the final hex digit.

                370d = 0 * 16^3 + 1 * 16^2 + 7 * 16^1 + 2 * 16^0

        Hence 370d = 172x

        We note that once the new decimal value is a single digit that digit will
        be the last hex digit since dividing a single digit by sixteen will always
        yield a quotient of zero and a remainder equal to that digit.

        Note also that the hex digits are generated in reverse order so after
        storing them in a string as we go we will need to reverse the string.
        The algorithm may also generate an extra trailing zero which will turn
        into a leading zero when reversed so we will need to strip trailing
        zeroes before reversing.

    */

    // Since 16^5 = 1048576 > 999999, five hex digits are always sufficient
    // to hold six decimals so we divide the decimal string length by six,
    // round up and multiply by five to reserve enough space in the new string.

    const char intToChar[ 16 ] = { '0', '1', '2', '3', '4', '5', '6', '7',
        '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

    const signed char charToIntShift = -48;

    unsigned int base      = 16;
    unsigned int dividend  = 0;
    unsigned int remainder = 0;
    unsigned int decDigit  = 0;

    std::string::size_type index = 0;

    std::string hexString;
    hexString.reserve( ( ( s.size() / 6 ) + 1 ) * 5 );

    if ( s.size() == 0 )
    {
        // What???  How do you convert an empty string to hex?
        return "";
    }

    if ( s.size() == 1 )
    {
        hexString.push_back( s[ 0 ] );
        return hexString;
    }

    std::string decStr( s );
    std::string newDecStr;

    while ( decStr.size() > 1 )
    {
        index = 0;
        remainder = decStr[ 0 ] + charToIntShift;
        newDecStr = "";
        while ( ( index + 1 ) < decStr.size() )
        {
            dividend  = remainder * 10 + decStr[ index + 1 ] + charToIntShift;
            decDigit  = dividend / base;
            remainder = dividend % base;

            newDecStr.push_back( intToChar[ decDigit ] );

            ++index;
        }
        hexString.push_back( intToChar[ remainder ] );
        decStr = newDecStr;
    }
    hexString.push_back( intToChar[ decDigit ] );

    // hexString needs to be reversed, but first we will strip trailing zeroes
    // so they don't turn into leading zeroes.
    if ( hexString.size() <= 1 )
    {
        // We are done since the string and its reversal are the same.
        // ( We also don't want to strip a single zero if present. )
        return hexString;
    }

    std::string::iterator iter = hexString.end();
    std::string::iterator startPlusOne = ( hexString.begin() )++;
    --iter;
    while ( iter != startPlusOne && *iter == '0' )
    {
        --iter;
    }
    ++iter;
    // iter now points to the first trailing zero ( possibly end() )

    hexString.erase( iter, hexString.end() );

    hexString = std::string ( hexString.rbegin(), hexString.rend() );
    return hexString;
}


std::string BigInt::hexToDec( const std::string& s )
{
    return binToDec( hexToBin( s ) );
}



std::string BigInt::decToBin( const std::string& s )
{
    return hexToBin( decToHex( s ) );
}


std::string BigInt::binToDec( const std::string& s )
{
    if ( s.empty() )
    {
        return s;
    }

    const char binToDecChar[ 10 ] = { '0', '1', '2', '3', '4', '5', '6', '7',
        '8', '9' };

    std::string decStr;
    BigInt ten( 10 );
    BigInt dividend;
    dividend.x_ = boost::dynamic_bitset<>( s );
    dividend.stripLeadingZeroes( dividend.x_ );
    BigInt quotient( 0 );
    BigInt remainder( 0 );

    while ( dividend > 9 )
    {
        dividend.divisionAndRemainder( ten, quotient, remainder );
        decStr.push_back( binToDecChar[ remainder.x_.to_ulong() ] );
        dividend = quotient;
    }
    decStr.push_back( binToDecChar[ quotient.x_.to_ulong() ] );
    decStr = std::string( decStr.rbegin(), decStr.rend() );
    return decStr;
}



std::string BigInt::hexToBin( const std::string& s )
{
    std::string binString( s.size() * 4, '0' );
    std::string::size_type i = 0;
    while ( i  != s.size() )
    {
        switch ( s[ i ] )
        {
        case '0' :
            binString.replace( i * 4, 4, "0000" );
            break;
        case '1' :
            binString.replace( i * 4, 4, "0001" );
            break;
        case '2' :
            binString.replace( i * 4, 4, "0010" );
            break;
        case '3' :
            binString.replace( i * 4, 4, "0011" );
            break;
        case '4' :
            binString.replace( i * 4, 4, "0100" );
            break;
        case '5' :
            binString.replace( i * 4, 4, "0101" );
            break;
        case '6' :
            binString.replace( i * 4, 4, "0110" );
            break;
        case '7' :
            binString.replace( i * 4, 4, "0111" );
            break;
        case '8' :
            binString.replace( i * 4, 4, "1000" );
            break;
        case '9' :
            binString.replace( i * 4, 4, "1001" );
            break;
        case 'a' :
        case 'A' :
            binString.replace( i * 4, 4, "1010" );
            break;
        case 'b' :
        case 'B' :
            binString.replace( i * 4, 4, "1011" );
            break;
        case 'c' :
        case 'C' :
            binString.replace( i * 4, 4, "1100" );
            break;
        case 'd' :
        case 'D' :
            binString.replace( i * 4, 4, "1101" );
            break;
        case 'e' :
        case 'E' :
            binString.replace( i * 4, 4, "1110" );
            break;
        case 'f' :
        case 'F' :
            binString.replace( i * 4, 4, "1111" );
            break;
        default :
            ;
        }
        ++i;
    }
    // strip any leading zeroes but not a final zero.
    stripLeadingZeroesFromString( binString );
    return binString;
}


std::string BigInt::binToHex( const std::string& s )
{
    if ( s.empty() )
    {
        return s;
    }

    const char binToHexChar[ 16 ] = { '0', '1', '2', '3', '4', '5', '6', '7',
        '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };

    boost::dynamic_bitset<> b( s );

    // we will pad b with leading zeroes to make sure size of b is a multiple of 4
    if ( b.size() % 4 != 0 )
    {
        b.resize( ( ( b.size() / 4 ) + 1 ) * 4 );
    }
    boost::dynamic_bitset<> currentFourBits( 4 );

    std::string hexString;
    hexString.reserve( b.size() / 4 );

    for ( boost::dynamic_bitset<>::size_type index = b.size(); index > 0; index -= 4 )
    {
        currentFourBits[ 0 ] = b[ index - 4 ];
        currentFourBits[ 1 ] = b[ index - 3 ];
        currentFourBits[ 2 ] = b[ index - 2 ];
        currentFourBits[ 3 ] = b[ index - 1 ];
        hexString.push_back( binToHexChar[ currentFourBits.to_ulong() ] );
    }

    // strip any leading zeroes but not a final zero.
    stripLeadingZeroesFromString( hexString );
    return hexString;
}




void BigInt::stripLeadingZeroes( boost::dynamic_bitset<>& db )
{
    // We will start at the high bit and reduce the new size by one for
    // each zero encountered unitl we find a one or reach the low bit,
    // then resize.  Note that we are careful not to resize to an
    // empty bitset if all the bits are zero.  The minimum size for
    // a non-empty bitset after processing is one.

    boost::dynamic_bitset<>::size_type s = db.size();

    // convert size which is one based to serve as an index which is zero based
    s -= 1;
    // Short circuit evaluation dependency
    while ( s != 0 && db[ s ] == 0 )
    {
        --s;
    }

    if ( s + 1 != db.size() )
    {
        db.resize( s + 1 );
    }
}



void BigInt::stripLeadingZeroesFromString( std::string& s )
{
    // This function strips any leading zeroes but not a final zero.
    std::string::size_type pos = s.find_first_not_of( '0' );
    s.erase( 0, ( pos != std::string::npos ? pos : s.size() - 1 ) );
    return;
}


bool BigInt::isValidBigIntString( const std::string& s )
{
    using std::string;
    switch ( s.size() )
    {
    case 0 :
        return false;
        break;

    case 1 :
        // single value must be 0-9
        return ( string::npos == s.find_first_not_of( "0123456789" ) ? true : false );
        break;

    case 2 :
        switch ( s[ 0 ] )
        {
        case 'b' :
        case 'B' :
            return ( string::npos == s.substr( 1 ).find_first_not_of( "01" ) ? true : false );
            break;

        case 'x' :
        case 'X' :
            return ( string::npos == s.substr( 1 ).find_first_not_of( "0123456789ABCDEFabcdef" ) ? true : false );
            break;

        case '+' :
        case '-' :
        case 'd' :
        case 'D' :
            return ( string::npos == s.substr( 1 ).find_first_not_of( "0123456789" ) ? true : false );
            break;

        default :
            // must be base ten with no sign
            return ( string::npos == s.find_first_not_of( "0123456789" ) ? true : false );
            break;
        }

    default :
        break;
    }

    // s.size() >= 3;

    switch ( s[ 0 ] )
    {
    case 'b' :
    case 'B' :
        if ( s[ 1 ] == '+' || s[ 1 ] == '-' )
        {
            return ( string::npos == s.substr( 2 ).find_first_not_of( "01" ) ? true : false );
        }
        else
        {
            return ( string::npos == s.substr( 1 ).find_first_not_of( "01" ) ? true : false );
        }
        break;

    case 'x' :
    case 'X' :
        if ( s[ 1 ] == '+' || s[ 1 ] == '-' )
        {
            return ( string::npos == s.substr( 2 ).find_first_not_of( "0123456789ABCDEFabcdef" ) ? true : false );
        }
        else
        {
            return ( string::npos == s.substr( 1 ).find_first_not_of( "0123456789ABCDEFabcdef" ) ? true : false );
        }
        break;

    case 'd' :
    case 'D' :
        if ( s[ 1 ] == '+' || s[ 1 ] == '-' )
        {
            return ( string::npos == s.substr( 2 ).find_first_not_of( "0123456789" ) ? true : false );
        }
        else
        {
            return ( string::npos == s.substr( 1 ).find_first_not_of( "0123456789" ) ? true : false );
        }
        break;

    case '+' :
    case '-' :
        return ( string::npos == s.substr( 1 ).find_first_not_of( "0123456789" ) ? true : false );
        break;

    default :
        // must be base ten without a sign
        return ( string::npos == s.find_first_not_of( "0123456789" ) ? true : false );
        break;
    }
}



void BigInt::compoundAddAssignIgnoreSign( const BigInt& rhs, boost::dynamic_bitset<>::size_type startIndex )
{
    /*
    This function adds with compound assignment rhs to *this, beginning at
    startIndex for *this, using an ordinary addition algorithm, as though
    they are the same sign even if they are not. That is, sign is ignored.
    (*this may have been switched to 2's complement before calling this function)

    startIndex is a default parameter with default value zero.

    Example:

        *this =    101100111      startIndex = 0
         rhs  =           11
                   ----------
                   101101010


                   101100111      startIndex = 3
                       11
                   ----------
                   101111111


    We will add rhs to this, changing *this as we go.  It is the responsibility of
    the calling routine to make sure that *this is large enought to hold the result.


    Algorithm:
        Note:  We show result separately as an aid to understanding, but *this
               will actually be overwritten with result as we go.

                 --- --- --- ---
        carry   |   | 1 | 1 | 0 |      ( *this && rhs ) || ( *this && carry ) || { rhs && carry )
                |---|---|---|---|
        *this   | 0 | 1 | 0 | 1 |
                |---|---|---|---|
        rhs     |   |   | 1 | 1 |
                 --- --- --- ---

                 --- --- --- ---
                | 1 | 0 | 0  | 0 |       ( *this ^ rhs ) ^ carry
        result  |---|---|---|---|


        We will add the two bits of *this and rhs and then add the result to the
        carry bit to get result.  Adding two bits can be done by XORing the bits'
        The carry bit is set if any two of *this, rhs or carry are set.

        *this  rhs  Addition  XOR
          0     0     0        0
          0     1     1        1
          1     0     1        1
          1     1     0        0
    */

    unsigned long minSize = rhs.x_.size();
    bool carryBit         = false;
    bool newCarryBit      = false;

    boost::dynamic_bitset<>::size_type thisBitIndex = startIndex;
    boost::dynamic_bitset<>::size_type rhsBitIndex  = 0;
    while ( rhsBitIndex < minSize )
    {
        // if any two of carry *this or rhs are one we will have a carry
        newCarryBit        = x_[ thisBitIndex ] && rhs.x_[ rhsBitIndex ] || x_[ thisBitIndex ] && carryBit || rhs.x_[ rhsBitIndex ] && carryBit;
        x_[ thisBitIndex ] = ( x_[ thisBitIndex ] ^ rhs.x_[ rhsBitIndex ] ) ^ carryBit;
        carryBit           = newCarryBit;
        ++rhsBitIndex;
        ++thisBitIndex;
    }

    // We have finished with rhs so we only need to continue if the carryBit is one.
    while ( thisBitIndex < x_.size() && carryBit )
    {
        newCarryBit = x_[ thisBitIndex ] & carryBit;
        x_[ thisBitIndex ] = x_[ thisBitIndex ] ^ carryBit;
        carryBit = newCarryBit;
        ++thisBitIndex;
    }
}



// *****************  Non-member functions  ****************************


// comparison operators
bool operator< ( const BigInt& lhs, const BigInt& rhs )
{
    // Note that <, <=, >, >= cannot be used on dynamic bitsets unless the
    // sizes are equal
    if ( lhs.negative_ && ! rhs.negative_ )
    {
        return true;
    }
    if ( ! lhs.negative_ && rhs.negative_ )
    {
        return false;
    }
    if ( ! lhs.negative_ && ! rhs.negative_ )
    {
        if ( lhs.x_.size() < rhs.x_.size() )
        {
            return true;
        }
        else
        {
            if ( lhs.x_.size() == rhs.x_.size() )
            {
                return lhs.x_ < rhs.x_;
            }
            else
            {
                return false;
            }
        }
    }
    if ( lhs.negative_ && rhs.negative_ )
    {
        if ( lhs.x_.size() < rhs.x_.size() )
        {
            return false;
        }
        else
        {
            if ( lhs.x_.size() == rhs.x_.size() )
            {
                return lhs.x_ > rhs.x_;
            }
            else
            {
                return true;
            }
        }
    }

    // to make the compiler happy about warning that not all control paths
    // return a value
    return true;
}


bool operator<= ( const BigInt& lhs, const BigInt& rhs )
{
    return ( lhs == rhs || lhs < rhs );
}


bool operator== ( const BigInt& lhs, const BigInt& rhs )
{
    return ( lhs.x_ == rhs.x_ && lhs.negative_ == rhs.negative_ );
}


bool operator!= ( const BigInt& lhs, const BigInt& rhs )
{
    return !( lhs == rhs );
}


bool operator>= ( const BigInt& lhs, const BigInt& rhs )
{
    return !( lhs < rhs );
}


bool operator> ( const BigInt& lhs, const BigInt& rhs )
{
    return !( lhs <= rhs );
}



// binary arithmetic operators
BigInt operator+ ( const BigInt& lhs, const BigInt& rhs )
{
    return BigInt( lhs ) += rhs;
}


BigInt operator- ( const BigInt& lhs, const BigInt& rhs )
{
    return BigInt( lhs ) -= rhs;
}


BigInt operator* ( const BigInt& lhs, const BigInt& rhs )
{
    return BigInt( lhs ) *= rhs;
}


BigInt operator/ ( const BigInt& lhs, const BigInt& rhs )
{
    return BigInt( lhs ) /= rhs;
}


BigInt operator% ( const BigInt& lhs, const BigInt& rhs )
{
    return BigInt( lhs ) %= rhs;
}


std::ostream& operator<< ( std::ostream& os, const BigInt& bi )
{
    const long int idx( BigInt::getOutputWordIndex() );
    std::string sign = ( bi.negative_ ? "-" : "" );
    std::ostringstream oss;
    oss << bi.x_;
    long int base      = os.iword( idx ) & 7L;
    long int alphaCase = os.iword( idx ) & 8L;
    bool useUpperCase  = ( alphaCase == 8 ? true : false );
    long int noShowBase  = os.iword( idx ) & 16L;
    bool useShowBase   = ( noShowBase == 16 ? false : true );
    switch ( base )
    {
    case BigInt::bin :
        if ( useUpperCase )
        {
            os << ( useShowBase ? "B" : "" );
        }
        else
        {
            os << ( useShowBase ? "b" : "" );
        }
        os << sign << oss.str();
        break;

    case BigInt::hex :
        {
        std::string s( BigInt::binToHex( oss.str() ) );
        if ( useUpperCase )
        {
            // Convert to uppercase.
            transform( s.begin(), s.end(), s.begin(), toupper );
            os << ( useShowBase ? "X" : "" ) << sign << s;
        }
        else
        {
            os << ( useShowBase ? "x" : "" ) << sign << s;
        }
        }
        break;

    case BigInt::dec :
    case BigInt::def :
    default :
        os << sign << BigInt::binToDec( oss.str() );
        break;
    }
    return os;
}


std::istream& operator>> ( std::istream& is, BigInt& bi )
{
    /*
    The input operator skips whitespace and then reads all characters
    up to the next whitespace ( a space, tab or newline ).  If the string
    read in is a valid BigInt string with a base identifier as the first
    character then all flags are ignored and a BigInt is constructed
    based on that string.  Only if there is no base identifier are the flags
    consulted as to the type of number, bin, hex or dec with dec being the
    default.  The only flags implemented for the input operator are:

        bin
        nobin
        hex
        nohex
        dec
        nodec
        def

    The flags uppercase, lowercase, showbase, noshowbase have no meaning and cannot
    be used.

    Examples:

        def or dec flag set:

            "b1010"    binary 1010 = decimal 10
            "x1010"    hex 1010    = decimal 4112
            "1010"     dec 1010    = decimal 1010

        bin flag set

            "1010"     binary 1010 = decimal 10

        hex flag set:

            "1010"     hex 1010 = decimal 4112

    */
    BigInt tempBi;

    std::string s;
    is >> s;
    if ( ! BigInt::isValidBigIntString( s ) )
    {
        is.setstate( std::ios_base::failbit );
        return is;
    }
    // if we reach this point s has at least one digit
    std::string::size_type digitStartPos = 0;

    switch ( s[ 0 ] )
    {
    case 'b' :
    case 'B' :
    case 'x' :
    case 'X' :
    case 'd' :
    case 'D' :
        tempBi =  s;
        bi.swap( tempBi );
        return is;
        break;

    case '+' :
    case '-' :
        digitStartPos = 1;
        break;

    default :
        digitStartPos = 0;
        break;
    }

    // no base identifier so consult the base flags
    const long int idx( BigInt::getInputWordIndex() );
    long int base = is.iword( idx ) & 7L;

    switch ( base )
    {
    case BigInt::bin :
        if ( std::string::npos != s.substr( digitStartPos ).find_first_not_of( "01" ) )
        {
            is.setstate( std::ios_base::failbit );
            return is;
        }
        tempBi = "b" + s;
        break;
    case BigInt::hex :
        if ( std::string::npos != s.substr( digitStartPos ).find_first_not_of( "0123456789ABCDEFabcdef" ) )
        {
            is.setstate( std::ios_base::failbit );
            return is;
        }
        tempBi = "x" + s;
        break;
    case BigInt::dec :
    case BigInt::def :
        if ( std::string::npos != s.substr( digitStartPos ).find_first_not_of( "0123456789" ) )
        {
            is.setstate( std::ios_base::failbit );
            return is;
        }
        tempBi = s;
        break;
    default :
        break;
    }

    bi.swap( tempBi );
    return is;
}



std::ostream& bigintbin( std::ostream& os )
{
    const long int idx( BigInt::getOutputWordIndex() );
    os.iword( idx ) = ( os.iword( idx ) & BigInt::nodec & BigInt::nohex ) | BigInt::bin;
    return os;
}


std::ostream& bigintdec( std::ostream& os )
{
    const long int idx( BigInt::getOutputWordIndex() );
    os.iword( idx ) = ( os.iword( idx ) & BigInt::nobin & BigInt::nohex ) | BigInt::dec;
    return os;
}


std::ostream& biginthex( std::ostream& os )
{
    const long int idx( BigInt::getOutputWordIndex() );
    os.iword( idx ) = ( os.iword( idx ) & BigInt::nodec & BigInt::nobin ) | BigInt::hex;
    return os;
}


std::ostream& bigintupper( std::ostream& os )
{
    const long int idx( BigInt::getOutputWordIndex() );
    os.iword( idx ) = ( os.iword( idx ) | BigInt::uppercase );
    return os;
}


std::ostream& bigintlower( std::ostream& os )
{
    const long int idx( BigInt::getOutputWordIndex() );
    os.iword( idx ) = ( os.iword( idx ) & BigInt::lowercase );
    return os;
}


std::ostream& bigintshowbase( std::ostream& os )
{
    const long int idx( BigInt::getOutputWordIndex() );
    os.iword( idx ) = ( os.iword( idx ) & BigInt::showbase );
    return os;
}


std::ostream& bigintnoshowbase( std::ostream& os )
{
    const long int idx( BigInt::getOutputWordIndex() );
    os.iword( idx ) = ( os.iword( idx ) | BigInt::noshowbase );
    return os;
}



std::ostream& bigintdefault( std::ostream& os )
{
    const long int idx( BigInt::getOutputWordIndex() );
    os.iword( idx ) = ( os.iword( idx ) & BigInt::def ) | BigInt::dec;
    return os;
}


// input stream manipulators
std::istream& bigintbin( std::istream& is )
{
    const long int idx( BigInt::getInputWordIndex() );
    is.iword( idx ) = ( is.iword( idx ) & BigInt::nodec & BigInt::nohex ) | BigInt::bin;
    return is;
}


std::istream& bigintdec( std::istream& is )
{
    const long int idx( BigInt::getInputWordIndex() );
    is.iword( idx ) = ( is.iword( idx ) & BigInt::nobin & BigInt::nohex ) | BigInt::dec;
    return is;
}


std::istream& biginthex( std::istream& is )
{
    const long int idx( BigInt::getInputWordIndex() );
    is.iword( idx ) = ( is.iword( idx ) & BigInt::nodec & BigInt::nobin ) | BigInt::hex;
    return is;
}


std::istream& bigintdefault( std::istream& is )
{
    const long int idx( BigInt::getInputWordIndex() );
    is.iword( idx ) = ( is.iword( idx ) & BigInt::def ) | BigInt::dec;
    return is;
}



// BigInt Math functions
BigInt factorial( const BigInt& n )
{
    BigInt result = 1;
    BigInt i = 2;
    while ( i <= n )
    {
        result *= i;
        ++i;
    }
    return result;
}