0
$\begingroup$

I was told by my professor that

"It takes c * ln(n) bits to store a number n, where ln() is base 2 and c is a constant."

Thus, to store a number 8, we need ln(8) = 3 bits(I think const c can be ignored here.), but isn't 8 stored as "1000" in a computer, which is 4 bits?

Thanks.

$\endgroup$
  • 1
    $\begingroup$ $ln$ is typically used for logarithm base $e$, i.e $log_e$. For base 2, use $log_2$. $\endgroup$ – garbagecollector Sep 4 at 20:39
  • 1
    $\begingroup$ @garbagecollector occasionally I see $\lg$ for base 2 (not saying I like it) $\endgroup$ – D. Ben Knoble Sep 5 at 4:05
0
$\begingroup$

The exact number of bits for a number $n \gt 0$ is: $$\lfloor log_2(n) \rfloor + 1$$ If to use natural logarithms, then this number will be: $$\lfloor log_2(n) \rfloor + 1 = \lfloor log_2(e) \cdot ln(n) \rfloor + 1 = \mathcal{O}(log(n))$$ We usually ignore the logarithm base in this kind of $\mathcal{O}$ notation, because logarithms with all constant bases are asymptotically equivalent.

$\endgroup$
1
$\begingroup$

$b$ bits have a total of $2^b$ distinct bit-patterns. To store 8 distinct values, you need at least 3 bits.

This does not tell you on its own how many bits are required to store the number 8, because it depends on the way that you assign numbers to bit patterns.

A typical "unsigned integer" uses $b$ bits to represent the numbers 0, 1, ... 2^b-1. In that format, you would need 4 bits to represent 8, because $2^3-1<8<2^4-1$.

A typical "two's complement integer" uses $b$ bits to represent the numbers $-2^{b-1}$ to $2^{b-1}-1$. In this format, you would need 5 bits to represent 8, since $2^{4-1}-1<8<2^{5-1}-1$.

If you're only interested in representing powers of two (perhaps because you doing something hardware or memory related, where divisions such as alignment are only ever powers of two), you use fewer bits; for example, if 00 is 1, 01 is 2, 10 is 4, and 11 is 8, you only need 2 bits to represent 8.

$\endgroup$
0
$\begingroup$

Simple answer is $4$-bits. Why $4$? Because $0$ is included. You need to count zero as one unit. So we have $9$ units in total. The number $8$ is the $9$th number in the sequence: $\{0,1,2,3,4,5,6,7,8\}$. Hope this made it clearer.

We can make a table of all the binary numbers that the computer use:

1: 0 0000
2: 1 0001
3: 2 0010
4: 3 0011
5: 4 0100
6: 5 0101
7: 6 0110
8: 7 0111
9: 8 1000 *

The first colum represents the unit (or quantifier), the second column represent the decimal number, the final colum represent the binary number containing four bits.

The $\log_2$ of $x$ is the power to which the number $2$ must be raised. Hence $\log_2(x) = y$ such that $2^y = x$.

$\log_2(8) = 3$.

$2^3 = 8$.

But, since the number $8$ is in the actual $9$th position, we have to add $+1$ when we compute the logarithm:

$\log_2(8+1) = \log_2(9) = 3.1699250014423126$

The computer cannot represent its value using $3.$something-bits, so we have to take the ceiling to be able to compress all numbers (including zero):

$\lceil\log_2(9)\rceil=\lceil3.1699250014423126\rceil=4$.

This should be enough. We can see however that $2^4=16$. So we can conclude that with four bits we can compress/pack $16$-numbers in total:

$\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15\}$. That is from $0$ to $15$. And number $8$ is in the $9$th position again.

Zero can be mistaken for not being treated as a quantity, so caution must be taken when computing with the base $2$ logarithm. Just add $1$ to fix it. Computer-registers are often restricted to $8$, $16$ or $32$ bits (which are power of twos). That is their numbers range from $0$ to $2^x-1$. As you can see their maximum value is $2^x-1$. The $-1$ shows some kind of symmetry to the notion that we have to add $+1$ to that log.

Edit: Also what Curtis F just stated, it depends on how you represent the numbers. You could indeed represent the number $8$ with just one bit, i.e. the mapping $\{0,1\}\rightarrow\{0,8\}$. But I don't think you want that.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.