1x10 ^ 49 в десятичном виде - как это двоичные биты и как бы вы преобразовали его в двоичный?

Question

Я сталкивался с веб-сайтом, который использует 50-значный десятичный целочисленный идентификатор в строке запроса URL, что кажется немного чрезмерным.

Наименьшее десятичное число из 50 цифр - 1.0 x 10^49, также известное как:

1000000000
0000000000
0000000000
0000000000
0000000000

1. Сколько бит содержит двоичное представление?
2. Как бы вы подошли к преобразованию такого большого десятичного числа в двоичное, принимая во внимание предел диапазона беззнаковых 32-разрядных целых или 64-разрядных целых чисел?

Я спрашиваю только из чистого любопытства программиста - это не вопрос колледжа, не проблема работы и не собеседование!

Answer 1

Минимальное двоичное представление (с целочисленной точностью) можно найти, взяв лог (основание 2) числа. В этом случае минимальное количество двоичных битов будет log (10 ^ 49) = 162,77. Нам нужно целое число, поэтому мы просто назовем его 163 битами.

Если бы мне пришлось представлять это число, а точность в представлении с плавающей точкой была недостаточной, я бы просто использовал библиотеку BigInteger .

Answer 2

1. 49 * log (10) / log (2) = 162,774477, поэтому двоичное представление будет содержать 163 бита.

2. Используйте класс bigint и примените стандартный алгоритм для преобразования из десятичного в двоичное.

Answer 3

Поскольку каждая десятичная цифра передает ту же информацию, что и lb 10 бит, любое 50-значное число будет помещаться в ceil(lb(10)*50) = 167 бит.

В частности, это не так сложно преобразовать из десятичной в двоичную, даже вручную. Просто разделите на два и поместите модуль (1, если последняя цифра была нечетной, 0, если четная) в конце вашего двоичного результата. Если вам нужны такие большие числа в программе, просто используйте большую целочисленную реализацию вашей платформы, например, BigInteger в Java и просто int в Python. В отсутствие этого ищите числовую библиотеку.

Да, и 10 ^ 49 в двоичном формате имеет длину 163 бита:

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 4

Можно использовать подходящую библиотеку манипуляций с longinteger для преобразования таких чисел. Если использование запрещено, чтение источника может дать полезные знания о том, как такие вещи выполняются эффективно.

Относительно количества бит, которое вам просто нужно для решения уравнения:

2 ^N = 10 ⁵⁰

взять журнал ₂ обеих частей:

N = log ₂ 10 ⁵⁰

Теперь преобразуйте журнал ₂ в журнал ₁₀ :

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

Возьмите следующее целое число (ceil) из N - это количество необходимых битов.

Answer 5

50-значные десятичные числа в диапазоне от 10 ^ 49 до 10 ^ 50-1. 10 ^ 49 - это 163 бита, а 10 ^ 50-1 - это 167 бит. Если вам нужно ТОЧНОЕ число битов, вам нужно взять логарифм этих больших чисел напрямую, а не просто вычислить «ярлык» 50 * log ₁₀ (2).

В качестве альтернативы вы можете преобразовать число в двоичное с использованием десятичного двоичного преобразователя произвольной точности и считать биты (кстати, преобразователь, с которым я связался, подсчитывает биты для вас).

Answer 6

Я бы использовал язык высокого уровня, который обрабатывает большие целые числа для меня. Пример сеанса irb (Ruby):

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

Answer 7

Что именно вы подразумеваете под сохранением числа X?

1. Вы имеете в виду сохранение всех чисел от 0 до X?
2. Или все числа от -X до X?
3. Или только хранение информации: null / X.

Мое интуитивное чувство, что интервьюер мог иметь в виду третьего. Ответ будет 1 бит.

Answer 8

1) 2 ^ 10 ~ 10 ^ 3, т. Е. 10 ^ 48 ~ 2 ^ 160; 10 ^ 49 будет 164-битной величиной.

2) Используйте класс BigInteger или MPI (которых можно найти, если ваша стандартная библиотека языка API не поставляется с ней). У Кнута есть детали.