Это вопрос домашней работы, с которым я застрял.
Рассмотрим целочисленное представление без знака. Сколько бит будет требуется для хранения десятичного числа, содержащего:
i) 3 digits ii) 4 digits iii) 6 digits iv) n digits
Я знаю, что диапазон целого числа без знака будет от 0 до 2 ^ n, но я не понимаю, как количество бит, необходимое для представления числа, зависит от него. Пожалуйста, помогите мне.
Спасибо заранее.
Ну, вам просто нужно рассчитать диапазон для каждого случая и найти самую низкую мощность 2, которая выше этого диапазона.
Например, в i), 3 десятичных разряда → 10 ^ 3 = 1000 возможных чисел, поэтому вам нужно найти наименьшую мощность 2, превышающую 1000, которая в этом случае равна 2 ^ 10 = 1024 (10 биты).
Изменить: В основном вам нужно найти количество возможных номеров с количеством цифр, которое у вас есть, а затем найти, какое количество цифр (в другой базе, в данном случае база 2, двоичная) имеет по крайней мере одинаковые возможные числа, такие как число в десятичной форме.
Чтобы вычислить количество возможностей с учетом количества цифр: possibilities=base^ndigits
Итак, если у вас есть 3 цифры в десятичной системе (база 10), у вас есть возможности 10^3=1000. Затем вам нужно найти несколько цифр в двоичном формате (бит, база 2), чтобы количество возможностей составляло не менее 1000, что в данном случае равно 2^10=1024 (9 цифр недостаточно, потому что 2^9=512, что меньше чем 1000).
Если вы обобщите это, у вас есть: 2^nbits=possibilities <=> nbits=log2(possibilities)
Что применяется к i) дает: log2(1000)=9.97, и поскольку число бит должно быть целым числом, вы должны округлить его до 10.
Формула для количества двоичных битов, необходимых для хранения n целых чисел (например, от 0 до n - 1):
и округлить.
Например, для значений от -128 до 127 (байт со знаком) или от 0 до 255 (байт без знака) число целых чисел равно 256, поэтому n равно 256, что дает 8 из приведенной выше формулы.
От 0 до n используйте n + 1 в приведенной выше формуле (есть n + 1 целое число).
На вашем калькуляторе log e может быть просто помечен как log или ln (натуральный логарифм).
Хорошо, чтобы обобщить технику того, сколько бит вам нужно представлять число, сделано таким образом. У вас есть R-символы для представления, и вы хотите знать, сколько бит, решить это уравнение R = 2 ^ n или log2 (R) = n. Где n - количество бит, а R - количество символов для представления.
Для десятичной системы чисел R = 9 мы решаем 9 = 2 ^ n, ответ составляет 3,17 бит на десятичную цифру. Таким образом, 3-значное число будет нуждаться в 9,51 бит или 10. Для 1000-разрядного номера требуется 3170 бит
Наибольшее число, которое может быть представлено n- значным числом в базе b, равно b n - 1. Следовательно, наибольшее число, которое может быть представлено в N двоичных цифрах, равно 2 N - 1. Нам нужно наименьшее целое число N, такое что:
2 N - 1 ≥ b n - 1
⇒ 2 N ≥ b n
Взяв логарифм по основанию 2 обеих сторон последнего выражения, получим:
log 2 2 N ≥ log 2 b n
⇒ N ≥ log 2 b n
⇒ N ≥ log b n/log 2
Поскольку мы хотим, чтобы наименьшее целое число N, удовлетворяющее последнему соотношению, нашло N, найдите log b n/log 2 и возьмем потолок.
В последнем выражении любая основа подходит для логарифмов, если обе базы одинаковы. Здесь удобно, поскольку нас интересует случай, когда b = 10, использовать логарифмы с основанием 10, используя преимущество log 10 10 n == n.
Для n = 3:
N = ⌈3/log 10 2⌉ = 10
Для n = 4:
N = ⌈4/log 10 2⌉ = 14
Для n = 6:
N = ⌈6/log 10 2⌉ = 20
И вообще, для n десятичных цифр:
N = ⌈n/log 10 2⌉
Продолжайте делить число на 2, пока не получите коэффициент 0.
Самый простой ответ - преобразовать требуемые значения в двоичный код и посмотреть, сколько бит требуется для этого значения. Тем не менее, вопрос задает, сколько бит для десятичного числа X цифр. В этом случае кажется, что вам нужно выбрать наивысшее значение с помощью X цифр, а затем преобразовать это число в двоичный.
В качестве базового примера предположим, что мы хотели сохранить десятизначное базовое десять чисел и хотели узнать, сколько бит потребуется. Самый большой десятизначный базовый номер десяти - 9, поэтому нам нужно преобразовать его в двоичный. Это дает 1001, который имеет в общей сложности 4 бита. Этот же пример может быть применен к двузначному номеру (с максимальным значением 99, которое преобразуется в 1100011). Чтобы решить за n цифр, вам, вероятно, придется решать остальные и искать шаблон.
Чтобы преобразовать значения в двоичные, вы повторно делитесь на два, пока не получите коэффициент 0 (и все ваши остатки будут равны 0 или 1). Затем вы меняете порядок остатков, чтобы получить номер в двоичном формате.
Экзамен: от 13 до двоичного.
Надеюсь, что это поможет.
пусть его требуемый n бит, затем 2 ^ n = (base) ^ digit, а затем возьмите журнал и подсчитайте no. для n
Для двоичного числа из n цифр максимальное десятичное значение, которое оно может удерживать, будет
2 ^ n - 1, а 2 ^ n - полные перестановки, которые могут быть сгенерированы с использованием этих многих цифр.
Принимая случай, когда вам нужны только три цифры, т.е. ваш случай 1. Мы видим, что требования:
2 ^ n - 1 >= 999
Применение журнала к обеим сторонам,
log (2 ^ n - 1) >= log (999)
log (2 ^ n) - log (1) >= log (999)
n = 9,964 (приблизительный).
Принимая значение ceil n, поскольку 9.964 не может быть допустимым числом цифр, получаем n = 10.
Предполагая, что вопрос задает вопрос о том, какие минимальные биты необходимы для хранения
Мой подход к этому вопросу:
Эта проблема может быть решена таким образом путем рекурсивного разделения 999 на 2. Тем не менее, проще использовать силу математики, чтобы помочь нам. По существу, мы решаем n для уравнения ниже:
2^n = 999
nlog2 = log999
n ~ 10
Вам понадобится 10 бит для хранения 3-значного числа.
Используйте аналогичный подход для решения других подпоследований!
Надеюсь, это поможет!
Здесь много ответов, но я добавлю свой подход, так как я нашел этот пост при работе над той же проблемой.
Начиная с того, что мы знаем здесь, это число от 0 до 16.
Number encoded in bits minimum number of bits to encode
0 000000 1
1 000001 1
2 000010 2
3 000011 2
4 000100 3
5 000101 3
6 000110 3
7 000111 3
8 001000 4
9 001001 4
10 001010 4
11 001011 4
12 001100 4
13 001101 4
14 001110 4
15 001111 4
16 010000 5
глядя на перерывы, он показывает эту таблицу
number <= number of bits
1 0
3 2
7 3
15 4
Итак, теперь, как мы вычисляем шаблон?
Помните, что база данных 2 (n) = база базы 10 (n)/база базы 10 (2)
number logb10 (n) logb2 (n) ceil[logb2(n)]
1 0 0 0 (special case)
3 0.477 1.58 2
7 0.845 2.807 3
8 0.903 3 3 (special case)
15 1.176 3.91 4
16 1.204 4 4 (special case)
31 1.491 4.95 5
63 1.799 5.98 6
Теперь желаемый результат соответствует первой таблице. Обратите внимание, как и некоторые значения являются особыми случаями. 0 и любое число, которое является степенью 2. Эти значения не изменяются при применении потолка, поэтому вы знаете, что вам нужно добавить 1, чтобы получить минимальная длина поля бита.
Для учета особых случаев добавьте один на вход. Результирующий код, реализованный в python, следующий:
from math import log
from math import ceil
def min_num_bits_to_encode_number(a_number):
a_number=a_number+1 # adjust by 1 for special cases
# log of zero is undefined
if 0==a_number:
return 0
num_bits = int(ceil(log(a_number,2))) # logbase2 is available
return (num_bits)
Этот работает!
floor(loge(n) / loge(2)) + 1
Чтобы включить отрицательные числа, вы можете добавить дополнительный бит, чтобы указать знак.
floor(loge(abs(n)) / loge(2)) + 2