ビット演算

この章では、データ単位の最小単位であるビットに関する操作について説明する。ビット操作は、マイクロプロセッサの最も基本的な機能の一つだ。

システムプログラマは、少なくともフラグパラメータを正しく使用するために、ビット演算を理解しておく必要がある。

データの一番低いレベルでの表現

プログラミング言語は抽象化だ。プログラミング言語で定義されたStudentのようなユーザー型は、コンピュータの内部構造とは直接関係がない。プログラミング言語は、ハードウェアの詳細を知らなくても、人間がハードウェアを使用できるようにするためのツールだ。

通常、ハードウェアを直接扱う必要はないが、ハードウェアレベルでのデータの表現方法を理解することは役立つ。

トランジスタ

現代の電子デバイスの処理能力は、主にトランジスタと呼ばれる電子素子に基づいている。トランジスタの重要な機能の一つは、トランジスタが属する電子回路の他の部分によって制御できることだ。ある意味、これにより電子回路は自分自身を認識し、自身の状態を変更できる。

ビット

情報の最小単位はビットである。ビットは、2つの状態を持つシステム(電子回路のいくつかのトランジスタの特別な配置など)によって表現できる。ビットには、0または1の2つの値がある。コンピュータのメモリでは、ビットに格納された情報は、新しい値が格納されるか、電源が切断されるまで保持される。

コンピュータはビットに直接アクセスすることはできない。その理由の一つは、そうするとコンピュータの設計が複雑になり、結果としてコンピュータのコストが高くなるためだ。もう一つの理由は、単一のビットで表現できる概念がそれほど多くないためだ。

バイト

バイトは8ビットの組み合わせだ。一意にアドレス指定可能な最小の情報単位はバイトである。コンピュータはメモリから読み込むか書き込む際に、少なくとも1バイト単位で行う。

そのため、1ビットの情報(falseまたはtrue)を保持するboolでも、1バイトとして実装する必要がある。

writefln("%s is %s byte(s)", bool.stringof, bool.sizeof);

boolは1バイト

レジスタ

マイクロプロセッサで処理されるデータはレジスタに格納される。レジスタは、非常に限られた機能だが非常に高速な操作を提供する。

レジスタのサイズは、マイクロプロセッサのアーキテクチャによって異なる。例えば、32ビットマイクロプロセッサには通常4バイトのレジスタが、64ビットマイクロプロセッサには通常8バイトのレジスタが搭載されている。レジスタのサイズによって、マイクロプロセッサが一度に効率的に処理できる情報量と、サポートできるメモリアドレスの数が決まる。

プログラミング言語によって実現されるすべてのタスクは、最終的にマイクロプロセッサの1つまたは複数のレジスタによって実行される。

2進数

日常生活で使用される10進数システムは、0123456789の10個の数字で構成されている。一方、コンピュータのハードウェアで使用される2進数システムは、0と1の2個の数字で構成されている。これは、ビットが2つの値で構成されることから直接的に導き出される結果だ。ビットが3つの値を持つ場合、コンピュータは3進数システムを使用することになる。

10進数の数字は、1、10、100、1000と、1つずつ順番に名前が付けられている。例えば、1023という数字は、次のように展開することができる。

当然、1桁を左に移動すると、その桁の値は10倍になる。1、10、100、1000などだ。

同じ規則を2進数システムに適用すると、2進数システムになる。数字は、1、2、4、8など、順番に番号が付けられている。つまり、1桁左に移動すると、その桁の値は2倍になる。1、2、4、8など。例えば、2進数の1011は、次のように展開できる。

数字を簡単に参照できるように、数字は右端から左端に向かって0から番号が付けられている。次の表は、2進数システムにおける32ビットの符号なし数値のすべての数字の値をまとめたものだ。

値の大きいビットは上位ビット、値の小さいビットは下位ビットと呼ばれる。

リテラルでは、2進リテラルは0bプレフィックスで指定されることをリテラルの章で覚えていると、次のプログラムは、リテラルの値が前の表の行にどのように対応しているかを示している。

import std.stdio;

void main() {
    //               1073741824                     4 1
    //               ↓                              ↓ ↓
    int number = 0b_01000000_00000000_00000000_00000101;
    writeln(number);
}

出力:

1073741829

リテラルは3つの0以外のビットのみで構成されていることに注意。出力される値は、前の表のビットに対応する値の合計である。1073741824 + 4 + 1 == 1073741829。

符号付き整数型の符号ビット

符号付き型の最上位ビットは、値が正か負かを決定する。

int number = 0b_10000000_00000000_00000000_00000000;
writeln(number);

