Алгоритмы - Побитовые операции. Побитовое описание математических операций над целыми числами

// Сложение
public static long Add(long summand, long addend)
{
    // Перенос.
    long carry = 0x00;

    // Итерировать до тех пор, пока не закончится перенос на старший разряд.
    while (addend != 0x00)
    {
        // Выставить флаг под разрядами с установленными битами.
        carry = (summand & addend);

        // Снять с первого слагаемого биты, разряд по которым уже учтен.
        summand = summand ^ addend;

        // Перенос переводится в старший разряд.
        addend = (carry << 1);
    }

    return summand;
}

 +1
 234
+  9
 ___
 243

 1
+1
__
10

 11
+11
___
110

 1111
+  11
_____
10010

carry = (summand & addend);
0011 = 0011 & 0011

summand = summand ^ addend;
0000 = 0011 ^ 0011

addend = (carry << 1);
0110 = (0011 << 1);

carry = (summand & addend);
0000 = 0000 & 0110

summand = summand ^ addend;
0110 = 0000 ^ 0110,

addend = (carry << 1);
0000 = (0000 << 1)

// Вычитание
public static long Sub(long minuend, long subtrahend)
{
    // Отрицательный перенос.
    long borrow = 0x00;

    // Итерировать до тех пор, пока не закончится перенос на младший разряд.
    while (subtrahend != 0x00)
    {
        // Выставить флаг под разрядами с установленными битами.
        borrow = ((~minuend) & subtrahend);

        // Снять с уменьшаемого биты, разряд по которым уже учтен.
        minuend = minuend ^ subtrahend;

        // Перенос переводится в старший разряд.
        subtrahend = (borrow << 1);
    }

    return minuend;
}

borrow = ((~minuend) & subtrahend);
11 = ((~100) & 11) = (11111011 & 11)

minuend = minuend ^ subtrahend;
111 = 100 ^ 11

subtrahend = (borrow << 1);
110 = (11 << 1)

borrow = ((~minuend) & subtrahend);
0 = ((~111) & 110) = (11111000 & 110)

minuend = minuend ^ subtrahend;
1 = 111 ^ 110

subtrahend = (borrow << 1);
0 = (0 << 1)

// Умножение
public static long Multiply(long mul1, long mul2)
{
    // Результат.
    long result = 0;

    // Пока второй множитель не равен нулю.
    while (mul2 != 0)
    {
        // Если установлен бит в очередном разряде...
        if ((mul2 & 1) == 1)
        {
            // сложить первый множитель с самим собою.
            result = Add(result, mul1);
        }

        // Очередной сдвиг первого множителя влево.
        mul1 <<= 1;

        // Подводим очередной разряд в начало для сверки с условием оператора if().
        mul2 >>= 1;
    }

    return result;
}

  234
х  23
_____
  702
+468
_____
 5382

    0111
    0011
    ____
+   0111
+  0111
+ 0000
+0000
________
   10101

if ((mul2 & 1) == 1)
{
    // сложить первый множитель с самим собою.
    result = Add(result, mul1);
}

mul1 <<= 1;

mul2 >>= 1;

// Хотя и входные данные long, их значения должны быть не больше int
public static long Divide(long dividend, long divisor)
{
    // Инициализация результата
    long ans = 0;

    // Получаем знак результата
    bool isNegative = (dividend < 0) ^ (divisor < 0);

    // Получаем модуль числа (абсолютное значение) для входных параметров (делимого и делителя).
    dividend = dividend < 0 ? Add((~dividend), 1) : dividend;
    divisor = divisor < 0 ? Add((~divisor), 1) : divisor;

    // Осуществляем побитовое деление
    for (int i = sizeof(int) * 8 - 1; i > -1; i--)
    {
        if ((divisor << i) <= dividend)
        {
            dividend -= divisor << i;
            ans += 1 << i;
        }
    }

    // Добавляем знак к результату
    return isNegative ? -ans : ans;
}

1024 >> 1 = 102 — деление на 10
1024 << 1 = 10240 — умножение на 10

