1x10^49 in decimal - how binary bits is that and how would you convert it to binary?

Question

I've encountered a website that uses a 50-digit decimal integer ID in a URL query string, which seems a little excessive.

The smallest 50-digit decimal number is 1.0 x 10^49, otherwise known as:

1000000000
0000000000
0000000000
0000000000
0000000000

1. How many bits would the binary representation contain?
2. How would you approach converting such a large decimal number to binary, taking into consideration the range limit of unsigned 32-bit-integer or 64-bit integers?

I ask out of pure programmer curiosity only - this is not a college question, work problem or interview puzzle!

Answer 1

Since every decimal digit conveys the same information as lb 10 bits, any 50 digit number will fit into ceil(lb(10)*50) = 167 bits.

Specifically, it's not that hard to convert from decimal to binary, even by hand. Just divide by two, and put the modulus(1 if the last digit was odd, 0 if even) at the end of your binary result. If you need such high numbers in a program, just use your platform's big integer implementation, e.g. BigInteger in Java and just int in python. In the absence of that, look for a numerical library.

Oh, and 10^49 in binary is 163 bit long:

110
1101 0111 1001 1111 1000 0010 0011 0010
1000 1110 1010 0011 1101 1010 0110 0001
1110 0000 0110 0110 1110 1011 1011 0010
1111 1000 1000 1010 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000

Answer 2

1) 2^10 ~ 10^3 so 10^48 ~ 2^160; 10^49 will be a 164 bit quantity.

2) Use a BigInteger or MPI class (of which there are plenty to be found if your language standard API library doesn't come with one). Knuth has the details.

Answer 3

The minimal binary representation(with integer precision) can be found by taking the log (base 2) of the number. In this case the minimal amount of binary bits would be log(10^49) = 162.77. We need a whole number so we will just call it 163 bits.

If I had to represent that number, and the precision in a floating point representation was insufficient, I would just use some BigInteger library.

Answer 4

1. 49 * log(10) / log(2) = 162.774477, so the binary representation would contain 163 bits.

2. Use a bigint class and apply the standard algorithm for converting from decimal to binary.

Answer 5

One could use a suitable longinteger manipulation library for converting such numbers. If using is not allowed reading the source can give useful knowledge of how such things are done efficiently.

Regarding the number of bits you just need to solve the equation:

2^N = 10⁵⁰

take a log₂ of both parts:

N = log₂10⁵⁰

Now convert log₂ to log₁₀:

N = log₂10⁵⁰ = log₁₀10⁵⁰/log₁₀2 = 50 / log₁₀2

Take the next integer (ceil) of N - that's the number of bits required.

Answer 6

What do you mean exactly by storing number X?

1. Do you mean storing all the numbers between 0 and X?
2. Or all the numbers between -X and X?
3. Or only storing the information: null / X.

My gut feeling is the interviewer might have meant the third one. The answer would be 1 bit.

Answer 7

I'd use a high-level language that handles big integers for me. Sample irb (Ruby) session:

>> (10**49).to_s
=> "10000000000000000000000000000000000000000000000000"
>> (10**49).to_s(2)
=> "1101101011110011111100000100011001010001110101000111101101001100001111000000110011011101011101100101111100010001010000000000000000000000000000000000000000000000000"
>> (10**49).to_s(2).size
=> 163

Answer 8

50 digit decimal integers range from 10^49 to 10^50-1. 10^49 is 163 bits, and 10^50-1 is 167 bits. If you want the EXACT number of bits, you need to take the logarithm of those big numbers directly, as opposed to just computing the "shortcut" 50*log₁₀(2).

As an alternative, you can convert the number to binary using an arbitrary precision decimal-binary converter and count the bits (BTW, the converter I linked to counts the bits for you).