Win a copy of Functional Reactive Programming this week in the Other Languages forum!

Huge Binary String to Decimal Conversion

Perry Campbell
Greenhorn
Posts: 6
So I've been poking around these parts (and google) looking for any way to convert a huge binary string (hundreds of digits) back into decimal. I've been searching for a couple hours with no luck so I figure it's time for a forum post. I've found quite a bit on binary/decimal conversion, but nothing to deal with Huge binary/decimal number conversion without using BigInt. The big catch for my problem is I can't use any BigInt/BigEtc.. types. Thus far I've been able to write a program to convert a huge int to binary which I've stored in a doubly linked list so I can easily do binary multiplication, etc. I'm just plain stuck on how to convert a huge binary number to decimal again. I know I can't store an integer like 2^200 in an int (or a double or a long) and I'm not allowed to use BigInt or anything like it for this assignment. I should probably mention that I'm working with signed integers in 2s compliment. Any help (even a good push!) would be much appreciated. Being stuck is no fun =(.

This is my first post here, but seeing as I'm a CS Student (and passionate about my work!), I hope to become a part of this community to better my knowledge of Java and hopefully help other kind souls on their pursuit of knowledge as well . Thanks in advance for your time, I promise it wont be wasted!

Jeff Verdegan
Bartender
Posts: 6109
6
Since you can't use BigInteger, when you say you want to "convert it to decimal," presumably you mean into a base-10 String representation.

Sounds like you just need to do math like you would with pencil and paper. Since the numerical work there is only with small pieces at a time, you can do that with int, and just build a String incrementally from the sub-steps.

For instance, if you wanted to multiply 2147483647 (Integer.MAX_VALUE) by 2, and assuming you couldn't use anything bigger than int, and you just needed to get the decimal String representation, you would do "2 * 7 = 14 ; put '4' as the last character in the result String ; 2 * 4 = 8, + 1 = 9; put '9' as the next-to-last character in the result String," etc.

Campbell Ritchie
Sheriff
Posts: 50241
79
Welcome to the Ranch

I think you can use a BigInteger. Start with a BigInteger representing 1, and one representing 0. Every time you pass a digit, you double the 1. If the digit was 1, you add it to the other. Remember you need to work right‑to‑left through the String. And what is wrong with this BigInteger constructor?

If you are not allowed to use BigInteger, then you want a List<Integer> or similar. This is a List<Integer> printed out: 3874598349560275609842350682370487561028752309865742398756234985. I think you said you already have such a List.
Remember that adding means you add from right to left; if the total is ≥10 (irrespective of radix), you have a carry digit (usually 1) to add to the next digit. Remember right‑to‑left. Each digit is treated as % 10.
Start with a List like this: 0, and one like this: 1. Every digit, you add the second list to itself, remembering that i × 2 = i + i. Still right‑to‑left. So the second list changes like this: 1→2→4→8→16→etc.
As you iterate your String, if the digit you pass is 1, you add that List to the one which used to be 0, and if the digit is 0, you simply pass on to the next iteration.

Campbell Ritchie
Sheriff
Posts: 50241
79
I presume you are not allowed to write your own LargeInteger class?

Winston Gutkowski
Bartender
Posts: 10527
64
Perry Campbell wrote:Thus far I've been able to write a program to convert a huge int to binary which I've stored in a doubly linked list so I can easily do binary multiplication, etc.

Seems a bit like overkill to me (although I think I understand your reasons). What about an array? (Hint: That's how BigInteger does it).

I'm just plain stuck on how to convert a huge binary number to decimal again. I know I can't store an integer like 2^200 in an int (or a double or a long) and I'm not allowed to use BigInt or anything like it for this assignment. I should probably mention that I'm working with signed integers in 2s compliment. Any help (even a good push!) would be much appreciated.

Well, you can convert a signed int to an unsigned long with int & 0xFFFFFFFFL, and that allows you to do arithmetic on each of your int "digits" (don't forget to carry ). If you use this form, it's better to keep the sign separate from the value (called sign-magnitude storage).

There are many algorithms for division on huge binary numbers (including a few in Knuth's great book), but they are quite involved. The nice thing about division by 10 (or any value that fits in a single int) is that you can simply emulate long division. You can also do it in place.

Winston

Perry Campbell
Greenhorn
Posts: 6
I'm running off to an integral calculus class at the moment but I wanted to get a quick reply in here for clarification. The assignment is to write a BigInt class (http://seattlecentral.edu/faculty/flepeint/java143/hw5.html). I think that the answer may have been touched on here after a quick read through, which is to just do it manually as you would on paper while storing results as a string. So if I had a bit that represents 2^100, manually calculate 2*2*2*2...using strings to hold the large numbers, and then ultimately add up all the results (2^100+2^68+2^12 or something along those lines, again manually with strings) to form the needed decimal. I'll spend a couple hours with this after my math class today and will post my successes/failures here =). I have a couple hours in between my calculus class and my programming lab today and I'll make sure to ask my professor if we're on the right track. I think we very well may be right on, but who knows, maybe there is a more elegant way?

Thank you all so much for your help (and sorry for the rushed post here)! I look forward to solving this problem and sharing my results with y'all.

Kind Regards,
-Perry

Winston Gutkowski
Bartender
Posts: 10527
64
Perry Campbell wrote:The assignment is to write a BigInt class (http://seattlecentral.edu/faculty/flepeint/java143/hw5.html).

Ah. I notice that your assignment doesn't require a divide() method (probably for the reason I said above); in which case an alternative approach is to subtract maximal powers of ten (Hint: a nice constant to know about if you're doing this is log10(2)).

Winston

Perry Campbell
Greenhorn
Posts: 6
I wanted to wait until after this assignment was due to post my solution so none of my classmates copy it. The basic idea turned out to be really simple. I start at the beginning of a huge binary string and move one place at a time. Ignoring the significant bit and starting with a string = "0" I repeat the following procedure for each time through the loop. No matter what I multiply the result string by 2. If the bit is an ON bit I add 1 as well. That's it. Here is my code for converting a 2s compliment binary string to a decimal string (which I'm sure could use some improvement...but it works!):

Thanks again for all the help!
-Perry