// Получение остатка от деления
public static long DivisionRemainder(long dividend, long divisor)
{
    // Получаем знак результата
    bool isNegative = (dividend < 0) ^ (divisor < 0);

    // Получаем модуль числа (абсолютное значение) для входных параметров (делимого и делителя).
    dividend = dividend < 0 ? Add((~dividend), 1) : dividend;
    divisor = divisor < 0 ? Add((~divisor), 1) : divisor;

    // Осуществляем побитовое деление и получаем остаток
    for (int i = sizeof(int) * 8 - 1; i > -1; i--)
    {
        if ((divisor << i) <= dividend)
        {
            dividend -= divisor << i;
        }
    }

    // Добавляем знак к результату
    return isNegative ? -dividend : dividend;
}

// Author: Dmitriy Sidyakin
// Date: 2021-10-02

using System;
using System.Collections.Generic;

namespace BitMath
{
    /// <summary>
    /// Represents an Unlimited Integer in a memory.
    /// The class is represented in RAM byte-by-byte. Integer operations are also performed.
    /// </summary>
    public class UnlimitedInteger: ICloneable
    {
        #region Fields

        /// <summary>
        /// Protected variable: The sign of Integer. Asked on the question: Is an Integer Negative?
        /// </summary>
        protected bool _isNegative;

        /// <summary>
        /// The sign of Integer. Asked on the question: Is an Integer Negative?
        /// </summary>
        public bool IsNegative
        {
            get
            {
                return _isNegative;
            }
            set
            {
                _isNegative = value;
            }
        }

        /// <summary>
        /// The Byte Representation of Integer is from the Low (the start index is 0) to the High (the end index is Lenght - 1).
        /// </summary>
        protected List<byte> _bytes;

        /// <summary>
        /// The Bytes of Integer part without sign.
        /// </summary>
        public byte[] Bytes
        {
            get
            {
                byte[] result = new byte[Length];
                if (Length > 0)
                    _bytes.CopyTo(result);
                return result;
            }
        }

        /// <summary>
        /// The Length of Integer is in bytes (byte count) without sign.
        /// </summary>
        public int Length
        {
            get
            {
                return _bytes.Count;
            }
        }

        #endregion

        #region Constructors

        public UnlimitedInteger(byte[] bytes, bool isNegative)
        {
            _bytes = new List<byte>(bytes);
            this.DeleteHighZeroBytes();
            _isNegative = isNegative;
        }

        #endregion

        #region Object methods

        public override bool Equals(object obj)
        {
            if (obj == null)
                return false;

            if (GetType() != obj.GetType())
                return false;

            UnlimitedInteger co = (UnlimitedInteger)obj;

            return this == co;
        }

        public override int GetHashCode()
        {
            byte additionalElements = 0;
            int sizeOfInt = sizeof(int);
            int additionalBytes = _bytes.Count % sizeOfInt;
            if (additionalBytes > 0)
            {
                additionalElements = 1;
            }

            int[] result = new int[_bytes.Count / sizeOfInt + additionalElements];
            int index = 0;

            while (index < result.Length)
            {
                if (index < (result.Length - 1))
                {
                    for (int i = 0; i < sizeOfInt; i++)
                    {
                        result[index] |= _bytes[index + i];

                        if (i < (sizeOfInt - 1))
                        {
                            result[index] <<= 8;
                        }
                    }
                }
                else
                {
                    for (int i = 0; i < additionalBytes; i++)
                    {
                        result[index] |= _bytes[index + i];

                        if (i < (sizeOfInt - 1))
                        {
                            result[index] <<= 8;
                        }
                    }
                }
                ++index;
            }

            int hashCode = 0;

            for (int i = 0; i < result.Length; i++)
                hashCode ^= result[i];

            return hashCode;
        }

        #endregion

        #region Comparison Operators (x == y, x != y, x < y, x > y, x <= y, x >= y)

        public static bool operator ==(UnlimitedInteger a, UnlimitedInteger b)
        {

            if (a.Length != b.Length)
                return false;

            if (a.IsNegative != b.IsNegative)
                return false;

            bool result = true;

            int currentByte = a.Length - 1;
            while (result && currentByte >= 0)
            {
                result = a._bytes[currentByte] == b._bytes[currentByte];
                --currentByte;
            }

            return result;
        }

        public static bool operator !=(UnlimitedInteger a, UnlimitedInteger b)
        {
            return !(a == b);
        }

