Thread: Convert binary to decimal string

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    244

    Convert binary to decimal string

    Hello!
    I need to convert a binary expression like
    Code:
    bool[] {1,1,0,1,0,1......1,0,0,1,0,1,1,0,1}
    to a decimal string like
    Code:
    "1890125081"
    the clue is, that the binary number can contain a million binary digits and the resulting decimal string could be very long. it's a little like using Blobs, only i have to do it myself.

    does anyone know how to do this? google couldn't help me at this one... it's damaging my brain right now...
    thanks.

  2. #2
    Registered User
    Join Date
    Mar 2009
    Location
    england
    Posts
    209
    Give this a try, it's based on some javascript online convertor i found here http://compnetworking.about.com/od/b...nvertbases.htm - there's also decimal string back to binary if you want that.

    Code:
    using System;
    
    namespace ConsoleApplication8
    {
        class Program
        {
            static int Main()
            {
                int[] bin = new int[] { 1, 0, 1, 0, 0, 1, 1, 1 }; // should convert to 167
    
                Console.WriteLine(Binary2DecimalString(bin));
                Console.Read();
                return 1;
            }
    
            static String Binary2DecimalString(int[] bin)
            {
                double d = 0;
    
                for (int i = 0; i < bin.Length; i++)
                    d += bin[i] * Math.Pow(2, bin.Length - i - 1);
    
                return d.ToString();
            }
        }
    }
    Last edited by theoobe; 01-21-2010 at 11:53 AM.

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    244
    well, thats the point i described above. you are using double, but my numbers are not 64-bit sized but more like 2^2^32 = 4 GB numbers
    they will never fit into a double...

  4. #4
    Registered User
    Join Date
    May 2003
    Posts
    1,619
    In general, binary to decimal conversion on arbitrarily large numbers is highly challenging; you're running up against the physical limits of how much memory you can allocate.

    For that matter, you can't even CREATE a boolean array with 2^32 entries; 2^31 - 1 is the maximum possible index value since all arrays are indexed with 32 bit signed integers. And on a 32 bit system the runtime wouldn't even be able to allocate that much address space.

    If you really wanted to do it, you'd likely need to use files on disk to store your input and 'variables' -- you'd run out of memory space if you tried to use conventional variables. You'd really only need one key function: Read a decimal 'variable' file, and double the number contained within, optionally incrementing it by one during the doubling.

    The easiest way would be to store the decimal numbers little-endian -- so the number 43,579 would be stored as the bytes [9 7 5 3 4] in a file. Then you'd just have a function that would go byte-by-byte and double the number, carrying any tens digit; for the first digit there'd also be the option to add one. So in this case, say you doubled and did add 1:

    * Compute 9 * 2 + 1 (this is the optional 1) = 19, write 9 to the output stream, save the 1 as a carry to the next digit
    * Compute 7 * 2 + 1 (the carry) = 15, write the 5, carry the 1
    and so on until you've written [ 9 5 1 7 8 ]

    You can actually, assuming you open the output file for both read/write, modify the file in-place so you don't actually need any more than a few bytes of temporary storage (in RAM) to hold digits as they are being processed. Likewise, you could reverse the number at the end of the operation in-place as well, if you wanted to have a far more human-readable big-endian number.



    How would this function help you convert binary to decimal? You use this algorithm to do your conversions:

    1. Start reading the bits starting with the most significant '1' bit. Set the initial output value to be 1, the value of this bit. (of course, if there are no '1' bits, your answer is zero and you're done).

    2. While there are more bits in the number (remember you're reading the binary starting at MSB and moving towards LSB), double the previous output and add the next bit (either 0 or 1 -- this is why the functionality to add 1 is there) -- save this as the new output.

    3. When there are no more bits, your output is now the (little endian) representation of that binary number. You can now reverse the digits if you want it big-endian.


    Oh, and one tip that would make the whole process more efficient: you could write your "doubling and increment" code to read / write an entire cluster at a time (typically 4 KB on modern machines, but somewhat challenging to find programmatically) .
    Last edited by Cat; 01-22-2010 at 06:01 PM.
    You ever try a pink golf ball, Wally? Why, the wind shear on a pink ball alone can take the head clean off a 90 pound midget at 300 yards.

  5. #5
    Registered User
    Join Date
    Jan 2008
    Posts
    244
    ok. here is the conversion algorithm i've found out:
    Code:
    static string DecimalToBase(LargeInt number)
    		{
    			string ret = "";
    			for (; number > 0; number /= 10)
    			{
    				int rem = number % 10;
    				ret = rem + ret;
    			}
    			return ret;
    		}
    it converts my LargeInt to a decimal string. the only problem is, that i would need division and modulu implementation in my LargeInt class.
    i simply don't know how to divide two numbers.

    i'm currently playing arroun with it, i think i'll be getting it solved!
    Last edited by Devils Child; 01-25-2010 at 04:42 AM.

  6. #6
    Registered User
    Join Date
    Mar 2009
    Location
    england
    Posts
    209
    you are using double, but my numbers are not 64-bit sized but more like 2^2^32 = 4 GB numbers they will never fit into a double
    Doubles can be infinite size. See double.IsInfinity(). Decimals are finite.

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    244
    ok. i've got the bin-dec conversion working:
    Code:
    Blob num = Clone();
    					while (num > 0)
    					{
    						num /= 10;
    						Blob rem = ModuloFlag;
    						int rem2 = 0;
    						if (rem.Raw[Size - 1]) rem2++;
    						if (rem.Raw[Size - 2]) rem2 += 2;
    						if (rem.Raw[Size - 3]) rem2 += 4;
    						if (rem.Raw[Size - 4]) rem2 += 8;
    						ret = rem2 + ret;
    					}
    					if (ret.Length == 0) ret = "0";
    but because of those many divisions it is damn slow!!! does anybody know how to speed this up?

  8. #8
    Sweet
    Join Date
    Aug 2002
    Location
    Tucson, Arizona
    Posts
    1,820
    Woop?

  9. #9
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    Quote Originally Posted by Devils Child View Post
    ok. i've got the bin-dec conversion working:
    Code:
    Blob num = Clone();
    					while (num > 0)
    					{
    						num /= 10;
    						Blob rem = ModuloFlag;
    						int rem2 = 0;
    						if (rem.Raw[Size - 1]) rem2++;
    						if (rem.Raw[Size - 2]) rem2 += 2;
    						if (rem.Raw[Size - 3]) rem2 += 4;
    						if (rem.Raw[Size - 4]) rem2 += 8;
    						ret = rem2 + ret;
    					}
    					if (ret.Length == 0) ret = "0";
    but because of those many divisions it is damn slow!!! does anybody know how to speed this up?
    -Don't have all the code, maybe all those ifs can be simplified
    -Since Blob is initialized once, the initialization should be done outside the while-loop, so it doesn't happen all the time.
    -rem2 is not really needed. You can simply directly increase ret.

  10. #10
    Registered User
    Join Date
    Jan 2008
    Posts
    244
    prog-bman: Read the post first, then answer.

    c_nuta: here is my blob code:
    it is a blob class. you can do any math operations on any numbers. the ToString() method converts it to a decimal, i've extracted the ret/=10 code into some binary ops. but it's still slow...
    Code:
    using System;
    using System.Windows.Forms;
    
    namespace LargeNumbers
    {
    	static public class Program
    	{
    		static public void Main()
    		{
    			DateTime time = DateTime.Now;
    			Blob num = new Blob(3).Pow(300);
    			Console.WriteLine(num.ToString());
    			DateTime time2 = DateTime.Now;
    			Console.WriteLine();
    			Console.WriteLine("ms: " + (time2 - time).TotalMilliseconds);
    			Console.ReadKey();
    		}
    	}
    
    	public class Blob
    	{
    		public const int Size = 512;
    		static private readonly ulong[] Potency = 
    		{
    			0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80,0x100,0x200,0x400,0x800,0x1000,0x2000,0x4000,0x8000,0x10000,0x20000,0x40000,0x80000,0x100000,0x200000,0x400000,0x800000,
    			0x1000000,0x2000000,0x4000000,0x8000000,0x10000000,0x20000000,0x40000000,0x80000000,0x100000000,0x200000000,0x400000000,0x800000000,0x1000000000,
    			0x2000000000,0x4000000000,0x8000000000,0x10000000000,0x20000000000,0x40000000000,0x80000000000,0x100000000000,0x200000000000,0x400000000000,0x800000000000,
    			0x1000000000000,0x2000000000000,0x4000000000000,0x8000000000000,0x10000000000000,0x20000000000000,0x40000000000000,0x80000000000000,0x100000000000000,
    			0x200000000000000,0x400000000000000,0x800000000000000,0x1000000000000000,0x2000000000000000,0x4000000000000000,0x8000000000000000,
    		};
    		static public Blob MinValue
    		{
    			get
    			{
    				Blob ret = new Blob();
    				ret.Raw[0] = true;
    				ret.Raw[Size - 1] = true;
    				return ret;
    			}
    		}
    		static public Blob MaxValue
    		{
    			get
    			{
    				Blob ret = new Blob();
    				for (int i = 1; i < Size; i++)
    				{
    					ret.Raw[i] = true;
    				}
    				return ret;
    			}
    		}
    
    		private bool[] Raw;
    		public bool this[int index]
    		{
    			get
    			{
    				if (index < 0 || index >= Size) throw new IndexOutOfRangeException();
    				return Raw[index];
    			}
    			set
    			{
    				if (index < 0 || index >= Size) throw new IndexOutOfRangeException();
    				Raw[index] = value;
    			}
    		}
    
    		public Blob()
    		{
    			Raw = new bool[Size];
    		}
    		public Blob(long number)
    		{
    			Raw = new bool[Size];
    			if (number >= 0)
    			{
    				for (int i = 0; i < 64; i++)
    				{
    					Raw[Size - 64 + i] = (Convert.ToUInt64(number) & Potency[63 - i]) > 0;
    				}
    			}
    			else
    			{
    				number = ~number;
    				for (int i = 0; i < 64; i++)
    				{
    					Raw[Size - 64 + i] = (Convert.ToUInt64(number) & Potency[63 - i]) > 0;
    				}
    				Raw = (~this).Raw;
    			}
    		}
    		private Blob(bool[] raw)
    		{
    			Raw = raw;
    		}
    		static public Blob Parse(string decimalNumber)
    		{
    			return Parse(decimalNumber, NumberFormat.Decimal);
    		}
    		static public Blob Parse(string number, NumberFormat format)
    		{
    			Blob ret = new Blob();
    			switch (format)
    			{
    				case NumberFormat.Binary:
    					for (int i = number.Length - 1; i >= 0; i--)
    					{
    						switch (number[number.Length - i - 1])
    						{
    							case '0':
    								break;
    							case '1':
    								ret.Raw[Size - i - 1] = true;
    								break;
    							default:
    								throw new FormatException();
    						}
    					}
    					break;
    				case NumberFormat.Decimal:
    					bool neg = number.StartsWith("-");
    					if (neg) number = number.Substring(1);
    					Blob p = 1;
    					Blob ten = 10;
    					for (int i = number.Length - 1; i >= 0; i--, p *= ten)
    					{
    						if (number[i] < 48 || number[i] > 57) throw new FormatException();
    						ret += new Blob(Convert.ToInt64(number[i] - 48)) * p;
    					}
    					if (neg) ret = -ret;
    					break;
    				case NumberFormat.Hexadecimal:
    					number = number.ToLower();
    					for (int i = number.Length - 1; i >= 0; i--)
    					{
    						char cur = number[number.Length - i - 1];
    						int cur2 = 0;
    						if (cur > 47 && cur < 58)
    						{
    							cur2 = cur - 48;
    						}
    						else if (cur > 96 && cur < 103)
    						{
    							cur2 = cur - 87;
    						}
    						else
    						{
    							throw new FormatException();
    						}
    						for (int a = 0; a < 4; a++)
    						{
    							ret.Raw[Size - 4 - i * 4 + a] = (Convert.ToUInt32(cur2) & Potency[3 - a]) > 0;
    						}
    					}
    					break;
    			}
    			return ret;
    		}
    
    		public override string ToString()
    		{
    			return ToString(NumberFormat.Decimal);
    		}
    		public string ToString(NumberFormat format)
    		{
    			string ret = "";
    			switch (format)
    			{
    				case NumberFormat.Binary:
    					foreach (bool bo in Raw)
    					{
    						ret += bo ? 1 : 0;
    					}
    					break;
    				case NumberFormat.Decimal:
    					Blob num = Clone();
    					bool neg = Raw[0];
    					if (neg) num = -num;
    					bool m0, m1, m2, m3, m4;
    					while (num > 0)
    					{
    						m0 = false; m1 = false; m2 = false; m3 = false; m4 = false;
    						for (int i = 0; i < Size; i++)
    						{
    							m0 = m1; m1 = m2; m2 = m3;
    							m3 = m4; m4 = num.Raw[0];
    							for (int a = 0; a < Size - 1; a++) num.Raw[a] = num.Raw[a + 1];
    							num.Raw[Size - 1] = false;
    							bool bigger = true;
    							if (m0) bigger = true;
    							else if (!m1) bigger = false;
    							else if (m2) bigger = true;
    							else if (!m3) bigger = false;
    							if (bigger)
    							{
    								bool car = m3;
    								m3 = !m3;
    								if (m2)
    								{
    									m2 = car;
    									car = true;
    								}
    								else
    								{
    									m2 = !car;
    								}
    								m1 ^= car;
    								bool b = true;
    								for (int a = Size - 1; a >= 0 && b; a--)
    								{
    									b = num.Raw[a];
    									num.Raw[a] = true;
    								}
    							}
    						}
    						int rem2 = Convert.ToInt32(m4);
    						if (m3) rem2 += 2;
    						if (m2) rem2 += 4;
    						if (m1) rem2 += 8;
    						ret = rem2 + ret;
    					}
    					if (ret.Length == 0) ret = "0";
    					if (neg) ret = "-" + ret;
    					break;
    				case NumberFormat.Hexadecimal:
    					for (int i = 0; i < Size / 8; i++)
    					{
    						int by = 0;
    						for (int a = 0; a < 8; a++)
    						{
    							if (Raw[i * 8 + a]) by += 1 << 7 - a;
    						}
    						ret += by.ToString("x2");
    					}
    					break;
    			}
    			return ret;
    		}
    		public override int GetHashCode()
    		{
    			return 0;
    		}
    		public override bool Equals(object obj)
    		{
    			return false;
    		}
    		public Blob Clone()
    		{
    			return new Blob((bool[])Raw.Clone());
    		}
    
    		static public Blob operator +(Blob num1, Blob num2)
    		{
    			Blob ret = num1.Clone();
    			bool[] raw1 = ret.Raw, raw2 = num2.Raw;
    			bool car = false;
    			for (int i = Size - 1; i >= 0; i--)
    			{
    				if (raw1[i] ^ raw2[i])
    				{
    					raw1[i] = !car;
    				}
    				else if (raw1[i] && raw2[i])
    				{
    					raw1[i] = car;
    					car = true;
    				}
    				else
    				{
    					raw1[i] = car;
    					car = false;
    				}
    			}
    			return ret;
    		}
    		static public Blob operator ++(Blob num)
    		{
    			bool b = true;
    			for (int i = Size - 1; i >= 0 && b; i--)
    			{
    				b = num.Raw[i];
    				num.Raw[i] = !num.Raw[i];
    			}
    			return num;
    		}
    		static public Blob operator -(Blob num1, Blob num2)
    		{
    			return num1 + ~num2 + 1;
    		}
    		static public Blob operator -(Blob num)
    		{
    			return ~num + 1;
    		}
    		static public Blob operator --(Blob num)
    		{
    			num -= 1;
    			return num;
    		}
    		static public Blob operator *(Blob num1, Blob num2)
    		{
    			Blob res = new Blob();
    			for (int i = 0; i < Size; i++)
    			{
    				if (num2.Raw[i]) res += num1 << Size - i - 1;
    			}
    			return res;
    		}
    		static public Blob operator /(Blob dividend, Blob divisor)
    		{
    			if (divisor == 0) throw new DivideByZeroException();
    			Blob num1 = dividend.Clone(), num2 = divisor.Clone();
    			bool n1s = num1.Raw[0], n2s = num2.Raw[0];
    			if (n1s) num1 = -num1;
    			if (n2s) num2 = -num2;
    			Blob mod = new Blob();
    			for (int i = 0; i < Size; i++)
    			{
    				mod <<= 1;
    				if (num1.Raw[0]) mod.Raw[Size - 1] = true;
    				num1 <<= 1;
    				if (mod >= num2)
    				{
    					mod -= num2;
    					num1++;
    				}
    			}
    			return n1s ^ n2s ? -num1 : num1;
    		}
    		static public Blob operator %(Blob dividend, Blob divisor)
    		{
    			if (divisor == 0) throw new DivideByZeroException();
    			Blob num1 = dividend.Clone(), num2 = divisor.Clone();
    			bool n1s = num1.Raw[0], n2s = num2.Raw[0];
    			if (n1s) num1 = -num1;
    			if (n2s) num2 = -num2;
    			Blob mod = new Blob();
    			for (int i = 0; i < Size; i++)
    			{
    				mod <<= 1;
    				if (num1.Raw[0]) mod.Raw[Size - 1] = true;
    				num1 <<= 1;
    				if (mod >= num2)
    				{
    					mod -= num2;
    					num1++;
    				}
    			}
    			return mod;
    		}
    		static public Blob operator <<(Blob num1, int num2)
    		{
    			if (num2 < 0) return num1 >> -num2;
    			num2 %= Size;
    			Blob ret = new Blob();
    			bool[] raw = ret.Raw;
    			for (int i = 0; i < Size; i++)
    			{
    				int p = i + num2;
    				if (p < 0)
    				{
    					raw[i] = num1.Raw[0];
    				}
    				else if (p >= Size)
    				{
    					raw[i] = false;
    				}
    				else
    				{
    					raw[i] = num1.Raw[p];
    				}
    			}
    			return ret;
    		}
    		static public Blob operator >>(Blob num1, int num2)
    		{
    			if (num2 < 0) return num1 << -num2;
    			num2 %= Size;
    			Blob ret = new Blob();
    			bool[] raw = ret.Raw;
    			for (int i = 0; i < Size; i++)
    			{
    				int p = i - num2;
    				if (p < 0)
    				{
    					raw[i] = num1.Raw[0];
    				}
    				else if (p >= Size)
    				{
    					raw[i] = false;
    				}
    				else
    				{
    					raw[i] = num1.Raw[p];
    				}
    			}
    			return ret;
    		}
    		static public Blob operator ~(Blob num)
    		{
    			Blob ret = new Blob();
    			for (int i = 0; i < Size; i++)
    			{
    				ret.Raw[i] = !num.Raw[i];
    			}
    			return ret;
    		}
    		static public Blob operator |(Blob num1, Blob num2)
    		{
    			Blob ret = new Blob();
    			for (int i = 0; i < Size; i++)
    			{
    				ret.Raw[i] = num1.Raw[i] | num2.Raw[i];
    			}
    			return ret;
    		}
    		static public Blob operator &(Blob num1, Blob num2)
    		{
    			Blob ret = new Blob();
    			for (int i = 0; i < Size; i++)
    			{
    				ret.Raw[i] = num1.Raw[i] & num2.Raw[i];
    			}
    			return ret;
    		}
    		static public Blob operator ^(Blob num1, Blob num2)
    		{
    			Blob ret = new Blob();
    			for (int i = 0; i < Size; i++)
    			{
    				ret.Raw[i] = num1.Raw[i] ^ num2.Raw[i];
    			}
    			return ret;
    		}
    		static public bool operator ==(Blob num1, Blob num2)
    		{
    			for (int i = 0; i < Size; i++)
    			{
    				if (num1.Raw[i] != num2.Raw[i]) return false;
    			}
    			return true;
    		}
    		static public bool operator !=(Blob num1, Blob num2)
    		{
    			for (int i = 0; i < Size; i++)
    			{
    				if (num1.Raw[i] != num2.Raw[i]) return true;
    			}
    			return false;
    		}
    		static public bool operator >(Blob num1, Blob num2)
    		{
    			if (num1.Raw[0] && !num2.Raw[0])
    			{
    				return false;
    			}
    			else if (!num1.Raw[0] && num2.Raw[0])
    			{
    				return true;
    			}
    			else
    			{
    				for (int i = 1; i < Size; i++)
    				{
    					if (num1.Raw[i] != num2.Raw[i]) return num1.Raw[i] && !num2.Raw[i];
    				}
    				return false;
    			}
    		}
    		static public bool operator <(Blob num1, Blob num2)
    		{
    			if (num1.Raw[0] && !num2.Raw[0])
    			{
    				return true;
    			}
    			else if (!num1.Raw[0] && num2.Raw[0])
    			{
    				return false;
    			}
    			else
    			{
    				for (int i = 1; i < Size; i++)
    				{
    					if (num1.Raw[i] != num2.Raw[i]) return !num1.Raw[i] && num2.Raw[i];
    				}
    				return false;
    			}
    		}
    		static public bool operator >=(Blob num1, Blob num2)
    		{
    			return num1 > num2 || num1 == num2;
    		}
    		static public bool operator <=(Blob num1, Blob num2)
    		{
    			return num1 < num2 || num1 == num2;
    		}
    		static public implicit operator Blob(long num)
    		{
    			return new Blob(num);
    		}
    		public Blob Pow(uint pow)
    		{
    			Blob ret = 1;
    			Blob p = Clone();
    			int to = 0;
    			for (int i = 32; i >= 0; i--)
    			{
    				if ((pow & Potency[i]) > 0)
    				{
    					to = i + 1;
    					break;
    				}
    			}
    			for (int i = 0; i < to; i++)
    			{
    				if ((pow & Potency[i]) > 0)
    				{
    					ret *= p;
    				}
    				p *= p;
    			}
    			return ret;
    		}
    	}
    
    	public enum NumberFormat
    	{
    		Binary, Decimal, Hexadecimal
    	}
    }
    Last edited by Devils Child; 01-27-2010 at 04:39 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting binary string to decimal
    By Sharke in forum C Programming
    Replies: 3
    Last Post: 03-30-2009, 12:18 AM
  2. Program using classes - keeps crashing
    By webren in forum C++ Programming
    Replies: 4
    Last Post: 09-16-2005, 03:58 PM
  3. Calculator + LinkedList
    By maro009 in forum C++ Programming
    Replies: 20
    Last Post: 05-17-2005, 12:56 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Another overloading "<<" problem
    By alphaoide in forum C++ Programming
    Replies: 18
    Last Post: 09-30-2003, 10:32 AM