-2147483648

ただし、最上位ビットは値から完全に切り離されているわけではない。例えば、上で示したように、数値の他のビットがすべて0であるからといって、その値が-0であるとは限らない。(実際、-0は整数としては有効な値ではない。) この章では、これはDでも使用されている2の補数表現によるものであることを指摘するだけにしておく。

ここで重要なのは、前の表の最大値である2,147,483,648は、符号なし整数型でのみ使用できる値であることだ。uintで同じ実験を行うと、まったく同じ値が表示される。

uint number = 0b_10000000_00000000_00000000_00000000;
writeln(number);

2147483648

この理由もあり、特に理由がない限り、ビット演算は常に符号なし型で実行する必要がある。ubyte、ushort、uint、ulong。

16進数

上記の0と1だけで構成されるリテラルからわかるように、2進法では、特に数字が大きい場合、読みづらくなることがある。そのため、より読みやすい16進法が、特にコンピュータ技術で広く採用されている。

16進数には16個の数字がある。アルファベットには10以上の数字がないため、このシステムでは、ラテンアルファベットから6文字を借用し、通常の数字とともに使用する:0123456789abcdef。数字a、b、c、d、e、fは、それぞれ 10、11、12、13、14、15の値を表す。ABCDEFの文字も使用可能だ。

他の数字体系と同様に、各数字の値は、その右側の数字の16倍になる。1、16、256、4096などだ。例えば、8桁の符号なし16進数のすべての数字の値は、次の通りだ。

16進リテラルは0xプレフィックスで指定されることを覚えておくと、各桁の値が数値全体の値にどのように寄与しているかがわかる。

//           1048576 4096 1
//                 ↓  ↓  ↓
uint number = 0x_0030_a00f;
writeln(number);

3186703

出力される値は、0以外のすべての桁の寄与によるものである。1048576の3、aの4096、fの1。aは10、fは15を表すことを覚えておくと、値は3145728 + 40960 + 15 ==3186703になる。

2進数と16進数の変換は簡単だ。16進数を2進数に変換するには、16進数の各桁を2進数に変換する。3つの数系における対応する表現は、次の表の通りだ。

例えば、16進数0x0030a00fは、前の表に従って各桁を個別に変換することで、2進数で次のように書くことができる。

// 16進数:     0    0    3    0    a    0    0    f
uint binary = 0b_0000_0000_0011_0000_1010_0000_0000_1111;

2進数から16進数への変換は逆である。2進数の各桁を4桁ずつ16進数に変換する。例えば、先ほど使用した2進数の値を16進数で表記すると、次のようになる。

// バイナリ:           0100 0000 0000 0000 0000 0000 0000 0101
uint hexadecimal = 0x___4____0____0____0____0____0____0____5;

ビット演算

値がビットによってどのように表現されるか、および数値が2進数および16進数でどのように表現されるかを確認した後、ビットレベルで値を変更する演算について見てみよう。

個々のビットに直接アクセスすることはできないため、これらの演算はビットレベルであっても、一度に少なくとも8ビットに影響を与える。例えば、型ubyteの変数では、その変数の8ビットすべてにビット演算が適用される。

最上位ビットは符号付き型の符号ビットであるため、以下の例では符号付き型は無視し、uintのみを使用する。ubyte、ushort、ulong、byte、short、int、longでも、最上位ビットの特別な意味を覚えておけば、これらの演算を繰り返すことができる。

まず、ビット演算子の動作を確認する際に役立つ関数を定義しよう。この関数は、値を 2進、16進、10進で出力する。

import std.stdio;

void print(uint number) {
    writefln("  %032b %08x %10s", number, number, number);
}

void main() {
    print(123456789);
}

同じ値を 2進、16進、10進の数値システムで表示すると、次のようになる。

補数演算子:~

配列の連結に使用される二項演算子 ~と混同しないでほしい。これは一項演算子~である。

この演算子は、値の各ビットをその反対の値に変換する。0のビットは1に、1のビットは0になる。

uint value = 123456789;
print(value);
writeln("~ --------------------------------");
print(~value);

二進数表現では効果が明確だ。すべてのビットが反転している(破線の下側):

一元演算子~の動作の要約は以下の通りだ:

~0 → 1
~1 → 0

And演算子:&

&は、2つの式の間に記述される2進演算子である。マイクロプロセッサは、2つの式の対応する2ビットを、他のすべてのビットとは別々に扱う。つまり、式の31、30、29などのビットは、それぞれ別々に評価される。結果の各ビットの値は、式の対応する2ビットが両方とも1の場合は1、それ以外の場合は0になる。