        public static bool operator <(UnlimitedInteger a, UnlimitedInteger b)
        {
            if (a.Length < b.Length)
                return true;
            if (a.Length > b.Length)
                return false;

            int firstDifferentByteIndexFromHigh = a.Length - 1;
            while (firstDifferentByteIndexFromHigh >= 0 && a._bytes[firstDifferentByteIndexFromHigh] == b._bytes[firstDifferentByteIndexFromHigh]) { --firstDifferentByteIndexFromHigh; }

            if (firstDifferentByteIndexFromHigh == -1)
                return false;
            else
                return a._bytes[firstDifferentByteIndexFromHigh] < b._bytes[firstDifferentByteIndexFromHigh];
        }

        public static bool operator >(UnlimitedInteger a, UnlimitedInteger b)
        {
            if (a.Length > b.Length)
                return true;
            if (a.Length < b.Length)
                return false;

            int firstDifferentByteIndexFromHigh = a.Length - 1;
            while (firstDifferentByteIndexFromHigh >= 0 && a._bytes[firstDifferentByteIndexFromHigh] == b._bytes[firstDifferentByteIndexFromHigh]) { --firstDifferentByteIndexFromHigh; }

            if (firstDifferentByteIndexFromHigh == -1)
                return false;
            else
                return a._bytes[firstDifferentByteIndexFromHigh] > b._bytes[firstDifferentByteIndexFromHigh];
        }

        public static bool operator <=(UnlimitedInteger a, UnlimitedInteger b)
        {
            if (a.Length < b.Length)
                return true;
            if (a.Length > b.Length)
                return false;

            int firstDifferentByteIndexFromHigh = a.Length - 1;
            while (firstDifferentByteIndexFromHigh >= 0 && a._bytes[firstDifferentByteIndexFromHigh] == b._bytes[firstDifferentByteIndexFromHigh] && firstDifferentByteIndexFromHigh >= 0) { --firstDifferentByteIndexFromHigh; }

            if (firstDifferentByteIndexFromHigh == -1)
                return true;
            else
                return a._bytes[firstDifferentByteIndexFromHigh] < b._bytes[firstDifferentByteIndexFromHigh];
        }

        public static bool operator >=(UnlimitedInteger a, UnlimitedInteger b)
        {
            if (a.Length > b.Length)
                return true;
            if (a.Length < b.Length)
                return false;

            int firstDifferentByteIndexFromHigh = a.Length - 1;
            while (firstDifferentByteIndexFromHigh >= 0 && a._bytes[firstDifferentByteIndexFromHigh] == b._bytes[firstDifferentByteIndexFromHigh]) { --firstDifferentByteIndexFromHigh; }

            if (firstDifferentByteIndexFromHigh == -1)
                return true;
            else
                return a._bytes[firstDifferentByteIndexFromHigh] > b._bytes[firstDifferentByteIndexFromHigh];
        }

        #endregion

        #region Delete High zero bytes

        protected void DeleteHighZeroBytes()
        {
            int highIndex = _bytes.Count - 1;

            while (highIndex > 0 && _bytes[highIndex] == 0)
            {
                --highIndex;
            }

            _bytes.RemoveRange(highIndex + 1, _bytes.Count - highIndex - 1);
        }

        #endregion

        #region Bitwise Operators (x & y, x | y, x ^ y, x << y, x >> y)

        public static UnlimitedInteger operator &(UnlimitedInteger a, UnlimitedInteger b)
        {
            int minLength = a.Length > b.Length ? b.Length : a.Length;

            byte[] result = new byte[minLength];

            for (int i = 0; i < minLength; i++)
            {
                result[i] = (byte)(a._bytes[i] & b._bytes[i]);
            }

            UnlimitedInteger resultUnlimited = new UnlimitedInteger(result, a.IsNegative & b.IsNegative);
            resultUnlimited.DeleteHighZeroBytes();

            return resultUnlimited;
        }

        /// <summary>
        /// Getting min and max values from (a,b). Exception: if a==b then min = a, max = b.
        /// </summary>
        /// <param name="a">First comparable element</param>
        /// <param name="b">Second comparable element</param>
        /// <param name="min">Minimum from elements</param>
        /// <param name="max">Maximum from elements</param>
        private static void GetMinMax(UnlimitedInteger a, UnlimitedInteger b, out UnlimitedInteger min, out UnlimitedInteger max)
        {
            if (a > b)
            {
                min = b; max = a;
            }
            else
            {
                min = a; max = b;
            }
        }

