Discover

__NOTOC__

In mathematics, the 'binary logarithm' (log₂ ''n'') is the logarithm for base 2. It is the inverse function of 2^''n''.
The binary logarithm is often used in computer science and information theory (where it is frequently written 'lg ''n''', or 'ld ''n''', from Latin ''logarithmus dualis''), because it is closely connected to the binary numeral system. The number of digits (bits) in the binary representation of a positive integer ''n'' is the integral part of 1 + lg ''n'', i.e.
:$lfloor\; lg\; n$
floor + 1.
In information theory, the definition of the amount of self-information and information entropy involves the binary logarithm; this is needed because the unit of information, the bit, refers to information resulting from an occurrence of one of two equally probable alternatives.
The binary logarithm also frequently appears in the analysis of algorithms. If a number ''n'' greater than 1 is divided by 2 repeatedly, the number of iterations needed to get a value at most 1 is again the integral part of lg ''n''. This idea is used in the analysis of several algorithms and data structures. For example, in binary search, the size of the problem to be solved is halved with each iteration, and therefore roughly lg ''n'' iterations are needed to obtain a problem of size 1, which is solved easily in constant time. Similarly, a perfectly balanced binary search tree containing ''n'' elements has height lg ''n''+1.
However, the running time of an algorithm is usually expressed in big O notation, ignoring constant factors. Since log₂ ''n'' = (1/log_k 2)log_k ''n'', where ''k'' can be any number greater than 1, algorithms that run in ''O''(log₂ ''n'') time can also be said to run in, say, ''O''(log₁₃ ''n'') time. The base of the logarithm in expressions such as ''O''(log ''n'') or ''O''(''n'' log ''n'') is therefore not important.
In other contexts, though, the base of the logarithm needs to be specified. For example ''O''(2^{lg ''n''}) is not the same as ''O''(2^{ln ''n''}) because the former is equal to ''O''(''n'') and the latter to ''O''(''n''^0.6931...).
Algorithms with running time ''n'' lg ''n'' are sometimes called linearithmic. Some examples of algorithms with running time ''O''(lg ''n'') or ''O''(''n'' lg ''n'') are:

★ average time quicksort

★ binary search trees

★ merge sort

★ Monge array calculation

Contents

Binary logarithm in integer domain and range

3) ? 1 : 0); }

Numerical value

References

See also

Binary logarithm in integer domain and range

In integer domain and range, binary logarithm can be computed rounding up, or rounding down. These two forms of integer binary logarithm are related by this formula:
:$lfloor\; log2(n)$
floor = lceil log2(n + 1)
ceil - 1, mbox{where }n ge 1. ^[1]
The following code example for the C language is an algorithm to compute the binary logarithm (rounding down) of a 32 bit integer. ^[1] Operator '>>' represents 'unsigned right shift'. The rounding down form of binary logarithm is identical to computing the position of the most significant 1 bit.
/
★
★

★ Returns the floor form of binary logarithm.

★ -1 is returned if n is 0.

★ /
int floorLog2(unsigned int n) {
int pos = -1;
if (n > 65535) { n = n >> 16; pos = pos + 16; }
if (n > 255) { n = n >> 8; pos = pos + 8; }
if (n > 15) { n = n >> 4; pos = pos + 4; }
if (n > 3) { n = n >> 2; pos = pos + 2; }
return pos + n - ((n

3) ? 1 : 0);
}

Using calculators==
An easy way to calculate the log₂(''n'') on calculators that do not have a log₂-function is to use the natural logarithm "ln" or the common logarithm "log" functions, which are found on most "scientific calculators". The formulae for this are:
:log₂(''n'') = ln(''n'')/ln(2) = log(''n'')/log(2)
so
:log₂(''n'') = log_''e''(''n'')×1.442695... = log₁₀(''n'')×3.321928...
and this produces the curiosity that log₂(''n'') is within 0.6% of log_''e''(''n'')+log₁₀(''n'').

Numerical value

The numeric value of the binary logarithm of a positive real number can easily be calculated using this algorithm.^[3]

#!/usr/bin/python

from __future__ import division

def log2(X):

  epsilon = 1.0/(10
★ 
★ 12)

  integer_value=0

  while X < 1:

    integer_value = integer_value - 1

    X = X 
★  2

  while X >= 2:

    integer_value = integer_value + 1

    X = X / 2

  decfrac = 0.0

  partial = 0.5

  X=X
★ X

  while partial > epsilon:

    if X >= 2:

      decfrac = decfrac + partial

      X = X / 2

    partial = partial / 2

    X=X
★ X

  return (integer_value + decfrac)

if __name__ == '__main__':

  value = 4.5

  print "     X  =",value

  print "LOG2(X) =",log2(value)

# Sample output

#

#    $ python log2.py 

#         X  = 4.5

#    LOG2(X) = 2.16992500144

#

References

1.
2.
3. Logarithm Function (Python)

See also

★ natural logarithm (base e),

★ common logarithm (base 10)