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.
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.
$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 that 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.
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.
Your professor is unclear here. If you know the number is eight, you don’t need to store it - zero bits. The question should be “how many bits do I need to store one of k different values”. For example , to be able to store a value from 0 to 8, 3 bits are not enough, you need four bits.
But if you store large amounts of numbers of different sizes, and you only need sequential access to them, you’d use something like Huffman coding or Arithmetic coding. In the first case the number of bits for the number eight depends on what percentage of your gazillions of numbers are eight, if one in 100 numbers on average are equal to eight, then most likely 7 bits would be used. With Arithmetic coding, it’s not even a fixed number of bits.