        public static UnlimitedInteger operator |(UnlimitedInteger a, UnlimitedInteger b)
        {
            UnlimitedInteger min, max;
            GetMinMax(a, b, out min, out max);

            byte[] result = new byte[max.Length];

            int copiedIndex = 0;
            for (int i = 0; i < min.Length; i++)
            {
                result[i] = (byte)(min._bytes[i] | max._bytes[i]);
                ++copiedIndex;
            }

            for (int i = copiedIndex; i < max.Length; i++)
            {
                result[i] = max._bytes[i];
            }

            UnlimitedInteger resultUnlimited = new UnlimitedInteger(result, a.IsNegative | b.IsNegative);
            resultUnlimited.DeleteHighZeroBytes();

            return resultUnlimited;
        }

        public static UnlimitedInteger operator ^(UnlimitedInteger a, UnlimitedInteger b)
        {
            UnlimitedInteger min, max;
            GetMinMax(a, b, out min, out max);

            byte[] result = new byte[max.Length];

            int copiedIndex = 0;
            for (int i = 0; i < min.Length; i++)
            {
                result[i] = (byte)(min._bytes[i] ^ max._bytes[i]);
                ++copiedIndex;
            }

            for (int i = copiedIndex; i < max.Length; i++)
            {
                result[i] = max._bytes[i];
            }

            UnlimitedInteger resultUnlimited = new UnlimitedInteger(result, a.IsNegative ^ b.IsNegative);
            resultUnlimited.DeleteHighZeroBytes();

            return resultUnlimited;
        }

        public static UnlimitedInteger operator <<(UnlimitedInteger a, int b)
        {

            if (b == 0)
            {
                return (UnlimitedInteger)a.Clone();
            }

            if (b < 0)
                return a >> Math.Abs(b);

            UnlimitedInteger result;

            int additionalBytes = b / 8;
            int shift = b % 8;

            if (shift > 0)
            {
                additionalBytes++;
            }

            int size = a.Length + additionalBytes;

            result = new UnlimitedInteger(a.Bytes, a.IsNegative);
            for (int i = 0; i < additionalBytes; i++)
                result._bytes.Insert(0, 0);

            if (shift > 0)
            {
                int unshift = 8 - shift;

                result >>= unshift;
            }

            result.DeleteHighZeroBytes();

            return result;
        }

        public static UnlimitedInteger operator >>(UnlimitedInteger a, int b)
        {
            if (b == 0)
            {
                return (UnlimitedInteger)a.Clone();
            }
            if (b == 8)
            {
                ;
            }

            if (b < 0)
                return a << Math.Abs(b);

            UnlimitedInteger result;

            int additionalBytes = b / 8;
            int shift = b % 8;

            int size = 1;
            if (a.Length > 1)
                size = a.Length - additionalBytes;

            byte[] newResult = new byte[size];
            for (int i = additionalBytes, j = 0; i < a.Length; i++, j++)
            {
                newResult[j] = a._bytes[i];
            }

            result = new UnlimitedInteger(newResult, a.IsNegative);

            if (shift != 0)
            {
                for (int i = 1; i < result.Length; i++)
                {
                    result._bytes[i - 1] = (byte)((result._bytes[i - 1]) >> shift);
                    result._bytes[i - 1] = (byte)((result._bytes[i] << (8 - shift)) | result._bytes[i - 1]);
                }

                result._bytes[result.Length - 1] >>= shift;
            }

            result.DeleteHighZeroBytes();

            return result;
        }

        #endregion

        #region Unary Operators (+x, -x, !x, ~x, ++, --, true, false)

        public static UnlimitedInteger operator +(UnlimitedInteger x)
        {
            return (UnlimitedInteger)x.Clone();
        }

        public static UnlimitedInteger operator -(UnlimitedInteger x)
        {
            UnlimitedInteger result = new UnlimitedInteger(x.Bytes, !x.IsNegative);
            return result;
        }

        public static bool operator true(UnlimitedInteger x)
        {
            bool result = true;
            if (x.Length == 1 && x._bytes[0] == 0)
                result = false;
            return result;
        }

        public static bool operator false(UnlimitedInteger x)
        {
            bool result = false;
            if (x.Length == 1 && x._bytes[0] == 0)
                result = true;
            return result;
        }

