Calculating the bits needed to store a decimal number

Question

This is a homework question I'm stuck with.

Consider an unsigned integer representation. How many bits will be required to store a decimal number containing:

i) 3 digits ii) 4 digits iii) 6 digits iv) n digits 

I know that the range of an unsigned integer will be from 0 to 2 ^ n, but I don't understand how the number of bits needed to represent a number depends on it. Please help me.

Thanks in advance.

Answer 1

Well, you just need to calculate the range for each case and find the lowest power 2 that is above that range.

For example, in i), 3 decimal places → 10 ^ 3 = 1000 possible numbers, so you need to find the lowest power 2 exceeding 1000, which in this case is 2 ^ 10 = 1024 (10 bits).

Edit: Basically, you need to find the number of possible numbers with the number of digits that you have, and then find how many numbers (in another base, in this case, base 2, binary) have at least the same possible numbers, such as a number in decimal form.

To calculate the number of possibilities given the number of digits: possibilities=base^ndigits

So, if you have 3 digits in the decimal system (base 10), you have the possibility of 10^3=1000 . Then you need to find a few digits in binary format (bit, base 2) so that the number of possibilities is at least 1000, which in this case is 2^10=1024 (9 digits are not enough, because 2^9=512 , which is less than 1000).

If you generalize this, you have: 2^nbits=possibilities <=> nbits=log2(possibilities)

Which applies to i) gives: log2(1000)=9.97 , and since the number of bits must be an integer, you must round it to 10.

Answer 2

The formula for the number of binary bits needed to store n integers (for example, from 0 to n - 1 ):

log _e (n) / log _e (2)

and round.

For example, for values ​​from -128 to 127 (signed bytes) or 0 to 255 (unsigned bytes), the number of integers is 256, so n is 256, which gives 8 from the above formula.

From 0 to n, use n + 1 in the above formula (there is n + 1 integer).

On your calculator, log _e can simply be marked as log or ln (natural logarithm).

Answer 3

Well, to generalize the technique of how many bits you need to represent a number, this is done. You have R characters to represent, and you want to know how many bits to solve, this equation is R = 2 ^ n or log2 (R) = n. Where n is the number of bits and R is the number of characters to represent.

For the decimal system of numbers R = 9, we solve 9 = 2 ^ n, the answer is 3.17 bits per decimal digit. Thus, a 3-digit number will need 9.51 bits or 10. For a 1000-bit number, 3170 bits are required

Answer 4

The largest number that can be represented by an n- digit number in base b is b ⁿ - 1 . Therefore, the largest number that can be represented in N binary digits is 2 ^N - 1 . We need the smallest integer N such that:

2 ^N - 1 ≥ b ⁿ - 1
⇒ 2 ^N ≥ b ⁿ

Taking the logarithm of the base 2 of both sides of the last expression, we get:

log ₂ 2 ^N ≥ log ₂ b ⁿ
⇒ N ≥ log ₂ b ⁿ
⇒ N ≥ log b ⁿ / log 2

Since we want the smallest integer N satisfying the last relation to find N , find log b ⁿ / log 2 and take the ceiling.

In the last expression, any base is suitable for logarithms if both bases are the same. It is convenient here, since we are interested in the case when b = 10 , to use logarithms with base 10, taking advantage of log ₁₀ 10 ⁿ == n .

For n = 3 :

N = ⌈3 / log ₁₀ 2⌉ = 10

For n = 4 :

N = ⌈4 / log ₁₀ 2⌉ = 14

For n = 6 :

N = ⌈6 / log ₁₀ 2⌉ = 20

And in general, for n decimal digits:

N = ⌈n / log ₁₀ 2⌉

Answer 5

Keep dividing the number by 2 until you get a factor of 0.

Answer 6

The simplest answer is to convert the required values ​​to binary and see how many bits are required for this value. However, the question asks how many bits are for the decimal number X digits. In this case, it seems that you need to select the highest value using X digits, and then convert that number to binary.

As a basic example, suppose we wanted to store a ten-digit base ten numbers and wanted to know how many bits would be needed. The largest ten-digit base number of ten is 9, so we need to convert it to binary. This gives 1001, which has a total of 4 bits. The same example can be applied to a two-digit number (with a maximum value of 99, which translates to 1100011). To solve for n digits, you probably have to solve the rest and look for a pattern.

To convert the values ​​to binary, you re-divide by two until you get a coefficient of 0 (and all your residuals will be 0 or 1). Then you change the order of the residues to get the number in binary format.

Exam: 13 to binary.

• 13/2 = 6 r 1
• 6/2 = 3 r 0
• 3/2 = 1 r 1
• 1/2 = 0 r 1
• = 1101 ((8 * 1) + (4 * 1) + (2 * 0) + (1 * 1))

Hope this helps.

Answer 7

let its required n bit, then 2 ^ n = (base) ^ digit, and then take the log and count no. for n

Answer 8

For a binary number of n digits, the maximum decimal value that it can hold will be

2 ^ n - 1, and 2 ^ n are complete permutations that can be generated using these many digits.

Assuming the case where you only need three digits, i.e. your case 1. We see the requirements:

2 ^ n - 1> = 999

Applying the magazine to both sides,

log (2 ^ n - 1)> = log (999)

log (2 ^ n) - log (1)> = log (999)

n = 9.964 (approximate).

Taking the value of ceil n, since 9.964 cannot be a valid number of digits, we get n = 10.

Answer 9

Assuming the question asks which minimum bits are needed to store

• 3 digits

My approach to this question:

• What is the maximum number of 3 digits we need to store? Ans: 999
• What is the minimum number of bits required to store this number?

This problem can be solved in this way by recursively dividing 999 by 2. However, it is easier to use the power of mathematics to help us. Essentially, we solve n for the equation below:

 2^n = 999 nlog2 = log999 n ~ 10 

You will need 10 bits to store a 3-digit number.

Use a similar approach to solve other subsequences!

Hope this helps!

Answer 10

There are many answers here, but I will add my approach, since I found this post while working on the same issue.

Starting from what we know here, this number is from 0 to 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 

looking at the breaks, he shows this table

 number <= number of bits 1 0 3 2 7 3 15 4 

So now, how do we calculate the template?

Remember that database 2 (n) = database base 10 (n) / database base 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 

Now the desired result corresponds to the first table. Note how some values ​​are special cases. 0 and any number that is a power of 2. These values ​​do not change when applying the ceiling, so you know that you need to add 1 to get the minimum bit field length.

To account for special cases, add one to the input. The resulting code implemented in python is as follows:

 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) 

Answer 11

This one works!

 floor(loge(n) / loge(2)) + 1 

To include negative numbers, you can add an extra bit to indicate the sign.

 floor(loge(abs(n)) / loge(2)) + 2