■■■ はじめに
数字はコンピュータの世界で当り前にあるものです。当り前すぎて、基本的な知識が欠落したままになる恐れがあります。ある日突然、意味不能な計算誤差を目にしたり、知識不足からセキュリティホールを埋め込む可能性があります。また、プログラミング作業の中で、パフォーマンスチューニングや、処理性能をスケールさせることが重要になる局面が多くあります。このとき、数字に対する適切な感覚と正しい理解が助けになります。本特集は、数字に関してプログラマが知っておくべき知識を、ソフトウェアとハードウェアの両面から説明します。


■■■ ビット
現代のほとんどのコンピュータは2進数を元にしたシステムです。ビット(bit)の意味は、2つの状態を取る事象を情報として抽象化した時の、情報の単位です。ビットはbinary digitの略から作られた用語で、一般に、ビットは数値の0と1で表現します。0と1が並んだ列を数値と見なす時、これを2進数と呼びます。

ハードウェアのレベルで、0と1が並んだ列を数値と見なすことの意味を考えると、CPU(脚注1>)が、ある長さの列に対してどのような演算をするか、ということを意味します。現在最も一般的なCPUは32bitですが、これは、演算の基本単位が32個の長さのビット列であることを示しています。

<脚注1>
正確には、CPUの抽象機能のひとつ、演算論理回路(ALU:Arithmetic Logic Unit)と書くべきですが、分かりやすさのためにCPUと書きます。
</脚注>


■■ ビット演算
読者の中には、ビット演算を使ったことが無い人もいるかもしれません。使う機会が無いことは悪い話ではありません。高レベルなプログラミング言語になれば、使う機会が減るのは事実だからです。しかし、ビット演算を知らないために、使うべき局面で使えないことは、良い話ではありません。だからと言って、使う必要も無い局面で、ビット演算を使ってコードを書くのは最悪です。一般的に可読性が落ちるからです。この時、ビット演算のコードが読めないから書き直してください、とは言いたくないはずです。ビット演算を理解した上で、自信を持って、可読性が悪いので書き直してください、と言えるようになってください。

ビット演算の真理値表とJavaの演算子の対応表を表1に示します。

表1に従いビットごとに値を計算するだけで、ビット演算の結果を得ることができます。Javaは2進数を整数リテラルとしてコードに直接書けませんが、書けたと仮定して、次のような演算を考えます。

010 & 111 (値はどちらも2進数)

桁上がりが無いので、上位桁と下位桁、どちらから考えても構いません(脚注2)。上位桁から見ると、0と1の&は0、1と1の&は1、0と1の&は0です(表1参照)。演算結果は010になります。

----------------------
<表1> ビット演算の真理値表とJavaの演算子
----------------------

<脚注2>
最上位ビットをMSB(most significant bit)、最下位ビットをLSB(least significant bit)と呼びます。
</脚注2>


■■ よく使うビット演算
ビットをフラグとして使う場合を例に、ビット演算の典型例を示します。ただし、Javaの場合、一般的にはBitSetクラスを使うべきです。ここでは、より低レベルのプログラミング言語を使うことを想定して読んでください。

特定のフラグを立てるには次のように | (OR演算)を使います。

flag |= mask;

flagはフラグ値を持たせた変数です。maskは立てたいフラグの位置のビットが1、それ以外が0の値を持つ変数です。1にしたいビット位置がコンパイル時に分かっている場合、次のように定数リテラルで初期化するのが簡単です。

static final int mask = 0xa;

次のようにシフト演算を使うと、ビット位置を明示できて、コードの意図が明確になります。以下の例は、右から1ビット目と3ビット目に1が立ちます(実際のコードでは3や1を定数として定義します)。

static final int mask = (1<<3) | (1<<1);

特定のフラグを落すには次のように & (AND演算)を使います。

flag &= ~mask;

maskは落としたいビット位置を1にします。

特定のフラグを反転するには次のように ^ (XOR演算)を使います。

flag ^= mask;

maskは反転したいビット位置を1にします。

特定のフラグのうち最低ひとつが立っていることの判定は次のように行います。

flag & mask

maskは判定したいビット位置を1にします。