        public static bool operator !(UnlimitedInteger x)
        {
            bool result = true;
            if (x)
                result = false;
            return result;
        }

        public static UnlimitedInteger operator ~(UnlimitedInteger x)
        {
            UnlimitedInteger result = new UnlimitedInteger(x.Bytes, !x.IsNegative);

            for (int index = 0; index < result.Length; index++)
            {
                result._bytes[index] = (byte)~result._bytes[index];
            }

            result.DeleteHighZeroBytes();

            return result;
        }


        public static UnlimitedInteger operator ++(UnlimitedInteger x)
        {
            UnlimitedInteger result;

            if (x.IsNegative)
            {
                if (!x)
                    result = One();
                else
                {
                    result = UnlimitedInteger.SubPositive(x, One());
                    result.IsNegative = true;
                }
            }
            else
            {
                if (!x)
                    result = One();
                else
                {
                    result = UnlimitedInteger.AddPositive(x, One());
                    result.IsNegative = false;
                }
            }

            result.DeleteHighZeroBytes();

            return result;
        }

        public static UnlimitedInteger operator --(UnlimitedInteger x)
        {
            UnlimitedInteger result;

            if (x.IsNegative)
            {
                if (!x)
                    result = MinusOne();
                else
                {
                    result = UnlimitedInteger.AddPositive(x, One());
                    result.IsNegative = true;
                }
            }
            else
            {
                if (!x)
                    result = MinusOne();
                else
                {
                    result = UnlimitedInteger.SubPositive(x, One());
                    result.IsNegative = false;
                }
            }

            result.DeleteHighZeroBytes();

            return result;
        }

        #endregion

        #region Maths Operations (x + y, x - y, x * y, x / y, x % y)

        private static UnlimitedInteger AddPositive(UnlimitedInteger summand, UnlimitedInteger added)
        {
            int maskLenght = summand.Length > added.Length ? summand.Length : added.Length;
            maskLenght++;
            byte[] maskBytes = new byte[maskLenght];
            for (int i = 0; i < (maskLenght - 1); i++)
            {
                maskBytes[i] = 0xFF;
            }
            maskBytes[maskLenght - 1] = 0b0000_0001;

            UnlimitedInteger carry = Zero(),
                myAdded = (UnlimitedInteger)added.Clone(),
                mySummand = (UnlimitedInteger)summand.Clone(),
                mask = new UnlimitedInteger(maskBytes, false);

            while (myAdded.Length > 1 || (myAdded.Length == 1 && myAdded._bytes[0] != 0))
            {
                carry = (mySummand & myAdded);

                mySummand = mySummand ^ myAdded;

                myAdded = (carry << 1) & mask;
            }

            return mySummand;
        }

        private static UnlimitedInteger SubPositive(UnlimitedInteger minuend, UnlimitedInteger subtrahend)
        {
            if (minuend < subtrahend)
                throw new ArgumentOutOfRangeException("Minuend must be higher or equal subtrahend");

            int maskLenght = minuend.Length;

            byte[] maskBytes = new byte[maskLenght];
            for (int i = 0; i < maskLenght; i++)
            {
                maskBytes[i] = 0xFF;
            }


            UnlimitedInteger borrow = Zero(),
                myMinuend = (UnlimitedInteger)minuend.Clone(),
                mySubtrahend = (UnlimitedInteger)subtrahend.Clone(),
                mask = new UnlimitedInteger(maskBytes, false);


            while (mySubtrahend.Length > 1 || (mySubtrahend.Length == 1 && mySubtrahend._bytes[0] != 0))
            {

                borrow = ((~myMinuend) & mySubtrahend);

                myMinuend = myMinuend ^ mySubtrahend;

                mySubtrahend = (borrow << 1) && mask;
            }

            return myMinuend;
        }

        public static UnlimitedInteger operator +(UnlimitedInteger a, UnlimitedInteger b)
        {
            UnlimitedInteger result;

            // Если у них разные знаки
            if (a.IsNegative ^ b.IsNegative)
            {
                // ... то делаем вычитание ...
                if (a._isNegative)
                {
                    if (a > b)
                    {
                        result = SubPositive(a, b);
                        result._isNegative = true;
                    }
                    else
                    {
                        result = SubPositive(b, a);
                        result._isNegative = false;
                    }
                }
                else
                {
                    if (b > a)
                    {
                        result = SubPositive(b, a);
                        result._isNegative = true;
                    }
                    else
                    {
                        result = SubPositive(a, b);
                        result._isNegative = false;
                    }
                }
            }
            else
            {
                // ... иначе сложение
                result = AddPositive(a, b);
                result._isNegative = a._isNegative;
            }

            return result;
        }