uint lhs = 123456789;
uint rhs = 987654321;

print(lhs);
print(rhs);
writeln("& --------------------------------");
print(lhs & rhs);

次の出力は、まず左辺の式 (lhs) を、次に右辺の式 (rhs) を示している。&演算の結果は、破線の下に示されている。

結果の1のビットは、式の両方のビットが1であるビットであることに注意。

この演算子は、左側と右側のビットが両方とも1の場合に1を生成するため、and演算子と呼ばれる。0と1の4つの組み合わせのうち、両方の値が1の場合のみ1が生成される。

0 & 0 → 0
0 & 1 → 0
1 & 0 → 0
1 & 1 → 1

観察事項:

• 一方のビットが0の場合、もう一方のビットの値に関わらず結果は常に0になる。したがって、"ビットを0でANDする"とは、そのビットをクリアすることを意味する。
• 一方のビットが1の場合、結果はもう一方のビットの値となり、1とANDしても何の影響もない。

OR演算子:|

|は、2つの式の間に記述される2進演算子である。マイクロプロセッサは、2つの式の対応する2つのビットを、他のすべてのビットとは別々に扱う。結果の各ビットの値は、式の対応する2つのビットが両方とも0の場合は0、それ以外の場合は1になる。

uint lhs = 123456789;
uint rhs = 987654321;

print(lhs);
print(rhs);
writeln("| --------------------------------");
print(lhs | rhs);

結果の値が0のビットは、式の両方の対応するビットが0であるビットであることに注意。左側または右側の対応するビットが1の場合、結果は1になる。

0 | 0 → 0
0 | 1 → 1
1 | 0 → 1
1 | 1 → 1

観察事項:

• 一方のビットが1の場合、もう一方のビットの値に関わらず結果は常に1になる。したがって、"ビットを1でOR演算する"とは、そのビットを1に設定することを意味する。
• 一方のビットが0の場合、結果はもう一方のビットの値となり、0でOR演算を行っても何の影響もない。

XOR演算子:^

Xorは、排他的論理和の略語だ。これも2進演算子である。2つの式の対応するビットが異なっている場合、結果は1になる。

uint lhs = 123456789;
uint rhs = 987654321;

print(lhs);
print(rhs);
writeln("^ --------------------------------");
print(lhs ^ rhs);

結果の1のビットは、式で対応するビットが互いに異なるビットであることに注意。

0 ^ 0 → 0
0 ^ 1 → 1
1 ^ 0 → 1
1 ^ 1 → 0

観察:

• "ビットをXOR演算する"とは、そのビットをクリアすることを意味する。

その値に関係なく、変数をそれ自身とXor すると、結果は常に0になる。

uint value = 123456789;

print(value ^ value);

右シフト演算子:>>

この演算子は、式のビットを指定したビット数だけ右にシフトする。シフトする余地のない右端のビットは、値から削除される。符号なし型の場合、左端のビットは0で埋められる。

次の例は、値を2ビット右にシフトして結果を生成している。

uint value = 123456789;
print(value);
print(value >> 2);

次の出力では、右側から削除されるビットと、値0になる左端のビットの両方を強調表示した。

強調表示されていないビットは2ビット分右にシフトされていることに注意。

左側から入力される新しいビットは、符号なし型の場合のみ0になる。符号付き型の場合、左端のビットの値は、符号拡張と呼ばれるプロセスによって決定される。符号拡張は、元の式の符号ビットの値を保持する。そのビットの値は、左側から入力されるすべてのビットに使用される。

符号ビットが1(つまり値が負)の符号付き型の値で、この効果を見てみよう。

int value = 0x80010300;
print(value);
print(value >> 3);

元の値の左端のビットは1であるため、結果の新しいビットもすべて1になる。

左端のビットが0の場合、新しいビットはすべて0になる:

int value = 0x40010300;
print(value);
print(value >> 3);

符号なし右シフト演算子:>>>

この演算子は、通常の右シフト演算子と同様に機能する。違いは、式の型や左端のビットの値に関係なく、新しい左端のビットは常に0になることだ。

int value = 0x80010300;
print(value);
print(value >>> 3);

左シフト演算子:<<

この演算子は、右シフト演算子の逆の動作をする。ビットが左にシフトされる:

uint value = 123456789;
print(value);
print(value << 4);

左側のビットは失われ、右側の新しいビットは0になる:

代入演算子

上記のすべての二項演算子には、代入演算子の対応するものが存在する:&=,|=,^=,>>=,>>>=, および<<=。整数と算術演算の章で見た演算子と同様に、これらの演算子は結果を左側のオペランドに代入する。

