パズル
先日こんなツイートが流れてきました。
@Java Puzzler:
— Peter Lawrey (@PeterLawrey) 2017年1月25日
int i = 0;
for (float f = 16384; f < 16384 + 1; f += 1e-3f)
i++;
What is i?
しばらく考えてみましたが、分かりませんでした・・・。
実行してみて答えを見てみましたが、なぜそうなるのかがぱっと見わかりませんでした。そこで。
解説を考えてみた
floatとは
問題にfloatがあるのでfloatの仕組みを知る必要があります。まず見るのは当然ながら言語仕様です。
4.2.3. Floating-Point Types, Formats, and Values
The floating-point types are float and double, which are conceptually associated with the single-precision 32-bit and double-precision 64-bit format IEEE 754 values and operations as specified in IEEE Standard for Binary Floating-Point Arithmetic, ANSI/IEEE Standard 754-1985 (IEEE, New York).
IEEE 754に概念的に関連づけられている、つまり準拠しているとわかります。ではIEEE 754準拠とは何か。わかりやすいサイトがありました。
IEEE754 Floating Point Number ※
単精度のIEEE 754浮動小数点数は、符号ビット（1 ビット）、指数部（8 ビット）、仮数部（23 ビット）の 32 ビットで表現されます。
参考：WikipediaのIEEE 754 での単精度浮動小数点数の形式: binary32 ではそれが図解されています。
検証
さて、※のサイトを参考に Integer.toBinaryString(Float.floatToRawIntBits(floatValue)); というコードを使って検証してみます。
System.out.println("rawIntBits(16384f )=" + Integer.toBinaryString(Float.floatToRawIntBits(16384f)));
System.out.println("rawIntBits(16384f + 1e-3f)=" + Integer.toBinaryString(Float.floatToRawIntBits(16384f + 1e-3f)));
これはどうなるでしょうか？
出力結果はこうなります。
rawIntBits(16384f )=1000110100000000000000000000000
rawIntBits(16384f + 1e-3f)=1000110100000000000000000000001
ここで、文字は31文字しか出ていませんので、実際の表現は
rawIntBits(16384f )=01000110100000000000000000000000
rawIntBits(16384f + 1e-3f)=01000110100000000000000000000001
であることに注意が必要です。（そう出力するようにコードを書けばよいだけですが）
さて、これが意味するところは何でしょうか？
APIドキュメント にありますが、
- 31ビット目：符号s(0がプラス、1がマイナス)
- 30-23ビット目：指数部e
- 22-0ビット目：仮数部m （※のサイトにあるとおり、最上位ビットが常に1となるため2ビット目以降の値)
です。s, e, m をそれぞれ使って、浮動小数を示します。
value = (-1)^s\times (1.m)_{2}\times 2^{e-127}
16384f
これは、
| s | e | m |
|---|---|---|
| 0 | 10001101 | 00000000000000000000000 |
なので、
\begin{align}
(-1)^0\times (1.00000000000000000000000)_{2}\times 2^{141-127} &= 1\times1\times2^{14} \\
&=16384
\end{align}
ということですね。
16384f + 1e-3f
同様に置くと、
| s | e | m |
|---|---|---|
| 0 | 10001101 | 00000000000000000000001 |
となり、
\begin{align}
(-1)^0\times (1.00000000000000000000001)_{2}\times 2^{141-127} &= 1\times (1+2^{-23}) \times 2^{14} \\
&= 1.00000011920928955078125 \times 16384 \\
&= 16384.001953125
\end{align}
話の核心
そう、つまり、1e-3=0.001 と考えると、クイズのループは、(16384 + 1 - 16384) ÷ 0.001=1000なので1000回回ることになり答えは1000になるはずです。ところが、上記で解説したとおり、16384+1e-3f=16384.001953125 ですから、1回のループで0.001よりも多く加算されてしまっています。ということは、1000回よりも少なくなります。
答え
1回のループで増分となった 0.001953125 は $2^{-9}$ です。つまり、クイズのfがループ終了条件に達するには $2^{9}$ 回のループが必要ということになります。
ということで、答えは 512 になります。