Rust でのビット演算 ~ 基礎から実践まで

はじめに

ビット演算とは、数値をビット単位で操作する演算のことです。

本記事では、Rust でのビット演算について丁寧に解説します。ビットの概要から始まり、ビット演算の基本、ビットマスク、ビットフィールド、最後に、ユーザの権限情報や優先度の管理など実践的な内容を取り上げます。

ビット（bit）

コンピュータ上では、あらゆるデータが 2 種類の電気信号 ( 0 と 1に対応 ）で表現されています。つまり、コンピュータ内部のデータは 2 進法によって表現されています。

コンピュータが扱うことのできるデータの最小単位はビット（ bit ）として表されます。

ビットは 0 または 1 のいずれかの値を持つことができます。つまり、n ビットは 2ⁿ 通りのデータを表現できます。（例: 2 ビットでは 00, 01, 10, 11 の 4 通り）

ビット	1	2	...	n
表現できるデータの種類	2	4		2n

2 進数で数を表すときに、0110 のように上位の桁が 0 であっても 0 を記述することがあります。これは、コンピュータ内部でその数を表すために何ビット使用されているかを明示するためです。

また、ビット以外にコンピュータでデータ量を表す単位として、バイト（ Byte ）があります。1 バイトは 8 ビットで構成されます。したがって、1 バイトは 2⁸ = 256 通りのデータを表現することができます。

バイト	1	2	...	n
ビット	8	16	...	8n
表現できるデータの種類	28	216		28n

ビット列（bit string）

ビット列とは、0 か 1 が複数並んだものを指します。コンピュータ内部では整数はビット列として表現します。

ビット列の長さは任意のビット数になりますが、通常はバイト単位（ 8, 16, 24, 32, ... ）で扱われます。
例えば、10 進数の 5 は 8 ビットの長さのビット列では 00000101 と表されます。

Rust でも整数型はバイト単位で定義されています。

ビットの表現方法

Rust では、整数型は符号付き（i8, i16, i32, i64, i128, isize）と符号なし（u8, u16, u32, u64, u128, usize）の 2 種類に分類されますが、どちらもバイト単位でメモリ上に格納されます。

符号なし整数型は、0 から最大値（u8 は 2⁸-1、u32 は 2³²-1）までの範囲で値を持つことができます。符号付き整数型は、負の数を含む範囲（i8 は -2⁷ ~ 2⁷-1、i32 は -2³¹ ~ 2³¹-1）で値を持つことができます。

ビット数	符号付き整数	符号なし整数
8	i8	u8
16	i16	u16
32	i32	u32
64	i64	u64
128	i128	u128
ポインタサイズ	isize	isize

※ ポインタサイズはアーキテクチャに依存し、32 ビットまたは 64 ビットです。

以下に符号付き 8 ビット整数を使った例を示します。

fn main() {
    let x: i8 = 10; // 1010 in binary
    // |0|0|0|0|1|0|1|0| <- `i8` は 8 bit のメモリを使用し、整数を表現

    // さまざまな出力方法
    println!("Default: {}", x); // 10 進法
    println!("Binary: {:b}", x); // 2 進法
    println!("Binary(8 bit): {:08b}", x); // 2 進法（ゼロ埋め 8 桁）
    println!("Binary(16 bit): {:016b}", x); // 2 進法（ゼロ埋め 16 桁）
}

Rust の println! マクロでは、さまざまフォーマット指定子（:b、:5、:08）を使用して数値や文字列の表示形式を制御できます。

デフォルト {} では整数型は 10 進法で表示されますが、{:b} にすると 2 進法、 {:x} にすると 16 進法で表示されます。
また、{:n} は指定された文字幅（n）で表示します（右詰めで表示され、文字幅を満たさない部分は空白で埋めます）。{:0n} も指定された文字幅（n）で表示しますが、文字幅を満たさない部分を 0 で埋めます。
{:08b} は、ゼロ埋めを行い、8 桁の 2 進数で出力することを指示します。

実行結果

Default: 10
Binary: 1010
Binary(8 bit): 00001010
Binary(16 bit): 0000000000001010

Rust では、負の整数は 2 の補数を用いて表現されます。2 の補数表現では、負の整数を表すために正の整数のビットを反転させ、さらに 1 を加えます。

例えば、8 ビットでの 2 の補数表現を考えます。

• 10 の 2 進法では 00001010
• -10 を得るには、まずビットを反転: 11110101
• 次に、1 を加えます: 11110110

let y: i8 = -10; // 11110110 in memory
println!("y: {:b}", y); // y: 11110110

整数値を記述する際、一般的には 10 進法を用いるのが一般的です。しかし、Rust では 10 進法だけでなく、2 進法、8 進法、16 進法といった他の形式で整数を記述することができます。

let x: i8 = 0b1010; // `0b` を先頭に記述し、2 進法であることを示す

println!("Default: {}", x); // 10 進法
println!("Binary: {:b}", x); // 2 進法
println!("Binary(8 bit): {:08b}", x); // 2進法（ゼロ埋め 8 桁）

実行結果

Default: 10
Binary: 1010
Binary(8 bit): 00001010

ビット演算（bitwise operation）の基本

論理演算

ビットの演算には以下のような演算子があります。

• AND（&）
  2 つの数の各桁が同時に 1 の場合に 1 を返す演算子
  例: 1010 と 0101 は、どの桁も同時に 1 にならないので 0000
• OR（|）
  2 つの数の各桁が少なくとも 1 の場合に 1 を返す演算子
  例: 1010 と 0101 は、どの桁も少なくとも一方が 1 なので 1111
• XOR（^）
  2 つの数の各桁が異なる場合に 1 を返す演算子
  例: 1010 と 0101 は、どの桁も異なる数字なので 1111
• NOT（!）
  1 つの数の各桁を反転させる演算子（0 を 1 に、1 を 0 にする）
  例: 1010 は各桁を反転させると 0101

let x: i8 = 10; // 00001010 in memory
let y: i8 = 5;  // 00000101 in memory

// Bitwise AND
let bitwise_and = x & y;
println!("result: {:08b}", bitwise_and); // result: 00000000

// Bitwise OR
let bitwise_or = x | y;
println!("result: {:08b}", bitwise_or); // result: 00001111

// Bitwise XOR
let bitwise_xor = x ^ y;
println!("result: {:08b}", bitwise_xor); // result: 00001111

// Bitwise NOT
let bitwise_not = !x;
println!("result: {:08b}", bitwise_not); // result: 11110101

シフト演算

上記以外にも、Left Shift や Right Shift などの演算子もあります。

• Left Shift（<<）
  各桁を n 桁左にずらす。空いた部分は 0 で埋める。
  • 00001010 は 2 桁左にシフトすると 00101000（空いた 2 桁は 0 で 埋める）
• Right Shift（>>）
  1 つの数を n 桁右にずらす。空いた部分は、符号なし整数型（u8 など）の場合は 0 で埋め、符号付き整数型（i8 など）の場合は、左端の数と同じ数で埋める。
  • 10011100(u8) は 2 桁右にシフトすると 00100111（0 で埋める）
  • 00001010(i8) は 2 桁右にシフトすると 00000010（左端の数と同じ 0 で埋める）
  • 10011100(i8) は 2 桁右にシフトすると 11100111（左端の数と同じ 1 で埋める）

let x: i8 = 100;  // 01100100 in memory
let y: i8 = -100; // 10011100 in memory
let z: u8 = 156;  // 10011100 in memory

println!("x:        {:08b}", x);      // 01100100
println!("y:        {:08b}", y);      // 10011100
println!("z:        {:08b}", z);      // 10011100

// Left Shift
println!("\nLeft Shift: << 2");
println!("x result: {:08b}", x << 2); // 10010000
println!("y result: {:08b}", y << 2); // 01110000
println!("z result: {:08b}", z << 2); // 01110000

// Right Shift
println!("\nRight Shift: >> 2");
println!("x result: {:08b}", x >> 2); // 00011001
println!("y result: {:08b}", y >> 2); // 11100111
println!("z result: {:08b}", z >> 2); // 00100111

シフト演算子とオーバーフロー
シフト演算子（<<, >>）を使用する際にはオーバーフローに注意する必要があります。オーバーフローは、計算結果がそのデータ型の表現範囲を超えた場合に発生します。

Rust では、シフト演算を行う際に、シフトするビット数がデータ型のビット数以上であればコンパイルエラーが発生します。（ビット数: i8 と u8 では 8、i32 と u32 では 32）

let x: i8 = 64; // 01000000

// 左シフト 7 回
let result = x << 7; // 00000000
// 左シフト 8 回
// let result = x << 8; // `error: this arithmetic operation will overflow`

// 右シフト 7 回
let result = x >> 7; // 00000000
// 右シフト 8 回
// let result = x >> 8; // `error: this arithmetic operation will overflow`

組み込み関数

Rust では、演算子以外にもビット演算のための関数が用意されています。

let b: u8 = 0b01001100; // |0|1|0|0|1|1|0|0| in memory

// count_ones: ビット列内の 1 の数を返す（返り値の型は u32）
println!("{}", b.count_ones()); // 3
// count_zeros: ビット列内の 1 の数を返す（返り値の型は u32）
println!("{}", b.count_zeros()); // 5

// leading_zeros: ビット列の頭の 0 の数を返す（返り値の型は u32）
println!("{}", b.leading_zeros()); // 1
// trailing_zeros: ビット列の末尾のゼロの数を返す（返り値の型は u32）
println!("{}", b.trailing_zeros()); // 2

// rotate_left: 指定された桁だけ左にシフトし、
//              切り捨てられたビットを整数の末尾に折り返す
println!("{:08b}", b.rotate_left(2)); // 00110001
// rotate_right: 指定された桁だけ右にシフトし、
//               切り捨てられたビットを整数の先頭に返す
println!("{:08b}", b.rotate_right(2));  // 00010011

参考: https://doc.rust-lang.org/std/primitive.u8.html

ビット演算の実践

以下ではビット演算が使用される具体例を示します。まずは、ビット演算を実践的に使用するための基礎であるビットマスクとビットフィールドを説明し、その応用としてフラグ管理を実装をします。

ビットマスク

ビットマスクは、特定のビットを抽出したり設定したりするために使用されます。ビットマスクは通常、ビット演算子（AND、OR、NOT など）と組み合わせて使用されます。

特定のビットを抽出

let value: u8 = 0b10101010; // 2 進法で 170
let mask: u8 = 0b00001111;  // 2 進法で 15

// マスクを適用して下位 4 ビットを抽出
let masked_value = value & mask;

println!("Original value: {:08b}", value);        // 10101010
println!("Masked value  : {:08b}", masked_value); // 00001010

この例では、0b00001111 というマスクを使用して、下位 4 ビットを抽出しています。& 演算子を使用してビットごとの AND 演算を行うことで、指定したビットだけを取り出すことができます。

特定のビットを設定

let value: u8 = 0b10101010; // 2 進法で 170
let mask: u8 = 0b00001111;  // 2 進法で 15

// マスクを適用して下位 4 ビットを 1 に設定
let new_value = value | mask;

println!("Original value: {:08b}", value);     // 10101010
println!("New value     : {:08b}", new_value); // 10101111

この例では、| 演算子を使用してビットごとの OR 演算を行い、下位 4 ビットを 1 に設定しています。

特定のビットをまとめて消去

let mut value: u8 = 0b10101010; // 2 進法で 170
let mask: u8 = 0b11110101;      // 2 進法で 245

// マスクを適用して 2 番目と 4 番目のビットを消す
value &= mask; // value = value & mask

println!("Original value: {:08b}", value); // 10100000

この例では、0b11110101 というマスクを使用して、2 番目と 4 番目のビットを消しています。&= 演算子を使用してビットごとの AND 演算を行い、特定のビットを消去します。

いずれかのビットが 1 であるか判断

いずれかのビットが 1 であるかどうかを判断するには、対応するビットをマスクして 0 でないかをチェックします。これには AND 演算と比較を使用します。

let value: u8 = 0b10100000; // 2 進法で 160
let mask: u8 = 0b11000000;  // 2 進法で 192

// マスクを使用して、上位 2 ビットのいずれかのビットが 1 であるかを判断
if (value & mask) != 0 {
    println!("Some bits are set."); // この文が表示
} else {
    println!("No bits are set.");
}

この例では、0b11000000 というマスクを使用して、上位 2 ビットのいずれかのビットが 1 であるかどうかをチェックしています。& 演算子を使用してビットごとに AND 演算を行い、0 でない場合に条件が成立することを確認します。

すべてのビットが 1 であるか判断

let value: u8 = 0b11110000; // 2 進法で 240
let mask: u8 = 0b11110000;  // 2 進法で 240

// マスクを使用して、上位 4 ビットのすべてのフラグが立っているかを判断
if (value & mask) == mask {
    println!("All bits are set."); // この文が表示
} else {
    println!("Not all bits are set.");
}

この例では、0b11110000 というマスクを使用して、上位 4 ビットのすべてのビットが 1 であるかどうかをチェックしています。& 演算子を使用してビットごとに AND 演算を行い、上位 4 ビットの全てのビットが 1 である場合に条件が成立することを確認します。

ビットフィールド

ビットフィールドは、メモリの効率的な使用とデータ構造のコンパクト化を目的として、ビット列内で特定の位置から特定数のビットを取得または設定するために使用されます。

例えば、カラーコードの各成分（Red、Gleen、Blue）をビットフィールドとして扱うことができます。

RGB カラーの各成分を抽出

24 ビットの値から RGB カラーの各成分を抽出する例を示します。

let color: u32 = 0x123456; // 16 進数表でカラーコード
// 00000000 00010010 00110100 01010110 <- 32 bit のメモリを使用
//          ^^^^^^^^ ^^^^^^^^ ^^^^^^^^
//            Red     Gleen     Blue

let red = (color >> 16) & 0xFF; // 右に 16 ビットシフトして下位 8 ビットを抽出
// 00000000 00000000 00000000 11111111 <- 0xFF
// 00000000 00000000 00000000 00010010 <- 0x123456 を右に 16 ビットシフト
//                            ^^^^^^^^
//                               Red


let green = (color >> 8) & 0xFF; // 右に 8 ビットシフトして下位 8 ビットを抽出
// 00000000 00000000 00000000 11111111 <- 0xFF
// 00000000 00000000 00010010 00110100 <- 0x123456 を右に 8 ビットシフト
//                   ^^^^^^^^ ^^^^^^^^
//                     Red     Gleen

let blue = color & 0xFF; // 下位 8 ビットを抽出
// 00000000 00000000 00000000 11111111 <- 0xFF
// 00000000 00010010 00110100 01010110 <- 0x123456
//          ^^^^^^^^ ^^^^^^^^ ^^^^^^^^
//            Red     Gleen     Blue

println!("Red: {:02x}", red); // 12
println!("Green: {:02x}", green); // 34
println!("Blue: {:02x}", blue); // 56

この例では、>> 演算子を使用してビットをシフトし、各成分（赤、緑、青）を抽出しています。それぞれの成分を抽出するために、& 演算子を使用して下位 8 ビットをマスクしています。

ビットフィールドの設定

次に、ビットフィールドを使用して RGB カラーの各成分を設定する例を示します。

let red: u32 = 0x12;   // 00000000 00000000 00000000 00010010 <- 32 bit のメモリを使用
let green: u32 = 0x34; // 00000000 00000000 00000000 00110100 <- 32 bit のメモリを使用
let blue: u32 = 0x56;  // 00000000 00000000 00000000 01010110 <- 32 bit のメモリを使用

let color = (red << 16) | (green << 8) | blue;
// 00000000 00010010 00000000 00000000 <- red << 16
// 00000000 00000000 00110100 00000000 <- green << 8
// 00000000 00000000 00000000 01010110 <- blue

println!("Color: {:06x}", color); // 123456
// 00000000 00010010 00110100 01010110
//          ^^^^^^^^ ^^^^^^^^ ^^^^^^^^
//            Red     Gleen     Blue

この例では、<< 演算子を使用してビットを左にシフトし、各成分を適切な位置に配置しています。その後、| 演算子を使用して各成分を組み合わせて最終的なカラーコードを生成しています。

フラグ管理

ビットマスクとビットフィールドの応用として、フラグ管理について説明します。

ユーザの権限情報

この例では、ビットマスクを使用してユーザの権限情報を管理しています。それぞれの権限は一つのビットで表現され、ビット操作（ビット論理和 | やビット論理積 &）を使用して権限の追加、削除、チェックを行います。

ビットフラグの定義
権限を表すビットフラグを定義します。それぞれのフラグは 2 進数で 1 ビットだけが立っている数値です。

// ユーザの権限を表すビットフラグ
const PERMISSION_READ: u32 = 0b0001;  // 1
const PERMISSION_WRITE: u32 = 0b0010; // 2
const PERMISSION_DELETE: u32 = 0b0100; // 4
const PERMISSION_ADMIN: u32 = 0b1000; // 8

権限を追加する関数
ビット論理和（|=）を使って権限を追加します。

fn add_permission(permission: u32, user_permission: u32) -> u32 {
    user_permission | permission
}

権限を削除する関数
ビット論理積（&=）とビット否定（!）を使って権限を削除します。

fn remove_permission(permission: u32, user_permission: u32) -> u32 {
    user_permission & !permission
}

権限をチェックする関数
ビット論理積（&）を使って特定の権限があるかをチェックします。

fn has_permission(permission: u32, user_permission: u32) -> bool {
    (user_permission & permission) != 0
}

main 関数
初期権限を設定し、関数を使って権限を追加・削除・チェックします。

fn main() {
    let mut user_permission: u32 = PERMISSION_READ;

    println!("初期権限: {}", user_permission);
    // 初期権限: 1 (読み取りのみ)

    user_permission = add_permission(PERMISSION_WRITE, user_permission);
    println!("書き込み権限追加後: {}", user_permission);
    // 書き込み権限追加後: 3 (読み取り+書き込み)

    user_permission = add_permission(PERMISSION_DELETE, user_permission);
    println!("削除権限追加後: {}", user_permission);
    // 削除権限追加後: 7 (読み取り+書き込み+削除)

    user_permission = remove_permission(PERMISSION_WRITE, user_permission);
    println!("書き込み権限削除後: {}", user_permission);
    // 書き込み権限削除後: 5 (読み取り+削除)

    println!(
        "読み取り権限があるか: {}",
        has_permission(PERMISSION_READ, user_permission)
    );
    println!(
        "書き込み権限があるか: {}",
        has_permission(PERMISSION_WRITE, user_permission)
    );
    println!(
        "削除権限があるか: {}",
        has_permission(PERMISSION_DELETE, user_permission)
    );
    println!(
        "管理者権限があるか: {}",
        has_permission(PERMISSION_ADMIN, user_permission)
    );
}

優先度の管理

最後に、より実践的な事例である優先度の管理を実装します。この例では、複数のタスクを並列に実行する場合に、ビットマスクを使用してタスクの優先度を管理します。

実際のプロジェクト（React）で使用されているコードを参考にしています。

以下のコードでは、複数のタスクの中から最も優先度の高いタスクを取得し、タスクを順に実行するプログラムを実装します。

ビットフラグの定義
各タスクの優先度をビットフラグとして定義します。それぞれのフラグは 2 進法で 1 ビットだけが立っている数値です。最も高い優先度のタスクが PRIORITY_1 であり、最も低い優先度のタスクが PRIORITY_4 です。

// タスクの優先度をビットフラグとして定義
const PRIORITY_1: u32 = 0b0001; // 最も高い優先度
const PRIORITY_2: u32 = 0b0010;
const PRIORITY_3: u32 = 0b0100;
const PRIORITY_4: u32 = 0b1000; // 最も低い優先度

最も優先度が高いタスクの取得
以下の関数は、論理積（&）とビット否定（!）を使用して最も低い位置にある 1 ビット（最も優先度が高いタスク）を取得します。この関数を理解するのには時間がかかると思います。

// tasks != 0b0000 (tasks == 0 の場合は `!tasks + 1` は overflow するため)
// 0b0001 <= tasks <= 0b1111
fn get_highest_priority_task(tasks: u32) -> u32 {
    tasks & (!tasks + 1)
}
// `!tasks + 1` は `tasks` の 2 の補数（ビットを反転し、1 を加えた値）
// 例えば、`tasks` が 0b1010 の場合、`!tasks + 1` は 0b0110 になります。

元の数（tasks）とその数をビット反転し、1（= 0b0001）を加えた数（!tasks + 1）を比較すると、

• 元の数の右端のビットが 1 の場合は、右端のビットだけ同じ 1 をとり、それ以外は異なる数になります。
  例: 0b0101 --ビット反転--> 0b1010 --0b0001を加算--> 0b1011
• 元の数の右端のビットが 0 の場合は、右端から元の数が 1 になる最初の位置までのビットはともに 0 になり、元の数が 1 の位置はともに 1 、それ以降は異なる数になります。（1 を加えると、桁上がりにより元の数が 1 になる位置まで右端から 0 が続く、元の数が 1 の位置はビット反転をした段階で 0 なので、それ以降は 1 を加算した影響を受けない）
  例: 0b1010 --ビット反転--> 0b0101 --0b0001を加算-> 0b0110

つまり、元の数とその数をビット反転し、1 加えた数で AND 演算を行うと、元の数の最も右端の位置にある 1 以外は 0 である数を返します。

タスクの実行関数
優先度に応じて適切なタスクを実行します。この例では、優先度ごとに異なるメッセージを表示しています。

fn execute_task(task: u32) {
    match task {
        1 => println!("Executing task with priority 1"),
        2 => println!("Executing task with priority 2"),
        4 => println!("Executing task with priority 3"),
        8 => println!("Executing task with priority 4"),
        _ => println!("Unknown priority"),
    }
}

main 関数
ループを用いて、ビットフラグから最も優先度が高いタスクを取得し、実行します。実行後、ビットマスクを用いてそのタスクをビットフラグから削除します。

fn main() {
    // 複数のタスクをビットフラグとして表現
    // この例では、優先度 2 と優先度 4 のタスクが存在します。
    let mut tasks: u32 = PRIORITY_2 | PRIORITY_4; // 2 + 8 = 10 (2 進数: 1010)

    // タスクが存在する限りループ
    while tasks != 0 {
        // 最も優先度が高いタスクを取得
        let highest_priority_task = get_highest_priority_task(tasks);

        // タスクを実行
        execute_task(highest_priority_task);

        // 実行したタスクを削除
        tasks &= !highest_priority_task;
    }
}

おわりに

ビット演算は、データを効率的に管理および操作するための強力なツールです。メモリ使用量を削減したり、計算を高速化したり、データ構造をコンパクトに表現したりするなど、様々な場面で活用できます。

しかし、その特性から理解しにくい場合もあるため、コードの可読性にも十分な注意を払うことが重要です。適切にコメントを付けたり、意味のある変数名を使用することで、ビット演算を含むコードの可読性を向上させることができます。