&=演算子でこれを見てみよう。

value = value & 123;
value &= 123;         // 上記と同じ

意味

これらの演算子がビットレベルでどのように機能するかを理解するだけでは、プログラムでの有用性を理解するには不十分かもしれない。次のセクションでは、これらの演算子がよく使われる方法を説明する。

|は共用体集合

|演算子は、2つの式で1のビットを共用体として生成する。

極端な例として、1ビットが交互に1に設定されている2つの値を考えてみよう。これらの値の共用体は、すべてのビットが1になる結果を生成する。

uint lhs = 0xaaaaaaaa;
uint rhs = 0x55555555;

print(lhs);
print(rhs);
writeln("| --------------------------------");
print(lhs | rhs);

&は交集合

&演算子は、2つの式で1になっているビットの共通部分を生成する。

極端な例として、最後の2つの値をもう一度考えてみよう。前の2つの式の1ビットは、もう一方の式と一致するビットがないため、結果のビットはすべて0になる。

uint lhs = 0xaaaaaaaa;
uint rhs = 0x55555555;

print(lhs);
print(rhs);
writeln("& --------------------------------");
print(lhs & rhs);

|= 選択されたビットを1に設定する

この動作を理解するには、一方の式を実際の式として、もう一方の式を1に設定するビットのセレクタとして見るとわかりやすい。

uint expression = 0x00ff00ff;
uint bitsToSet = 0x10001000;

write("before     :"); print(expression);
write("to set to 1:"); print(bitsToSet);

expression |= bitsToSet;
write("after      :"); print(expression);

影響を受けるビットの前後の値が強調表示されている。

ある意味では、bitsToSetが1に設定するビットを決定する。他のビットは影響を受けない。

&= 選択されたビットをクリアする

一方の式を実際の式、もう一方の式をクリアする(0に設定する)ビットのセレクタとみなすことができる。

uint expression = 0x00ff00ff;
uint bitsToClear = 0xffefffef;

write("before       :"); print(expression);
write("bits to clear:"); print(bitsToClear);

expression &= bitsToClear;
write("after        :"); print(expression);

影響を受けるビットの前後の値が強調表示される。

ある意味では、bitsToClearはどのビットを0に設定するかを決定する。他のビットは影響を受けない。

& ビットが1かどうかを決定する

式のいずれかで1に設定されているビットが1つだけの場合、その式を使用して、もう一方の式の対応するビットが1であるかどうかを照会することができる。

uint expression = 123456789;
uint bitToQuery = 0x00010000;

print(expression);
print(bitToQuery);
writeln(expression & bitToQuery ? "yes, 1" : "not 1");

照会対象のビットがハイライト表示される:

そう、1

今度は、bitToQueryの別のビットを1に設定して、同じ式の別のビットをクエリしよう。

uint bitToQuery = 0x00001000;

1でない

クエリ式に1が設定されているビットが2つ以上ある場合、クエリは、他の式に対応するビットのいずれかが1であるかどうかを判断する。

1ビット右シフトは2で割ることに相当する

値のすべてのビットを1位置右にシフトすると、元の値の半分になる。その理由は、上記の数字の値の表でわかる。この表では、各ビットは、その左にあるビットの値の半分になっている。

値を一度に複数のビット分右にシフトすることは、その回数だけ2で割ることを意味する。例えば、3ビット右シフトすると、値は8で割られる。

uint value = 8000;

writeln(value >> 3);

1000

2の補数システムでは、右シフトは符号付き値にも同じ効果をもたらす。

int value = -8000;

writeln(value >> 3);

-1000

1ビット左シフトは、2倍するのと同等である

各ビットは右側のビットの2倍の値であるため、値を1ビット左にシフトすると、その値は2倍になる。

uint value = 10;

writeln(value << 5);

2を合計5回乗算することは、32倍乗算することと同じだ:

320

一般的な用途

フラグ

フラグは、同じ変数にまとめて保持される1ビットの独立したデータだ。それぞれ1ビット幅しかないので、有効/無効、有効/無効などの 2 値概念を表現するのに適している。

このような1ビットの概念は、Cライブラリを基盤とするDモジュールで時々見られる。

フラグは通常、enum型の重複しない値として定義される。

例として、ゲームのリアリズムを設定できるカーレースゲームを考えてみよう。

• 燃料消費が現実的かどうか。
• 衝突で車が損傷するかどうか。
• タイヤは使用により摩耗するかしないか。
• 道路表面にスリップ痕が残るか否か。