        public static UnlimitedInteger operator -(UnlimitedInteger a, UnlimitedInteger b)
        {
            UnlimitedInteger result;

            // Если у них разные знаки
            if (a.IsNegative ^ b.IsNegative)
            {
                // ... иначе сложение
                result = AddPositive(a, b);
                result._isNegative = a._isNegative;

            }
            else
            {
                // ... то делаем вычитание ...
                if (a._isNegative)
                {
                    if (a > b)
                    {
                        result = SubPositive(a, b);
                        result._isNegative = true;
                    }
                    else
                    {
                        result = SubPositive(b, a);
                        result._isNegative = false;
                    }
                }
                else
                {
                    if (b > a)
                    {
                        result = SubPositive(b, a);
                        result._isNegative = true;
                    }
                    else
                    {
                        result = SubPositive(a, b);
                        result._isNegative = false;
                    }
                }
            }

            return result;
        }

        public static UnlimitedInteger operator *(UnlimitedInteger a, UnlimitedInteger b)
        {
            // Результат.
            UnlimitedInteger result = Zero();

            UnlimitedInteger mul1 = (UnlimitedInteger)a.Clone(), mul2 = (UnlimitedInteger)b.Clone();

            mul1.IsNegative = false;
            mul2.IsNegative = false;

            // Пока второй множитель не равен нулю.
            while (mul2 != Zero())
            {
                // Если установлен бит в очередном разряде...
                if ((mul2 & One()) == One())
                {
                    // сложить первый множитель с самим собою.
                    result = AddPositive(result, mul1);
                }

                // Очередной сдвиг первого множителя влево.
                mul1 <<= 1;

                // Подводим очередной разряд в начало для сверки с условием оператора if().
                mul2 >>= 1;
            }

            result.IsNegative = a.IsNegative ^ b.IsNegative;

            return result;
        }
        public static UnlimitedInteger operator /(UnlimitedInteger a, UnlimitedInteger b)
        {
            if (a < b)
            {
                return Zero();
            }
            if (a == b)
            {
                return One();
            }
            if (b == Zero())
            {
                throw new DivideByZeroException();
            }

            // Результат.
            UnlimitedInteger result = Zero();

            UnlimitedInteger dividend = (UnlimitedInteger)a.Clone(), divisor = (UnlimitedInteger)b.Clone();

            dividend.IsNegative = false;
            divisor.IsNegative = false;

            int length = a.Length * 8 - 1;

            for (int i = length; i > -1; i--)
            {
                if ((divisor << i) <= dividend)
                {
                    dividend -= divisor << i;
                    result += One() << i;
                }
            }

            result.IsNegative = a.IsNegative ^ b.IsNegative;
            return result;
        }

        private static int GetLastOneBitPossition(UnlimitedInteger a)
        {
            for (int i = a.Length * 8 - 1; i > -1; i--)
            {
                if (a >> i != Zero())
                {
                    return i - 1;
                }
            }

            return -1;
        }

        private static bool IsMinus(UnlimitedInteger a, UnlimitedInteger b)
        {
            if ((a && b) == b)
            {
                return false;
            }
            else
            {
                return true;
            }
        }

        public static UnlimitedInteger operator %(UnlimitedInteger a, UnlimitedInteger b)
        {
            return Remainder(a, b);
        }

        private static UnlimitedInteger Remainder(UnlimitedInteger a, UnlimitedInteger b)
        {
            if (a < b)
            {
                return (UnlimitedInteger)a.Clone();
            }
            if (a == b)
            {
                return Zero();
            }
            if (b == Zero())
            {
                throw new DivideByZeroException();
            }

            // Результат.
            UnlimitedInteger result = Zero();

            UnlimitedInteger dividend = (UnlimitedInteger)a.Clone(), divisor = (UnlimitedInteger)b.Clone();

            dividend.IsNegative = false;
            divisor.IsNegative = false;

            int length = a.Length * 8 - 1;

            for (int i = length; i > -1; i--)
            {
                if ((divisor << i) <= dividend)
                {
                    dividend -= divisor << i;
                    result += One() << i;
                }
            }

            dividend.IsNegative = a.IsNegative ^ b.IsNegative;
            return dividend;
        }

