Long integer

#pragma once
 
#include <bitset>
 
const unsigned BITS = 256;
const unsigned BASE = 10;
 
class LongInt
{
public:
    LongInt(int number = 0);
    LongInt(const LongInt& other);
    LongInt& operator =(const LongInt& other);
 
public:
    class reference //прокси-класс для элемента
    {
        friend class LongInt;
 
        public: 
            reference& operator =(const reference& ref)
            {
                valuePtr->Set(myPosition, unsigned(ref));
                return *this;
            }
 
            reference& operator	=(unsigned value)
            {
                valuePtr->Set(myPosition, value);
                return *this;
            }
 
            operator unsigned() const
            {
                return valuePtr->Get(myPosition);
            }
 
        private:
            reference(LongInt* value, unsigned position)
            : valuePtr(value)
            , myPosition(position)
            {}
 
        private:
            unsigned myPosition;
            LongInt* valuePtr;
    };
 
public: // арифметические операторы
    LongInt& operator +=(const LongInt& other);
    LongInt& operator -=(const LongInt& other);
    LongInt& operator *=(const LongInt& other);
    LongInt& operator /=(const LongInt& other);
    LongInt& operator %=(const LongInt& other);
 
public: // битовые операторы
    LongInt& operator |=(const LongInt& other);
    LongInt& operator ^=(const LongInt& other);
    LongInt& operator &=(const LongInt& other);
 
public: // операторы битового сдвига
    LongInt& operator <<=(unsigned offs);
    LongInt& operator >>=(unsigned offs);
 
public:
    LongInt& operator ++();
    LongInt& operator --();
    const LongInt operator ++(int);
    const LongInt operator --(int);
 
public: //унарные операторы арифметического и битового отрицания
    const LongInt operator -() const;
    const LongInt operator ~() const;
 
public:
    //operator bool() const;
 
public:
	size_t size();
 
public:
    reference operator [](unsigned index);
    unsigned operator [](unsigned index) const;
 
public:
    bool IsEqual(const LongInt& other) const; // Существует по соображениям эффективности и удобства.
    bool IsLess(const LongInt& other) const; // Отношения порядка достаточно. "==" можно представить, как !(l < r) && !(r < l))
 
public: // обмен без генерации исключений
    void Swap(LongInt& other);
 
private:
    void Divide(const LongInt& left, const LongInt& right, LongInt& quotient, LongInt& reminder);
    void SignedDivide(const LongInt& left, const LongInt& right, LongInt& quotient, LongInt& reminder);
 
private: // установка разряда
    void Set(unsigned position, unsigned value);
    unsigned Get(unsigned position) const;
 
private:
    typedef std::bitset<BITS> Bitset;
    Bitset value;
};
 
// Бинарные операторы как свободные функции.
 
const LongInt operator <<(const LongInt& value, unsigned shift);
const LongInt operator >>(const LongInt& value, unsigned shift);
 
const LongInt operator +(const LongInt& left, const LongInt& right);
const LongInt operator -(const LongInt& left, const LongInt& right);
const LongInt operator *(const LongInt& left, const LongInt& right);
const LongInt operator /(const LongInt& left, const LongInt& right);
const LongInt operator %(const LongInt& left, const LongInt& right);
const LongInt operator ^(const LongInt& left, const LongInt& right);
const LongInt operator &(const LongInt& left, const LongInt& right);
const LongInt operator |(const LongInt& left, const LongInt& right);
 
bool operator ==(const LongInt& left, const LongInt& right);
bool operator !=(const LongInt& left, const LongInt& right);
bool operator >=(const LongInt& left, const LongInt& right);
bool operator <=(const LongInt& left, const LongInt& right);
bool operator  >(const LongInt& left, const LongInt& right);
bool operator  <(const LongInt& left, const LongInt& right);
 
const LongInt Gcd(const LongInt& left, const LongInt& right)
const LongInt Pow(const LongInt& number, unsigned pow);
const LongInt Abs(const LongInt& number);
const LongInt Factorial(const LongInt& other);
 
 
LongInt::LongInt(int number) : value(number)
{}
 