これらの設定オプションは、実行時に次のenum値で指定できる。

enum Realism {
    fuelUse    = 1 << 0,
    bodyDamage = 1 << 1,
    tireUse    = 1 << 2,
    skidMarks  = 1 << 3
}

これらの値はすべて、互いに矛盾しない単一のビットで構成されていることに注意。各値は、1ビットずつ異なる数だけ左シフトすることで決定される。対応するビット表現は次の通りだ。

1ビットは他のビットと一致しないため、これらの値は、|演算子によって組み合わせて同じ変数に保持することができる。例えば、タイヤに関連する2つの設定オプションは、次のコードのように組み合わせることができる。

Realism flags = Realism.tireUse | Realism.skidMarks;
writefln("%b", flags);

これらの2つのフラグのビットは、変数flags内で隣り合って格納される:

1100

後で、これらのフラグは&演算子で照会できる:

if (flags & Realism.fuelUse) {
    // ... 燃料消費に関するコード ...
}

if (flags & Realism.tireUse) {
    // ... タイヤの摩耗に関するコード ...
}

&演算子は、flagsに指定されたフラグが設定されている場合のみ1を返す。

また、0以外の値は自動的にtrueに変換されるため、結果はif条件で使用できることに注意。条件式は、&の結果が0の場合はfalse、それ以外の場合はtrueになる。その結果、フラグが有効になっている場合にのみ、対応するコードブロックが実行される。

マスキング

一部のライブラリおよびプロトコルでは、整数値は複数の情報を保持する場合がある。例えば、32ビット値の上位3ビットは特定の意味を持ち、下位29ビットは別の意味を持つ場合がある。このような別々のデータ部分は、マスキングによって変数から抽出することができる。

IPv4アドレスの4つのオクテットは、この概念の例である。オクテットは、IPv4アドレスの一般的なドット表記を構成する個々の値だ。これらはすべて、単一の32ビット値に格納される。例えば、IPv4アドレス192.168.1.2は、32ビット値0xc0a80102である。

c0 == 12 * 16 + 0 = 192
a8 == 10 * 16 + 8 = 168
01 ==  0 * 16 + 1 =   1
02 ==  0 * 16 + 2 =   2

マスクは、変数の特定の部分を覆う1ビットの数字で構成される。値をマスクで"And"すると、そのマスクで覆われた変数の部分が抽出される。例えば、マスク値0x000000ffは、値の下位8ビットを覆う。

uint value = 123456789;
uint mask  = 0x000000ff;

write("value :"); print(value);
write("mask  :"); print(mask);
write("result:"); print(value & mask);

マスクで覆われるビットはハイライト表示される。その他のビットはクリアされる:

同じ方法を、IPv4 アドレス 0xc0a80102に、最上位の8ビットを覆うマスクを適用しよう:

uint value = 0xc0a80102;
uint mask  = 0xff000000;

write("value :"); print(value);
write("mask  :"); print(mask);
write("result:"); print(value & mask);

このマスクは、値の最上位8ビットを覆う。

ただし、表示結果は予想の192ではなく3221225472になっていることに注意。これは、マスクされた値も右端にシフトしなければならないためだ。値を24ビット分右にシフトすると、その8ビットが表す値になる。

uint value = 0xc0a80102;
uint mask  = 0xff000000;

write("value :"); print(value);
write("mask  :"); print(mask);
write("result:"); print((value & mask) >> 24);

演習

1. IPv4 アドレスをドット形式で返す関数を作成しよう。

   string dotted(uint address) {
       // ...
   }
   
   unittest {
       assert(dotted(0xc0a80102) == "192.168.1.2");
   }

   D

   IDEで開く
2. 4つのオクテット値を対応する32ビットのIPv4アドレスに変換する関数を作成しよう。

   uint ipAddress(ubyte octet3,    // 最も重要なオクテット
                  ubyte octet2,
                  ubyte octet1,
                  ubyte octet0) {  // 最も重要でないオクテット
       // ...
   }
   
   unittest {
       assert(ipAddress(192, 168, 1, 2) == 0xc0a80102);
   }

   D

   IDEで開く
3. マスクの作成に使用できる関数を作成しよう。指定したビットから始まり、指定した幅を持つ必要がある。

   uint mask(int lowestBit, int width) {
       // ...
   }
   
   unittest {
       assert(mask(2, 5) ==
              0b_0000_0000_0000_0000_0000_0000_0111_1100);
       //                                            ↑
       //                                    最下位ビットは2で、
       //                                    マスクは5ビット幅である
   }

   D

   IDEで開く