2
$\begingroup$

Right off the bat, I want to say that I know the How many bits? question has already been asked many times, in many ways.

I have done my best to comb through the answers given in the previous posts, but there seem to be two conflicting answers. For example, in this post, there is a disagreement on the following:

Given an unsigned integer $n$, what is the minimum number of bits $N_b$ required to represent it?

The first (and marked correct) answer is: $N_b=\lfloor{\log_2(n)+1}\rfloor$

However, users in the comments and answers below claim that the above is wrong, and that the actual answer is: $N_b=\lceil\,\log_2(n+1)\rceil$

When I try to figure it out myself, I come up with the second answer:

Need $N_b$ s.t. $n\leq 2^{N_b}-1$, which implies that $N_b\geq\log_2 (n+1)$. And since we cannot have fractional $N_b$, but know that $\log_2 (n+1)$ is the lowest $N_b$ can be, we must round up to the next integer. Therefore we have $N_b=\lceil\,\log_2(n+1)\rceil$.

Does anyone know where the first answer comes from and/or why there is a discrepancy/disagreement between the two?

$\endgroup$
5
  • 2
    $\begingroup$ They give the same answer for all $n>0$. $\endgroup$ Commented Aug 28, 2019 at 5:58
  • $\begingroup$ Whoops, do you have a proof of this? $\endgroup$ Commented Aug 28, 2019 at 6:19
  • $\begingroup$ Actually the number of values you need to represent is n+1, since 0 is included. $\endgroup$ Commented Aug 28, 2019 at 6:23
  • $\begingroup$ @Moti, does it not already account for that fact, since its $2^{N_b}-1$ rather than $2^{N_b}$? $\endgroup$ Commented Aug 28, 2019 at 6:26
  • $\begingroup$ You are right. Is there a case (n) where the results contradict. $\endgroup$ Commented Aug 28, 2019 at 14:25

1 Answer 1

Reset to default
3
$\begingroup$

First, note that $\log_2(n)$ is an integer $p$ iff $n=2^p$, and $\log_2(n)$ is strictly increasing with $n$.

  • First expression

For $n\in [2^p,2^{p+1}-1]$, $\log_2(n)\in[p,p+1[$., which means $\lfloor\log_2(n)+1\rfloor=p+1$, which is the number of bits of these values of $n$. This is true for all $p\ge0$, hence for all $n>0$.

  • Second expression

For $n\in [2^p,2^{p+1}-1]$, we have $n+1\in [2^p+1,2^{p+1}]$, hence $\lceil\log_2(n+1)\rceil=p+1$, which is also the expected result.

Both expression are correct for $n>0$. For $n=0$, the first is undefined, and the other yields $0$. It's not entirely clear how the number of bits should be defined for $n=0$, but I'd say you still need one bit.

$\endgroup$
3
  • $\begingroup$ Done and done- interesting that it seems the two equations arise simply from a difference in derivation approach, that is adding one first, then taking $\log_2$, vs. taking the $\log_2$, then adding one. $\endgroup$ Commented Aug 28, 2019 at 6:38
  • $\begingroup$ Also, what does the notation $...p+1[...$ mean? $\endgroup$ Commented Aug 28, 2019 at 8:01
  • 1
    $\begingroup$ @BenGranger The interval is half-open on the right. That is, $p\le \log_2(n)\lt p+1$. The notation is usual in France, but maybe you are more accustomed to $[p,p+1)$. $\endgroup$ Commented Aug 28, 2019 at 8:03

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.