■ アラインメント処理
整数nに対して、n以上で定数Nの倍数の最小値を求めたいとします。例えばNが4であれば、n=0,1,2,3,4には4を返し、n=5,6,7,8には8を返します。C言語などで、メモリのバイト境界に合わせる(アラインメント処理)ために必要な処理です。最も素直なコードはリスト1のコード1になります。nより大きい、Nの倍数の最小値を求めるコードの場合、リスト1のコード2になります。

----------------------
<リスト1> 素直なアラインメント処理
----------------------

Nが2の倍数の場合、ビット演算を使って次のように書くこともできます(リスト2)。実際に小さなビット長で計算してみてください。

----------------------
<リスト2> ビット演算を使ったアラインメント処理
----------------------

Javaでビット演算を使う場合と使わない場合の速度を比較してみます。メソッド呼び出しを避けるため、式で書きやすい、「nより大きい、Nの倍数の最小値を求めるコード」で比較しました(リスト3)。

JDK6でコンパイルして実行したところ、ビット演算を使わない処理は数100ミリ秒、ビット演算を使った処理は数10ミリ秒でした。これだけの回数ループをまわしての差なので、現実的には、ほとんど差が無い、と言うべきです。

----------------------
<リスト3> ビット演算を使うコードの速度比較
----------------------


■■■ 整数
ビット列を数値と見なす最も代表的なケースは整数です。現在の多くのプログラミング言語で、intとして知られる型です。多くのプログラミング言語は、8進数、10進数、16進数のリテラル表現を許しています(脚注3)。これらの8、10、16を基数(radixもしくはbase)と呼びます。4bitの場合の対応を表2に示します。

<脚注3>
多くの場合、8進数は070のように先頭を0から始め、16進数は0x1fのように先頭を0xで始めます。一部の言語(RubyやPerl)は2進数のリテラル表現を許しています(0b010など)。
</脚注3>

----------------------
# [Q] これは常識すぎて不要?
<表2> 4bitの対応表
----------------------

ソースコード上、どんな基数で整数を書こうと、値が同じであれば、実行時にそれらの区別はありません。ソースコードに書かれた10、012、0xaという数値は、実行時には同じ値の数値でしかありません。

プログラミングの初心者によくある質問で、ソースコード上に書かれた16進数を見て、10進数の数値に変換する方法を知りたい、というものがあります。ソースコード上に人間が16進数で数値を書いても、その基数が実行時にコンピュータにとって意味を持つことはありません(脚注4)。質問に戻ると、数値を特定の基数で表記した文字列に変換したいことが、質問者のやりたいことであることが多いです。つまり、0xaという数値に対して、10進数で"10"や2進数で"1010"の文字列として見たい、が質問の意図です。意地悪な人は、意図が分かっていても、数値の基数の変換なんてできない、と答えるかもしれません(意地悪ではなく、たぶんあなたを試しているのです)。その場合、文字列に変換したい意図を伝えましょう。

<脚注4>
コンピュータにとっては常に基数は2、という言い方もできます。
</脚注4>


■■ 基数の変換 (ここはコラムでもいいかも)
実行時のコンピュータに基数は意味が無くても、ソースコードを読む人間には意味があります。数値を別の基数の表記に変換したいことはよくあります。関数電卓や電卓ソフトを使う手もありますが、格好悪いのでお薦めしません。最も簡易な方法は、コマンドラインでperlを使う方法だと思います(図1)。

----------------------
<図1> perlで数値の基数の変換
----------------------

perlが使えない環境のために、筆者は図2のような関数をシェルで定義しています。

----------------------
<図2> シェルで数値の基数の変換
----------------------


