Convert binary to decimal string

Devils Child · 01-21-2010, 09:04 AM

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.

theoobe · 01-21-2010, 11:48 AM

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();
        }
    }
}

Devils Child · 01-22-2010, 03:54 AM

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...

Cat · 01-22-2010, 05:13 AM

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) .

Devils Child · 01-25-2010, 04:25 AM

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!

theoobe · 01-25-2010, 05:59 AM

Quote:

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.

Devils Child · 01-25-2010, 09:22 AM

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?

prog-bman · 01-25-2010, 07:44 PM

Convert.ToInt64 Method (String, Int32) (System)

C_ntua · 01-25-2010, 09:24 PM

Quote:

Originally Posted by Devils Child

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.

Devils Child · 01-26-2010, 07:37 AM

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
	}
}

01-21-2010, 09:04 AM	#1
Devils Child Registered User Join Date: Jan 2008 Posts: 207	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.
Devils Child is offline

01-22-2010, 03:54 AM	#3
Devils Child Registered User Join Date: Jan 2008 Posts: 207	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...
Devils Child is offline

01-22-2010, 05:13 AM	#4
Cat Registered User Join Date: May 2003 Posts: 1,219	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) . __________________ 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. Last edited by Cat; 01-22-2010 at 06:01 PM.
Cat is offline

01-25-2010, 04:25 AM	#5
Devils Child Registered User Join Date: Jan 2008 Posts: 207	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.
Devils Child is offline

01-25-2010, 07:44 PM	#8
prog-bman Sweet Join Date: Aug 2002 Location: Tucson, Arizona Posts: 1,758	Convert.ToInt64 Method (String, Int32) (System) __________________ Woop?
prog-bman is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

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