BitArray

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;

namespace BitArray
{
    class BitArray
    {
        public const int BITS_COUNT = 100100;
        private uint[] bitValues = new uint[BITS_COUNT / 32 + 1];
        private static int digits = 0;
        private static string lastPowerOf2 = "1";
        private static int lastPowerOf2int = 0;
        // Indexer declaration
        public int this[int index]
        {
            get
            {
                if ((index >= 0) && (index < BITS_COUNT))
                {
                    // Calculate the offset
                    int offset = index / 32;
                    int innerIndex = index % 32;
                    // Check the bit at position index
                    return ((bitValues[offset] >> innerIndex) & 1) == 1 ? 1 : 0;
                }
                else
                {
                    throw new IndexOutOfRangeException(String.Format("Index {0} is invalid!", index));
                }
            }

            set
            {
                if ((index < 0) || (index > BITS_COUNT - 1))
                {
                    throw new IndexOutOfRangeException(String.Format("Index {0} is invalid!", index));
                }
                if ((value < 0) || (value > 1))
                {
                    throw new ArgumentException(String.Format("Value {0} is invalid!", value));
                }
                // Calculate the offset
                int offset = index / 32;
                int innerIndex = index % 32;
                // Clear the bit at position index
                bitValues[offset] &= ~((uint)(1 << innerIndex));
                // Set the bit at position index to value
                bitValues[offset] |= (uint)(value << innerIndex);
                if (index > BitArray.digits) BitArray.digits = index;
            }
        }

        //methods
        public override string ToString()
        {
            StringBuilder bitsStr = new StringBuilder();
            int offset = 0;
            //bitsStr.Append(string.Format("bits = \noffset {0,5} :", offset));
            bitsStr.Append(new string(' ', 31 - (BitArray.digits % 32)));
            for (int i = BitArray.digits; i >= 0; i--)
            {
                bitsStr.Append(this[i]);
                if ((i) % 32 == 0)
                {
                    offset++;
                    if (offset % 2 == 0) bitsStr.Append("\n");
                    else bitsStr.Append(" ");
                }
            }
            return bitsStr.ToString();
        }

        public string ToBigDecimal()
        {
            StringBuilder bigStr = new StringBuilder();
            string power = "0";
            string sum = "0";
            for (int i = 0; i < BITS_COUNT; i++)
            {
                if (this[i] == 1)
                {
                    power = BitArray.BigPower2(i);
                    sum = BitArray.SumTwoHugeNumbers(sum, power);
                }
            }
            return sum;
        }

        public static string SumTwoHugeNumbers(string big1, string big2)
        {
            int len1 = big1.Length;
            int len2 = big2.Length;

            if (len1 < len2) big1 = new String('0', len2 - len1) + big1;
            else if (len1 > len2) big2 = new String('0', len1 - len2) + big2;
            char[] ch1 = big1.Reverse().ToArray();
            char[] ch2 = big2.Reverse().ToArray();

            int len = ch1.Length;
            char[] result = new char[len];
            int sum = 0, over = 0;
            for (int i = 0; i < len; i++)
            {
                sum = ch1[i] + ch2[i] + over - 96;
                over = 0;
                if (sum > 9)
                {
                    over = sum / 10;
                    sum %= 10;
                }
                result[i] = (char)(sum + 48);
            }
            string answer = new string(result.Reverse().ToArray());
            if (over > 0) return ((char)(over + 48)).ToString() + answer;
            else return answer;
        }

        public static string BigPower2(int power)
        {
            if (power < 0) throw new ArgumentOutOfRangeException("Power cannot be negative!");
            //if (power < 31) return ((int)(1 << power)).ToString();
            if (power == 0) return "1";

            string tmp = BitArray.lastPowerOf2;
            int i = BitArray.lastPowerOf2int+1;

            if (power<BitArray.lastPowerOf2int)
            {
                i = 0;
                tmp = "1";
            }

            for (; i <= power; i++)
            {
                tmp = BitArray.SumTwoHugeNumbers(tmp, tmp);
            }
            BitArray.lastPowerOf2int = power;
            BitArray.lastPowerOf2 = tmp;
            return tmp;
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            BitArray bits = new BitArray();
            bits[0] = 1;
            bits[1] = 1;
            bits[2] = 0;
            bits[33] = 0;
            bits[10000] = 1;

            Console.WriteLine("Binary representation:\n{0}", bits);
            Stopwatch stopwatch = new Stopwatch();
            stopwatch.Start();
            string hudge = bits.ToBigDecimal();
            Console.WriteLine("Hudge integer representation:\n\n{0}\n\ntotal digits {1}\n", hudge, hudge.Length);
            stopwatch.Stop();
            Console.WriteLine("time taken {0} seconds", stopwatch.Elapsed);

            //Console.WriteLine(BitArray.SumTwoHugeNumbers("123456789012345", "12131234546785465489798784513229"));
            //Console.WriteLine("2 to {0} is {1}", 100, BitArray.BigPower2(100));
        }
    }
}