LongInt::LongInt(const LongInt& other) : value(other.value)
{}
 
LongInt& LongInt::operator =(const LongInt& other) //Канонический вид оператора присваивания через копирующий конструктор и swap.
{
    LongInt temp(other); //Все исключения могут произойти только здесь.
    temp.Swap(*this); //Не вызывает исключений.
    return *this;
}
 
void LongInt::Swap(LongInt& other) //swap через xor. Работает для произвольных битовых наборов равной длины.
{
    value ^= other.value;
    other.value ^= value;
    value ^= other.value;
}
 
bool LongInt::IsEqual(const LongInt& other) const
{
    return value == other.value;
}
 
bool LongInt::IsLess(const LongInt& other) const //Знаковый оператор "меньше". 
{
    LongInt diff = *this - other;
    LongInt xorr = *this ^ other;
 
    return (diff ^= xorr &= diff ^= *this).value.test(BITS - 1);
}
 
inline bool add(bool l, bool r, bool& carry) //Сложение битов с флагом переноса.
{
    bool sum = l ^ r ^ carry;
    carry = (l && r) || (l && carry) || (r && carry);
 
    return sum;
}
 
inline bool sub(bool l, bool r, bool& borrow) //Вычитание битов с флагом заема.
{
    bool diff = borrow ? !(l ^ r) : l ^ r;
    borrow = borrow ? !l || (l && r) : !l && r;
 
    return diff;
}
 
// Операторы доступа
 
LongInt::reference LongInt::operator [](unsigned index)
{
    return reference(this, index);
}
 
unsigned LongInt::operator [](unsigned index) const
{
    return Get(index);
}
 
// Операторы вида @= являются членами класса и модифицируют объект.
// Возвращают ссылку на себя.
 
LongInt& LongInt::operator +=(const LongInt& other)
{
    bool carry = false;
 
    for (unsigned i = 0; i != BITS; ++i)
        value[i] = add(value[i], other.value[i], carry);
 
    return *this;
}
 
LongInt& LongInt::operator -=(const LongInt& other)
{
    bool borrow = false;
 
    for (unsigned i = 0; i != BITS; ++i)
        value[i] = sub(value[i], other.value[i], borrow);
 
    return *this;
}
 
LongInt& LongInt::operator *=(const LongInt& other)
{
    LongInt temp(*this);
    value.reset();
 
    bool hasMoreZeroes = temp.value.count() < other.value.count();
 
    const LongInt& mult1 = hasMoreZeroes ? temp : other;
    const LongInt& mult2 = hasMoreZeroes ? other : temp;
 
    for (unsigned shift = 0; shift != BITS; ++shift)
        if (mult1.value.test(shift)) (*this) += (mult2 << shift);
 
    return *this;
}
 
LongInt& LongInt::operator /=(const LongInt& other)
{
    SignedDivide(LongInt(*this), other, *this, LongInt());
    return *this;
}
 
LongInt& LongInt::operator %=(const LongInt& other)
{ 
    SignedDivide(LongInt(*this), other, LongInt(), *this);
    return *this;
}
 
LongInt& LongInt::operator |=(const LongInt& other)
{ 
    value |= other.value;
    return *this;
}
 
LongInt& LongInt::operator ^=(const LongInt& other)
{ 
    value ^= other.value;
    return *this;
}
 
LongInt& LongInt::operator &=(const LongInt& other)
{ 
    value &= other.value;
    return *this;
}
 
LongInt& LongInt::operator <<=(unsigned shift) // знаковый сдвиг влево совпадает с беззнаковым
{ 
    value <<= shift;
    return *this;
}
 
LongInt& LongInt::operator >>=(unsigned shift) // знаковый сдвиг вправо на основе беззнакового
{ 
    unsigned MSB = BITS - 1;
 
    value.flip(MSB);
    value >>= shift;
 
    LongInt tmp;
    if (shift <= MSB) tmp.value.set(MSB - shift);
 
    return *this -= tmp;
}
 
 
// Префиксный инкремент/декремент изменят свой объект
 
