The literature mentions several formulae for determining the number of bits required to store the binary expression of a given integer n if n > 0.
Example: the number of binary digits required to store the integer 13 is 4: $$\text{Binary Expression of }13_{10}\text{: 1101}_{2}$$
Concrete Mathematics suggests two ways to get the number of bits required to store a given positive integer with a function B(n) such that:
$$B(n) = \lfloor log_2(n)\rfloor+ 1$$
or
$$B(n) = \lceil log_2(n + 1)\rceil$$
For all integers greater than zero both functions give the correct number of bits; however, the first function using a floor fails to render an integer result when n = 0 and yields undefined, while the second function using a ceiling yields 0.
Graham, Knuth, and Patashnik note for the latter function that it holds for zero "if we're willing to say that it takes zero bits to write n = 0 in binary."
This post is concerned with the case that we ARE NOT willing to say that it takes zero bits to write n = 0 in binary, OR, more correctly, that we MUST require at least one binary digit to store a 0 or 1 in a theoretical information storage system. Thus the domain I'm concerned with is $n\geq0$.
One solution uses a piecewise function:
$$B(n) := \begin{cases}n = 0 & 1\\ n > 0 & \lceil log_2(n + 1)\rceil \\ \end{cases}$$
I implemented this in Excel when iterating over a set of positive integers (with zeroes) to find the minimum bits required to store each while researching a certain bit-packing encoding: =IF(A1=0,1,CEILING(LOG(A1+1,2),1)) or =IF(A1>0,CEILING(LOG(A1+1,2),1),1)
Is there a non-piecewise function that can accomplish the same result?
Examples (n, B(n)):
(0, 1) (1, 1) (2, 2) (3, 2) (4, 3) (5, 3) (6, 3) (7, 3) (8, 4) …
Note:
This question is similar but distinct to the following MathExchange questions: 1416606, 160295, 927468, 3336664
Best Answer
For instance, $B(n) = \lceil \log_2(n+1) \rceil + 1 - \lceil n/(n+1) \rceil$, taking advantage of the fact that $n/(n+1)$ is zero when $n=0$ and between 0 and 1 otherwise.
I think it's unlikely that there is any practical situation where this is a superior alternative.