For instance, How would I be able to convert 2^60 or 12345678901234567890123456789012345678901234567890 to binary?
Basically, numbers that are too large to represent in Java.
Edit: I will be making a class that will be able to represent number that are too large. I'm just having a hard time figuring our how to convert decimal to binary.
Edit2: And also, I am not allowed to use BigDecimal, BigInteger, or any other library, sorry for not specifying earlier.
Here is a quik&dirty (very very very dirty) code:
public class BigDec2Bin {
public static int[] string2arrayReversed( String s )
{
char a[] = s.toCharArray();
int b[] = new int[ s.length() ];
for( int i = 0; i < a.length; i++ )
{
b[a.length-1-i] = a[i] - 48;
}
return b;
}
// adds two binary numbers represented as strings
public static String add( String s1, String s2 )
{
String result = "", stmp;
int[] a1, a2;
int ctmp, mark = 0;
// a1 should be the longer one
a1 = string2arrayReversed( ( s1.length() > s2.length() ? s1 : s2 ) );
a2 = string2arrayReversed( ( s1.length() < s2.length() ? s1 : s2 ) );
for( int i = 0; i < a1.length; i++ )
{
ctmp = a1[i] + ( i < a2.length ? a2[i] : 0 ) + mark;
switch( ctmp )
{
default:
case 0:
stmp = "0";
mark = 0;
break;
case 1:
stmp = "1";
mark = 0;
break;
case 2:
stmp = "0";
mark = 1;
break;
case 3:
stmp = "1";
mark = 1;
break;
}
result = stmp + result;
}
if( mark > 0 ) { result = "1" + result; }
return result;
}
public static String dec2bin( String s )
{
String result = "";
for( int i = 0; i < s.length() ; i++ )
{
result = add( result + "0", result + "000" );
result = add( result, Integer.toBinaryString( s.charAt(i) - 48 ) );
}
return result;
}
public static void main( String[] args )
{
String dec = "12345"; // should be 11000000111001
System.out.println( "dec2bin( " + dec + " ) = " + dec2bin( dec ) );
dec = "12345678901234567890123456789012345678901234567890";
System.out.println( "dec2bin( " + dec + " ) = " + dec2bin( dec ) );
}
}
Output:
dec2bin( 12345 ) = 011000000111001
dec2bin( 12345678901234567890123456789012345678901234567890 ) = 10000111001001111111011000110110100110101010111110000011110010100001010100000010011001110100011110101111100011000111111100011001011011001110001111110000101011010010
My main idea is to use always strings.
add -method adds two binary numbers which are represented as strings
dec2bin -method is where the magic happens.
Allow me to explain:
result = add( result + "0", result + "000" );
is a calculation to multiply any given number by 10.
Multiplying a binary number by 10 is the same as adding the number with shifts:
x*10 <=> x<<1 + x<<3
result = add( result, Integer.toBinaryString( s.charAt(i) - 48 ) );
just adds a the next digit (from left to right) on the result string
Basicly what I'm doing is for example with 1234:
0*10 + 1 = 1
1*10 + 2 = 12
12*10 + 3 = 123
123*10 + 4 = 1234
but only in binary (represented as strings).
I hope i could help and sorry for my bad english.
Try this:
new BigDecimal("12345678901234567890123456789012345678901234567890").toString(2);
Edit:
For making a big-number class, you may want to have a look at my post about this a week ago. Ah, the question was by you, never mind.
The conversion between different number systems in principle is a repeated "division, remainder, multiply, add" operation. Let's look at an example:
We want to convert 123 from decimal to a base 3 number. What do we do?
So it looks like this:
123 % 3 == 0. ==> The last digit is 0.123 / 3 == 41.41 % 3 == 2 ==> The second last digit is 2.41 / 3 == 1313 % 3 == 1 ==> The third digit is 1.13 / 3 == 44 % 3 == 1 ==> The fourth digit is 1 again.4 / 3 == 11 % 3 == 1 ==> The fifth digit is 1.So, we have 11120 as the result.
The problem is that for this you need to have already some kind of division by 3 in decimal format, which is usually not the case if you don't implement your number in a decimal-based format (like I did in the answer to your last question linked above).
But it works for converting from your internal number format to any external format.
So, let's look at how we would do the inverse calculation, from 11120 (base 3) to its decimal equivalent. (Base 3 is here the placeholder for an arbitrary radix, Base 10 the placeholder for your internal radix.) In principle, this number can be written as this:
1 * 3^4 + 1 * 3^3 + 1*3^2 + 2*3^1 + 0*3^0
A better way (faster to calculate) is this:
((((1 * 3) + 1 )*3 + 1 )*3 + 2)*3 + 0
1
3
4
12
13
39
41
123
123
(This is known as Horner scheme, normally used for calculating values of polynomials.)
You can implement this in the number scheme you are implementing, if you know how to represent the input radix (and the digits) in your target system.
(I just added such a calculation to my DecimalBigInt class, but you may want to do the calculations directly in your internal data structure instead of creating a new object (or even two) of your BigNumber class for every decimal digit to be input.)
What about this approach:
result = 0;
for each digit in the decimal number, from left to right
result = result * 10 + digit;
return result;
So we need a way to represent an arbitrarily large binary number, and implement multiplication by 10 and addition of small numbers.
The most straightforward way to represent an arbitrarily large binary number is an array of its binary digits. You can then apply the algorithms for addition and multiplication your learned in elementary school, except that digits will "overflow" when they exceed 1 rather than 9. For example:
1010 * 1100111
----------------
11001110
+ 1100111000
----------------
10000000110
Pew: thanks, that works for some numbers. The number 6123456789012 however doesn't work, but here is the fix:
// a1 should be the longer one
a1 = string2arrayReversed( ( s1.length() >= s2.length() ? s1 : s2 ) ); //GREATER EQUAL
there is a fast program to get the binary representation of a huge decimal. This programm is indeed fast, it takes only 20ms to deal with a decimal with 3000digits, eg:string(3000,'2')+'12345'. because of the pursuit of efficiency, it is not very readable. you can modify it yourself to make it easier to understand.
inline string remove_pre_zero(const string& a)
{
auto t = a.find_first_not_of('\0', 0);
if (t == a.npos)
return string("0");
else
return a.substr(t);
}
string convert_to_bin(const string& _s)
{
const static string str[] = { "0", "1" };
string s(_s.size(), '0');
string binary;
binary.reserve(_s.size()*3);
int i = 0;
for (const auto& c : _s)
s[i++] = (c - '0');
while (s!="0")//simulate divide by 2
{
int t = 0, old_t = 0;
for (auto& ch : s)
{
t = ((old_t * 10 + ch) & 1);
ch = (ch + old_t * 10) >>1;
old_t = t;
}
binary += str[t];
if (s[0] == 0)
s = remove_pre_zero(s);
}
return string(binary.rbegin(), binary.rend());
}
If you only work with integers, use BigInteger.toByteArray.
If not, unfortunately BigDecimal doesn't have that method. But I suppose you can always (in both cases) just ASCII encode the string representation of the number, if the binary form is just meant for transfer and not calculation anywhere.