LongInt& LongInt::operator ++()
{
    return *this += 1;
}
 
LongInt& LongInt::operator --()
{
    return *this -= 1;
}
 
// Постфиксный инкремент/декремент использует префиксную версию.
// Все изменения, внесенные в ++, воспринимаюстя ++(int) автоматически.
 
const LongInt LongInt::operator ++(int)
{
    LongInt temp(*this);
    ++(*this);
    return temp;
}
 
const LongInt LongInt::operator --(int)
{
    LongInt temp(*this);
    --(*this);
    return temp;
}
 
// Неявное приведение к bool.
// Используется в конструкциях вида if (a) ...
// Прежде, чем раскомментировать эту функцию, 
// нужно написать перегруженные фукнции для каждой операции, для каждого встроенного типа.
// Иначе, код не будет компилироваться из-за невозможности однозначно подобрать нужное преобразование.
/*
LongInt::operator bool() const
{
    return value.any();
}
*/
 
// Унарные операторы.
// Возвращают const Obj, чтобы не компилировалось следующее: -b += c;
 
const LongInt LongInt::operator ~() const
{
    LongInt temp(*this);
    temp.value.flip();
    return temp;
}
 
const LongInt LongInt::operator -() const //-a == ~a + 1 == ~(a - 1)
{
    return ~(*this - 1);
}
 
// Все бинарные операторы вида Res operator @(L, R) используют Res operator @=(R)
// Правки вносятся только в operator @=. operator @ воспринимает изменения автоматически.
// ****
// Все бинарные операторы реализованы, как свободные функции. Этот прием позволяет _не_ухудшать_
// инкапсуляцию и, как следствие, делать более переносимый код. Класс LongInt может полностью поменяться
// сохранив лишь интерфейс и это не отразится на работе операторов.
// ****
// Наличие свободного бинарного оператора позволяет записывать выражения вроде 5 + LongInt(10).
// 5 будет неявно преобразовано к LongInt, потому, что у LongInt есть соответсвующий конструктор.
 
const LongInt operator +(const LongInt& left, const LongInt& right)
{
	LongInt temp(left);
	temp += right;
	return temp;
}
 
const LongInt operator -(const LongInt& left, const LongInt& right)
{
    LongInt temp(left);
    temp -= right;
    return temp;
}
 
const LongInt operator *(const LongInt& left, const LongInt& right)
{
    LongInt temp(left);
    temp *= right;
    return temp;
}
 
const LongInt operator /(const LongInt& left, const LongInt& right)
{
    LongInt temp(left);
    temp /= right;
    return temp;
}
 
const LongInt operator %(const LongInt& left, const LongInt& right)
{
    LongInt temp(left);
    temp %= right;
    return temp;
}
 
const LongInt operator |(const LongInt& left, const LongInt& right)
{
    LongInt temp(left);
    temp |= right;
    return temp;
}
 
const LongInt operator ^(const LongInt& left, const LongInt& right)
{
    LongInt temp(left);
    temp ^= right;
    return temp;
}
 
const LongInt operator &(const LongInt& left, const LongInt& right)
{
    LongInt temp(left);
    temp &= right;
    return temp;
}
 
const LongInt operator <<(const LongInt& value, unsigned shift)
{
    LongInt temp(value);
    temp <<= shift;
    return temp;
}
 
const LongInt operator >>(const LongInt& value, unsigned shift)
{
    LongInt temp(value);
    temp >>= shift;
    return temp;
}
 
const bool operator ==(const LongInt& left, const LongInt& right)
{
    return left.IsEqual(right);
}
 
const bool operator !=(const LongInt& left, const LongInt& right)
{
    return !(left == right);
}
 
const bool operator <(const LongInt& left, const LongInt& right)
{
    return left.IsLess(right);
}
 
const bool operator <=(const LongInt& left, const LongInt& right)
{
    return (left < right) || (left == right);
}
 
const bool operator >(const LongInt& left, const LongInt& right)
{
    return !(left <= right);
}
 
