[EDITED]
Apologies if this has been answered already in a different thread. I was asked this question in a recent interview. Given a large string of integers(> 64bit), say, "163878712638127812737637876347236482", how would you convert it to binary? This should be done without the use of binary related java API or libraries.
Brett's method should work. But in case that you are not allowed to use any external libraries, you can treat the string as an array of digits and perform long division on it. So you divide the number by 2 repeatedly until you get 0 or 1 left. You might have to write your own method to do the division on an array of digits (deal with leftovers and remainders), but it should have a pretty good run time.
Here's an example: Lets say you have the string 163878712638127812737637876347236482. Convert it to an array of ints (or shorts if memory is a concern). Perform a long division by 2, keep result in a separate array and keep track of the remainder:
int[] answer = new int[input.length]; //create the answer array
String binary = "";
public void convert(input, answer){
for(int i=input.length-1;i<=0;i--) //you want to start from the left end
{
int temp = input[i]/2; //int division, disregard decimal.
answer[i] = temp;
int remainder = input[i] - temp*2; //will be 1 or 0, carry over to the next digit
if(i>0) //check if we are not at the last digit
input[i-1] += 10*remainder;
else
binary = remainder+binary; //add new bit to the left of the binary
}
if(answer_is_smaller_than_2) //check if we have 0 or 1 left, maybe just go through the answer array
binary = answer[0]+binary;// add the last digit to binary string. It is generally ok to have a 0 in the beginning, but you can easily do a check and remove the 0
else convert(answer, new int[answer.length]); //keep dividing
}
Sorry that the recursion is not very polished. I wrote it on a run. For more information on converting decimal to binary: http://www.wikihow.com/Convert-from-Decimal-to-Binary Hope this helps :)
I got to thinking about this problem and here's finally my solution. I was able to validate the output for 10 digit long numeric strings, but not for the string used in the program. It'd be great if someone can verify and tell me if the solution is correct. Also, the solution is unoptimized, so please feel free to suggest changes:
public class BinaryString {
String finArr = "";
public static void main(String[] args) {
String num = "37489237892374892734872398479827498238932787";
BinaryString bs = new BinaryString();
bs.getBinaryValue(num);
}
void getBinaryValue(String num) {
String quo = getBin(num);
if (!quo.equals("1")) {
getBinaryValue(quo);
} else {
finArr = quo + finArr;
System.out.println(" Final Binary Value=" + finArr);
return;
}
}
String getBin(String num) {
int[] numArr = new int[num.length()];
for (int i = 0; i < num.length(); i++) {
numArr[i] = Character.getNumericValue(num.charAt(i));
}
int p = 0;
String quo = "";
int rem = numArr[0];
for (int i = 0; i < numArr.length; i++) {
p = rem / 2;
if (p != 0) {
quo = quo + p;
} else if (p == 0 && i > 0) {
quo = quo + p;
}
if ((i + 1) != numArr.length) {
rem = numArr[i] % 2 * 10 + numArr[i + 1];
} else {
rem = rem % 2;
break;
}
}
finArr = Integer.toString(rem) + finArr;
return quo;
}
}
Output:
Final Binary Value=1101011100101101011110111111010001110101100001011011011110010001000101111111100101111101100001010010001101100101101001110011101101111011100110011