Calculating bits required to store decimal number

Question

Consider 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 the unsigned integer will be 0 to 2^n but I don't get how the number of bits required to represent a number depends upon it.

Answer 1

Well, you just have to calculate the range for each case and find the lowest power of 2 that is higher than that range.

For instance, in i), 3 decimal digits -> 10^3 = 1000 possible numbers so you have to find the lowest power of 2 that is higher than 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 you have and then find which number of digits (in the other base, in this case base 2, binary) has at least the same possible numbers as the one in decimal.

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

So, if you have 3 digits in decimal (base 10) you have 10^3=1000 possibilities. Then you have to find a number of digits in binary (bits, base 2) so that the number of possibilities is at least 1000, which in this case is 2^10=1024 (9 digits isn't enough because 2^9=512 which is less than 1000).

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

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

Answer 2

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

log_e(n) / log_e(2)

and round up.

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

For 0 to n, use n + 1 in the above formula (there are n + 1 integers).

On your calculator, log_e may just be labelled log or ln (natural logarithm).

Answer 3

The largest number that can be represented by an n digit number in base b is bⁿ - 1. Hence, 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 base 2 logarithm of both sides of the last expression gives:

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

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

In the last expression, any base is fine for the logarithms, so long as both bases are the same. It is convenient here, since we are interested in the case where b = 10, to use base 10 logarithms 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 4

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

For the decimal number system R=9 so 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. A 1000 digit number needs 3170 bits

Answer 5

Assuming that the question is asking what's the minimum bits required for you to store

1. 3 digits number

My approach to this question would be:

• what's the maximum number of 3 digits number we need to store? Ans: 999
• what's the minimum amount of bits required for me to store this number?

This problem can be solved this way by dividing 999 by 2 recursively. However, it's simpler to use the power of maths to help us. Essentially, we're solving n for the equation below:

2^n = 999
nlog2 = log999
n ~ 10

You'll need 10 bits to store 3 digit number.

Use similar approach to solve the other subquestions!

Hope this helps!

Answer 6

The short answer is:

int nBits = ceil(log2(N));

That's simply because pow(2, nBits) is slightly bigger than N.

Answer 7

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

Answer 8

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

2^n - 1, and 2^n is the total permutations that can be generated using these many digits.

Taking a case where you only want three digits, ie your case 1. We see that the requirements is,

2^n - 1 >= 999

Applying log to both sides,

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

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

n = 9.964 (approx).

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

Answer 9

There are a lot of answers here, but I'll add my approach since I found this post while working on the same problem.

Starting with what we know here are the number 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, it shows this table

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

So, now how do we compute the pattern?

Remember that log base 2 (n) = log base 10 (n) / log 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 matching the first table. Notice how also some values are special cases. 0 and any number which is a powers of 2. These values dont change when you apply ceiling so you know you need to add 1 to get the minimum bit field length.

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

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 10

This one works!

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

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

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

Answer 11

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

Answer 12

The simplest answer would be to convert the required values to binary, and see how many bits are required for that value. However, the question asks how many bits for a decimal number of X digits. In this case, it seems like you have to choose the highest value with X digits, and then convert that number to binary.

As a basic example, Let's assume we wanted to store a 1 digit base ten number, and wanted to know how many bits that would require. The largest 1 digit base ten number is 9, so we need to convert it to binary. This yields 1001, which has a total of 4 bits. This same example can be applied to a two digit number (with the max value being 99, which converts to 1100011). To solve for n digits, you probably need to solve the others and search for a pattern.

To convert values to binary, you repeatedly divide by two until you get a quotient of 0 (and all of your remainders will be 0 or 1). You then reverse the orders of your remainders to get the number in binary.

Exampe: 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 out.

Answer 13

As said above, the short (perfect and brillant) answer from ad absurdum is:

N = ⌈n / log₁₀ 2⌉

A faster answer could be:

N < ( n × 3402 ) » 10 + 1

" » " stands for a bitwise shift to the right, which is a division by a power of 2, rounded down.

This formula only needs integer operations and produces a good result up to a quite high number of digits (more than 1000, and error is 0 or +1). It may be used to allocate a buffer in a parser because the error is always positive.

Explanation :
First turn the division into a multiplication :

N = n / log₁₀ 2 = n × ( 1/log₁₀ 2 )

Let's multiply by a power of 2 and select an integer upper bound :

n × ( 1/log₁₀ 2 ) × 2¹⁰ = n × 3 401,654… < n × 3402

Then divide by 2¹⁰ :

n / log₁₀ 2 < ( n × 3402 ) / 2¹⁰
N < ( n × 3402 ) / 2¹⁰

Finally replace the division by a shift and add 1 to round up.

n/log₁₀ 2 < ( n × 3402 ) » 10 + 1

You can easily get a better accuracy with a higher power of 2. With 2¹⁶ or 2³² you just have to discard the lower bytes. But you need larger integer words. 2⁸ might be a good approximation for embeded computing.