const bool operator >=(const LongInt& left, const LongInt& right)
{
    return !(left < right);
}
 
// Функция установки разряда
 
void LongInt::Set(unsigned position, unsigned value)
{
    *this += Pow(BASE, position) * LongInt(std::min(value, BASE - 1) - Get(position));
}
 
unsigned LongInt::Get(unsigned position) const
{
    LongInt lDigit = Pow(BASE, position); // единица данного разряда
    LongInt hDigit = position =lDigit * BASE; // единица следующего разряда 
 
    return Abs(*this % hDigit / lDigit).value.to_ulong();
}
 
// Функция деления длинных чисел, считающая частное и остаток.
 
void LongInt::Divide(const LongInt& left, const LongInt& right, LongInt& quotient, LongInt& reminder)
{
    if (right == 0)
         throw std::domain_error("division by zero");
 
    quotient.value.reset();
 
    if (left == right)
    {
        quotient.value.set(0);
    }
    else
    {
        reminder = left;
 
        if (left >= right)
        {
            unsigned leftMsbIndex = 0;
            for (leftMsbIndex = BITS - 1; !left.value[leftMsbIndex] && leftMsbIndex >= 0; --leftMsbIndex);
 
            unsigned rightMsbIndex = 0;
            for (rightMsbIndex = BITS - 1; !right.value[rightMsbIndex] && rightMsbIndex >= 0; --rightMsbIndex);
 
            unsigned alignment = leftMsbIndex - rightMsbIndex;
            LongInt temp(right << alignment);
 
            do
            {
                if (temp <= reminder)
                {
                    quotient.value.set(alignment);
                    reminder -= temp;
                }
 
                temp >>= 1;
            }
            while (alignment--);
        }
    }
}
 
void LongInt::SignedDivide(const LongInt& left, const LongInt& right, LongInt& quotient, LongInt& reminder)
{
    bool leftSign = left < 0;
    bool rightSign = right < 0;
 
    if (leftSign && rightSign)
        Divide(-left, -right, quotient, reminder);
    else if (leftSign && !rightSign)
        Divide(-left, right, quotient, reminder);
    else if (!leftSign && rightSign)
        Divide(left, -right, quotient, reminder);
    else
        Divide(left, right, quotient, reminder);
 
    if (leftSign && rightSign)
    {
        reminder = -reminder;
    }
    else if (leftSign && !rightSign)
    {
        quotient = -quotient;
        reminder = -reminder;
    }
    else if (!leftSign && rightSign)
    {
        quotient = -quotient;
    }
}
 
size_t LongInt::size()
{
	return BITS / (log(BASE) / log(2));
}
 
// Дополнительные возможности реализованы, как свободные функции по тем же причинам, что и бинарные операторы.
 
const LongInt Gcd(const LongInt& left, const LongInt& right)
{
    LongInt a = left, b = right;
 
    while (a > 0 && b > 0)
        a >= b ? a = a % b : b = b % a;
 
    return a + b; //одно из них всегда равно 0
}
 
const LongInt Pow(const LongInt& number, unsigned pow) //быстрое возведение в степень
{
    LongInt result = 1;
    LongInt temp = number;
 
    while (pow)
    {
        if (pow & 1) // pow % 2 == 1
            result *= temp;
 
        temp *= temp;
        pow >>= 1;
    }
    // Можно в одну строчку: while(pow = pow & 1 ? (result *= temp, pow - 1) : (temp *= temp, pow >> 1)); 
    // но будьте готовы, что коллеги вас побьют.
 
    return result;
}
 
const LongInt Abs(const LongInt& number)
{
    return number >= 0 ? number : -number;
}
 
const LongInt Factorial(const LongInt& number)
{
    LongInt result = 1;
 
    if (number > 1)
    {
        LongInt temp = number + 1; // +1, чтобы избежать постфиксного декремента. 
                                  // Постфиксный декремент(как и инкремент) работает медленнее т.к. создает временный объект.
        while (--temp > 0)
            result *= temp;
    }
 
    return result;
}