二進対数 (にしんたいすう、英: binary logarithm)とは、2を底とする対数 log2 x のことである。これは、指数関数 x → 2x の逆関数でもある。
コンピューターへの応用
情報理論

二進対数は二進法と密接に関係しているため、計算機科学や情報理論でしばしば使われる。この文脈において、二進対数は「lg x」と表記されることがよくある[1]。同じ関数の別の表記としてときどき（特にドイツ語で）使われるものとして「ld x」があり、これはラテン語の Logarithmus Du?lis から来ている[2]。ただし、ISO 80000-2では「lg x」は log10 x すなわち常用対数を示すとされており、二進対数の略記法は「lb x」である。本稿でもこれに従う。

正整数 n の二進法における桁数（すなわちビット数）は 1 + lb n の整数部分であり、以下の床関数で表される。 ⌊ lb n ⌋ + 1   {\displaystyle \lfloor \operatorname {lb} \,n\rfloor +1\ }
計算の複雑性

二進対数は、アルゴリズム解析で頻出する。1より大きな数 n を2で繰り返し割っていき、その値を1以下にするために必要な繰り返し回数は、 ⌊ lb n ⌋ {\displaystyle \lfloor \operatorname {lb} \,n\rfloor } で与えられる。この発想は、多くのアルゴリズムやデータ構造の分析で使用される。例えば二分検索では、検索すべき空間の大きさは操作の繰り返しごとに半分になる。ゆえに、大きさ1の問題を得るには大まかにいって lb n 回の繰り返しが必要となり、そのあとは定数時間で終了する。同様に、n 個の要素からなる完全平衡二分探索木は、1 + lb n の高さをもつ。

しかし、アルゴリズムの実行時間は通常、定数倍の差を無視してランダウの記号で表記される。ここで、1以外の任意の正の数 k に対して log2 n = logk n / logk 2（底の変換）が成り立つので、O(log2 n) の実行時間をもつアルゴリズムは、1より大きな任意の底、たとえば13を用いて、O(log13 n) の実行時間を持つとも表現できる[3]。したがって、O(log n) や O(n log n) といった式では、対数の底がいくつであるかは本質的な問題ではない。

ただし、対数の底を指定する必要があるケースもあるので注意が必要である。例えば、所要時間 O(2lb n) の計算と、所要時間 O(2ln n) の計算とは同等ではない。前者は O(n) と等価であり、後者は O(n0.6931...) と等価である。

O(n log n) の実行時間をもつアルゴリズムは、しばしば線形対数と呼ばれる。O(log n) や O(n log n) の実行時間をもつアルゴリズムの例としては、次のようなものがある。

クイックソート（ただしこれは平均の場合であり、最悪の場合には O(n2) となる。）

2分探索木

マージソート

モンジュ配列（英語版）の計算

電卓の使用法

log2 のボタンがない電卓で log2 n を計算するための簡単な方法は、関数電卓に一般的に存在する自然対数 "ln" または常用対数 "Log" のボタンを使うことである。この場合、次のような底の変換公式を使うことになる。log2 n = ln n / ln 2 = Log n / Log 2

従って、log2 n = logen × 1.442695... = log10 n × 3.321928...

となる。

ところでこの式は、loge n + log10 n が0.6%以内の差で log2 n と一致する、という興味深い結果を与える。実際のところ、loge n + log10 n という式は、 e 1 / ( 1 + log 10 ⁡ e ) = 10 1 / ( 1 + log e ⁡ 10 ) = 2.00813   59293   46243   95422   87563   25191 … {\displaystyle e^{1/(1+\log _{10}e)}=10^{1/(1+\log _{e}10)}=2.00813\ 59293\ 46243\ 95422\ 87563\ 25191\ldots }

という底を用いて、log2.0081359... n と表現される。
二進対数の算出
整数→整数

小数点以下の切り上げ・切り捨てを行って、整数→整数の二進対数を定めることができる。これら二つ（切り上げ・切り下げ）の整数二進対数の間には、 ⌊ log 2 ⁡ n ⌋ = ⌈ log 2 ⁡ ( n + 1 ) ⌉ − 1 {\displaystyle \lfloor \log _{2}n\rfloor =\lceil \log _{2}(n+1)\rceil -1} 　　ただし、1 ≦ n

の関係がある[4]。この左辺の関数は、 ⌊ log 2 ⁡ 0 ⌋ = − 1 {\displaystyle \lfloor \log _{2}0\rfloor =-1} とおくことによって、定義域を n ≧ 0 にまで拡張できる。このように拡張した関数は、非負整数 n の m ビット符号なし二進表示における先頭の0の個数（英語版） nlz(n) との間で ⌊ log 2 ⁡ n ⌋ = ( m − 1 ) − nlz ⁡ ( n ) {\displaystyle \lfloor \log _{2}n\rfloor =(m-1)-\operatorname {nlz} (n)} [4]

の関係にある。この整数二進対数は、n の最上位ビットがどこにあるかを示している。
実数→実数

一般の正の実数に対しては、二進対数は次の2段階の手順で計算できる。
整数部分 ⌊ lb x ⌋ {\displaystyle \lfloor \operatorname {lb} \,x\rfloor } を計算する。

小数部分を計算する。

まず、整数部分の計算は簡単である。任意の正の実数 x に対して、2n ≦ x < 2n+1 となるような整数 n が唯一に定まる[5]。この各辺を 2n で割った 1 ≦ x/2n < 2 という式を立ててもよい。これをもって、二進対数の整数部分を n と定める。そして、この n を使って、小数部分を lb (x/2n) と表記することにする。すなわち、y = x/2n と置くと、次のようになる。lb x = n + lb y　　ただし、1 ≦ y < 2

小数部分 lb y は、掛け算と割り算のみを使って再帰的に計算できる。