BOTTOM LINE - DOUBLE PRECISION FLOATING POINT
We can make use of the floating point encoding directly to efficiently determine $\log_2$ for the represented number (and as I show at the end provide the result in dB as well). The following algorithm will provide the result within an accuracy of 0.3 dB from the encoding of a double precision floating point value given as $x$:
- Extract the 11 bit exponent as unsigned integer $E$ and subtract 1023.
- Extract the 52 bit mantissa as unsigned integer $M$.
- Divide $M$ by $2^{52}$ (Shift M 52 bits to the right) to be all fractional in range of [0, 1)
- $\log_2(x) = E - 1023 + M/2^{52} + 2^{-5}$.
DETAILS
IEEE-754 double precision floating point representation is encoded into 64 bits as a sign bit, exponent, and mantissa as depicted in the graphic below:
The resulting floating point number is given as:
$$x = (-1)^S \cdot (1 + 2^{-52}M) \cdot 2^{(E-1023)} \label{1}\tag{1}$$
Where $M$ and $E$ represent the unsigned integer representations for the binary values stored in the mantissa and exponent respectively.
$$ S \in \{0,1\} \\
1 \le E < 2^{11}-1 \\
0 \le M < 2^{52} $$
The exponent is stored with a bias to represent positive and negative exponents rather than using 2's complement as then different numbers can be compared directly using fixed point arithmetic (simple!). The range for the exponent does not include the two values corresponding to a binary number with all zeros or all ones as those two values are used to encode special conditions (infinity, zero, NaN).
From $M$ and $E$ taken directly from the stored floating point representation, we can estimate $\log_2(x)$ for all positive values $x$ with a max error of 0.05 using
$$\log_2(x) \approx E - 1023 + 2^{-52}M + 2^{-5} \label{2}\tag{2}$$
Note that all operations are simple bit shifts, so computationally cheap. This can be improved to higher accuracy with additional curve fitting of the equation $\log_2(1+2^{-52}M)$ which results in an exact solution.
DERIVATION
The following $\log_2$ relationship is from \ref{1}:
$$\frac{x}{1+2^{-52}M} = 2^{(E-1023)} $$
$$\log_2\bigg(\frac{x}{1+2^{-52}M}\bigg) = E-1023 \label{3}\tag{3}$$
We note that denominator term $1+2^{-52}M$ has a range from 1 to 2.
Rewriting \ref{3}:
$$\log_2(x) - \log_2(1+2^{-52}M) = E - 1023 \label{4}\tag{4}$$
And we get the exact relationship for $\log_2(x)$ from the given floating point encoding:
$$\log_2(x) = E - 1023 + \log_2(1+2^{-52}M) \label{5}\tag{5}$$
We can use several approximation methods to replace the $\log_2(1+M/2^{52})$ term depending on accuracy needed, including computations from the Taylor Series expansion or table look-up methods. Observe in the graph below the match by simply subtracting one and adding the closest bit shift offset of 2^{-5} as:
$$\log_2(1+2^{-52}M) \approx 2^{-52}M -1 + 2^{-5}$$
Given this, we can make a first approximation of $\log_2(x)$ from the exponent directly. This has a peak error of 1 (or add 1/2 to this to reduce the peak error to 0.5 as the error is always negative):
$$\log_2(x) \approx E-1023 \label{6}\tag{6}$$
We can improve this by including the mantissa curve fit as:
$$\log_2(x) \approx E + 2^{-52}M -1023 + 2^{-5} \label{7}\tag{7}$$
Testing this on actual floating point representations I was able to create the following graphic, where the error pattern is consistent with the curve fit used for the $\log_2(1+2^{-52}M) $:
Thinking in dB
An interesting perspective since many of us often work in the world of dB units is that we can express a magnitude quantity in dB as either:
$$dB(x) = 20\log_{10}(x)$$
or
$$dB(x) = 6\log_2(x)$$
since $\log_{10}x = \log_2(x)/\log_{2}(10)$.
We see how this results in a simple dB computation as well, and with that we see that using Equation \ref{6} directly could have an error of up to 6 dB (or +/-3 dB if we added the 1/2). This would be unacceptable in most applications, but with Equation \ref{7} the error in dB is reduced to 0.3 dB which would then have wider appeal. A simple one or two more orders of curve fit for the mantissa term would improve this accuracy substantially.
BOTTOM LINE - FIXED POINT
We can play similar tricks for a signed fixed point number $x$ by converting the number represented in an arbitrary Q(m,n) format to Q(2, m+n-2) format. (For further details on Q(m,n) formats, please see https://en.wikipedia.org/wiki/Q_(number_format)) by moving the radix to the left $E$ places ($E$ can be negative). This means determining the minimum $E$ such that dividing $x$ by $2^E$ results in a fractional number between 1 and nearly 2. (which means shift right maintaining fractional values until there is only one integer magnitude bit left, keeping track of the number of shifts needed to derive the value $E$).
The resulting number will then be have a value $1 + F$ having a range between 0 and nearly 1, with $F$ as the fractional part. This results in the following approximation:
$$\log_2(x) \approx E + F + 2^{-5}$$
For example, in 16 bit Q16.0 signed representation, the number 532 would be given in binary as:
$$0000\_0010\_0001\_0100$$
To be in Q(2, 14) format, we would move the radix (which is at the far right to start) 9 places to the left, so $E=9$, and the fractional result in Q2.14 format is $532/2^9 = 1.0390625 = 1 + F$
Therefore, $\log_2(532) \approx 9 + 0.0390625 + 2^{-5} = 9.0703125$
The actual result is $\log_2(532) = 9.05528...$
If we multiply the estimate 9.07 by 6 we get the result in dB as 54.42 dB. The actual dB computation is $20\log_{10}(532)= 54.52$ dB.
