HHeLiBeXの日記 正道編

日々の記憶の記録とメモ‥

Nを表すのに必要な最低限のビット数

数学 Java

Javaのあるプログラムで非負整数Nに対する以下のような式を見かけた。

int n = (int)(Math.log10(N) / Math.log10(2) + 1.0);

最初、何を求めているのかしばらく分からなかったのでメモ。

ちなみに以下のように書いても同じ(はず)である。

int n = (int)Math.ceil(Math.log10(N) / Math.log10(2));

上記の答えnが何を表すかというと、タイトルに書いてしまったが、Nを2進数にしたときの長さ、つまりビット数の最小値を求めている。

なぜこれでビット数が求められるのかの証明と、他の求め方を記録しておく。

対数を使った求め方の証明

分かってしまえば簡単な話なのだが、以下のようにして証明できる。

非負整数Nを表現するのに必要なビット数をpとすると、
{\displaystyle 2^p > N }
が成り立つ。この両辺の常用対数を取ると、
{\displaystyle log_{10}{2^p} > log_{10}{N} }
{\displaystyle p*log_{10}{2} > log_{10}{N} }
{\displaystyle p > \frac{log_{10}{N}}{log_{10}{2}} }
右辺は小数になるので、
{\displaystyle p = \lceil \frac{log_{10}{N}}{log_{10}{2}} \rceil }

他の求め方

他の求め方としては、以下の2通りがある。

int n = Long.bitCount(Long.highestOneBit(N) - 1) + 1;

int n = Long.toBinaryString(N).length();

1つ目の方法の説明は以下の通り。

  1. まずLong.highestOneBit(N)で最上位のビットのみを残した値を求める。
  2. そこから1を引くと、最上位のビットが0になり、代わりにそれ以下のビットが全て1となる。
  3. Long.bitCount()で1となっているビット数をカウントする。
  4. 最上位のビットの分の1を足す。

2つ目の方法は、説明するまでもないと思うが、単純にNを2進数文字列に変換してその長さを取得しているだけ。 ただし、この方法は他の2つの方法に比べてStringオブジェクトを生成している分だけメモリコストや時間的コストがかかるので、シビアな状況においては要注意。