        #endregion

        #region Math Functions

        public bool IsEven()
        {
            return (this && One()) == Zero();
        }

        public bool IsOdd()
        {
            return (this && One()) == One(); ;
        }

        #endregion

        #region ToString Operations

        public string ToString(byte @base)
        {
            if (!(@base == 2 || @base == 8 || @base == 10 || @base == 16))
                throw new ArgumentOutOfRangeException("@base", "Avaliable values: 2, 8, 10, 16");

            string result = String.Empty;

            if (@base != 10)
            {
                if (@base == 2)
                {
                    for (int i = 0; i < _bytes.Count; i++)
                    {
                        result = Convert.ToString((int)(_bytes[i]) ^ 0b100000000, @base).Substring(1, 8) + result;
                    }
                    result = TrimLeftWithChar(result, '0');

                    if (result.Length == 0)
                        result = "0";
                }

                if (@base == 16)
                {
                    for (int i = 0; i < _bytes.Count; i++)
                    {
                        result = Convert.ToString(_bytes[i] ^ 0b100000000, @base).Substring(1, 2) + result;
                    }
                    result = TrimLeftWithChar(result, '0');

                    if (result.Length == 0)
                        result = "0";
                }

                if (@base == 8)
                {
                    UnlimitedInteger forOctal = (UnlimitedInteger)Clone();

                    while (forOctal.Length > 1)
                    {
                        result = Convert.ToString(forOctal._bytes[0] & 0b00000111, @base).Substring(0, 1) + result;

                        forOctal >>= 3;
                    }

                    byte lastByte = forOctal._bytes[0];

                    while (lastByte != 0)
                    {
                        while (lastByte != 0)
                        {
                            result = Convert.ToString(lastByte & 0b00000111, @base).Substring(0, 1) + result;

                            lastByte >>= 3;
                        }
                    }
                }
            }
            else
            {
                UnlimitedInteger dec = (UnlimitedInteger)Clone();
                dec.IsNegative = false;
                while (dec != Zero())
                {
                    result = (dec % Ten()).Bytes[0].ToString() + result;
                    dec = dec / Ten();
                }

                if (String.IsNullOrEmpty(result))
                {
                    result = "0";
                }
            }

            if (IsNegative)
            {
                result = "-" + result;
            }

            return result;
        }

        private static string TrimLeftWithChar(string input, char chr)
        {
            int count = 0;

            while (count < input.Length && input[count] == chr) count++;

            return input.Substring(count);
        }

        #endregion

        #region ICloneable Interface

        public object Clone()
        {
            UnlimitedInteger result = new UnlimitedInteger(this.Bytes, this.IsNegative);
            return result;
        }

        #endregion

        #region Constants

        public static UnlimitedInteger One()
        {
            return new UnlimitedInteger(new byte[1] { 1 }, false);
        }

        public static UnlimitedInteger MinusOne()
        {
            return new UnlimitedInteger(new byte[1] { 1 }, true);
        }

        public static UnlimitedInteger Zero()
        {
            return new UnlimitedInteger(new byte[1] { 0 }, false);
        }

        public static UnlimitedInteger Ten()
        {
            return new UnlimitedInteger(new byte[1] { 10 }, false);
        }

        #endregion

        #region Parse

        public static UnlimitedInteger Parse(string str)
        {
            int startIndex = 0;

            bool isNeg = false;
            if (str[0] == '-')
            {
                isNeg = true;
                startIndex++;
            }

            UnlimitedInteger result = UnlimitedInteger.Zero();
            UnlimitedInteger j = UnlimitedInteger.One();
            for (int i = str.Length - 1; i >= startIndex; i--, j *= UnlimitedInteger.Ten())
            {
                byte digit = byte.Parse(str[i].ToString());
                UnlimitedInteger uiDigit = new UnlimitedInteger(new byte[] { digit }, false);
                result += uiDigit * j;
            }

            result.IsNegative = isNeg;

            return result;
        }

        #endregion
    }
}