■■ 符号
符号付き整数を表現するには、一般に2の補数(2's complement)と呼ばれる形式を使います。4bitの場合を例に、符号無しと符号付きの図を示します。図4を見てわかるように、符号の正負は最上位ビットで区別ができます。

----------------------
<図3> 4ビットの符号無し整数
----------------------

----------------------
<図4> 4ビットの符号付き整数
----------------------

2の補数とは別に、1の補数(1's complement)と呼ばれる符号の表現形式もあります。現在のアーキテクチャでは2の補数が一般的です。2の補数と1の補数の求め方を図5に示します。なおJavaでは~演算子を使って1の補数を求めることができます(脚注5)。

----------------------
<図5> 2の補数と1の補数の求め方
----------------------

<脚注5>
2の補数は、intもしくはlongで符号を逆転すれば求められます。
</脚注5>



■■ 桁あふれ(オーバーフロー)
前節の図3と図4の円上で、それぞれの値に1ずつ加算すると、結果は時計まわりの次の値になります(0に1を足すと1、1に1を足すと2)。両者とも不連続点が一ヶ所あります。図3の場合、15から0に変化する0時の方向が不連続点です。図4の場合、7から-8に変化する6時の方向が不連続点です。4bit符号なし整数は、15に1を足した結果が0になります。4bit符号付き整数は、7に1を足した結果が-8になります。これらを桁あふれと呼びます。不連続点は、減算(反時計まわり)でも事情は同じです。なお、CPUのレベル(2進のビット列)で見ると、符号があろうとなかろうと、加算処理に違いが無いことにも注意してください(符号の有無に関わらず同じCPU命令です)。

整数演算で桁あふれが起きた場合、基本的には期待する答えが得られていないので、バグです。単に答えが間違うだけではなく、昨今では、セキュリティホールになることもあります。例えば、ばらけた値が欲しくて次のような計算をしたとします。

乱数(0から正の最大数) * ユーザーに入力させる正の整数 % 1024

1024の剰余をとっているので、結果は0から1023の間の数になると思うかもしれません。符号付きの整数の場合、結果は-1023から1023の間の数になります。0から1023の間になると仮定して、配列のインデックスに使っていると予期せぬ結果をうむことがあります。


■■ 大きな整数
Javaのintは32bit、longは64bitです。現在の一般的なCPUでは、1命令で行える演算は32bitや64bitです。これより大きなビット数の整数を扱うことはできないのでしょうか。もちろんできます。より大きなビット数の演算を行うには、1回のCPU命令ではできないので、ソフトウェアによる繰り返し処理が必要です。

JavaにはBigIntegerという標準クラスが用意されています。ここでは、BigIntegerの加算メソッドの実装を例に、大きな整数の扱いを見ます。リスト4はjava.math.BigIntegerクラスのaddメソッドの抜粋です。ふたつの引数のバイト長が等しい場合に限定して、コードを抜粋しています。

----------------------
<リスト4> java.math.BigIntegerからコードを整形して抜粋
----------------------


説明を簡単にするため、intが4bit長、longが8bit長だと見なして説明します。

引数xとyの配列の長さ(BigIntegerのコードは長さが異なっても動きますが、抜粋したコードは等しい前提で抜粋しています)がもし3であれば、xIndexとyIndexは3になるので、whileループは3回まわります。ループは、x[2]とy[2]、x[1]とy[1]、x[0]とy[0]と、配列を後ろからなめながら加算し、結果をsumに格納します。

[1]行目で、配列の要素をLONG_MASKでAND演算しています。やりたいことはintからlongへの拡張です。素直にキャストを使わない理由はなんでしょうか。Javaでintからlongへキャストすると、符号を保ったままビット長を拡張します。1111(intが4bit長だと仮定)をlong(8bit長と仮定)にキャストすると、11111111になります(10進数で考えるとどちらも-1です)。[1]行目で欲しい値は、1111から00001111です。つまり4bit部分を変化させないまま、ビット長を倍にすることが目的です。このための手段がLONG_MASKでのAND演算です。

[2]行目および[3]行目の最小値は 00000000、最大値は 00001111 になります。この加算結果の範囲は 00000000 から 00011110 になります。
[4]行目はsumを32bit右シフトする演算です。intを4bit長と仮定した場合、ここの処理は sum >>> 4 と考えてください。>>>演算は右シフトで空いたビットを0で埋めます。sumの初期値はゼロなので、最初のループではシフト演算結果もゼロです。結果的に、最初のループでsumの取りうる値の範囲は 00000000 から 00011110 です。2度目以降のループでは、前回のループのsumの値を4bit右シフトします。この意味は下位4bitが消えて、上位4bitが値として残るということです。つまり、sum >>> 4 の取りうる値の範囲は 0 から 1 です。[2][3][4]を足したsumの取りうる値の範囲は 00000000 から 00011111 になります。このようにループがまわると、[2]と[3]の加算の結果が4bitの範囲を越えた場合、次のループ時に sum >>> 4 が1になります。日常の足し算でもお馴染みの、繰り上がり処理に相当することが見て取れると思います。ここまでの説明を図6に示します

----------------------
<図6> 大きな数の加算の例
----------------------


■■■ 浮動小数点数

■■ 実数
多くのプログラミング言語には、実数を表す型が用意されています。一般にfloatやdoubleと呼ばれています。この内部表現が浮動小数点数(floating point number)です。現代のPCはハードウェア命令として浮動小数点数の演算命令を持っています(脚注6)。

<脚注6>
ビット演算さえできれば、整数演算も浮動小数点数演算もソフトウェアで書くことは可能です。
</脚注6>

浮動小数点数の考え方を知るためにまず10進数で考えます。図7のように異なる桁の数を、仮数(かすう)と基数と指数で表現します。仮数の取り方でいくつもの表現方法がありますが、仮数を1以上2未満に正規化することで、仮数、基数、指数は一意に決めます。

----------------------
<図7> 浮動小数点数の基本(10進数)
----------------------

実際のコンピュータでは基数が2です。小数点以下に関しても次の図8のように基数2で考えます。

----------------------
<図8> 浮動小数点数の基本(2進数)
----------------------

浮動小数点数の内部形式はIEEE754と呼ばれる標準規格が一般的です。32bit(Javaではfloat)の場合を図9に示します。IEEE754は32bit以外も形式を決めていますが、基本的な考え方は同じです(ビット幅が異なります)。

----------------------
<図9> IEEE754
----------------------

Javaのコードで確認してみます(リスト5)。

----------------------
<リスト5> floatの内部表現の確認
----------------------


■■■ BigDecimal
本誌の読者にはWebアプリケーションの開発者が多いと思います。現在のWebアプリケーションの適用分野で、浮動小数点数を使う局面はあまり無いと思います。なぜなら、原理的に浮動小数点数の誤差を無くすことができないからです(脚注6)。業務系システムで、小数点以下が必要になる最も典型的な数値は金額だと思います(課税、利息、外貨など)。誤差が許されないため、金額に浮動小数点数演算は使えません。

<脚注6>
科学計算やシミュレーションの世界では、そもそも測定データ自体が誤差を含んでいるので、有効数字以上の桁に関して正確さを追求する意味がありません。このような世界では、浮動小数点数の理解が必要です。そして、計算を繰り返す過程で計算誤差が蓄積して拡大することを防ぐテクニックが重要になります。
</脚注6>

Javaにはこの用途のためにjava.math.BigDecimalというクラスがあります。BigDecimalは内部的に、図10のように情報を保持しています。見て分かるように有限桁数の小数で値を保持するので、実数のすべての正確な値を保証できるわけではありません。

演算は小数点以下の桁数を(被演算数のうち大きい方に)合わせてから、整数の演算を行います。このため、浮動小数点数にあるような計算誤差はありません。

----------------------
<図10> BigDecimalの内部表現
----------------------


■■ BigDecimalの注意点
BigDecimalは基本型ではないため、演算子を使った演算はできません。リスト6のようにメソッドを呼ぶ必要があります。

----------------------
<リスト6> BigDecimalの使用例
----------------------

BigDecimalのequalsメソッドは、値と小数点以下の桁数の両方が一致した場合にのみtrueを返します。つまり、次の式はfalseを返します。

new BigDecimal("1.0").equals(new BigDecimal("1.00"))

数字の大小比較をしたい場合は、compareToメソッドを使ってください。このメソッドは真偽値ではなく、-1,0,1を返すことに注意してください(値が等しい時、0を返します)。

次のように計算結果が無限小数になる場合、例外(java.lang.ArithmeticException)が起きます。

new BigDecimal("1").divide(new BigDecimal("3")); // 例外発生

この場合、リスト7のように計算の打ち切り規則を指定する必要があります。ROUND_HALF_UPは4捨5入の指定です。どの位で4捨5入するかは、被演算数の位の大きい方で決まります。"1"と"3"の場合、小数点以下がどちらも0桁なので、小数点以下1桁で0.3を4捨5入して結果が0になります。"1.000"と"3"を指定すると、小数点以下4桁で4捨5入して結果が0.333になります。

----------------------
<リスト7> BigDecimalの除算
----------------------