ビット演算の基本と応用

ビット演算とシフト演算は、コンピュータの基本的な操作であり、バイナリレベルでのデータ操作を可能にします。アルゴリズム競技において、これらの操作は特定のタスクを効率的に実行するための強力なツールとなります。その特性と応用例を理解することは、競技プログラミングにおいて非常に重要です。

1. 演算子の優先順位

C++における演算子の優先順位は、式の評価順序を決定します。ビット演算子の優先順位を正しく理解し、適切な括弧の使用を心がける必要があります。一般的な優先順位は以下の通りです（高い順）。

1. 単項演算子（~, !）
2. 乗算・除算（*, /）
3. 加算・減算（+, -）
4. シフト演算子（<<, >>）
5. 比較演算子（==, !=）
6. ビットAND（&）
7. ビットOR（|）
8. 論理AND（&&）
9. 論理OR（||）

2. シフト演算子: << と >>

2.1 演算規則

シフト演算子は、数値のバイナリ表現を指定されたビット数だけ左または右に移動させます。空いたビットは0で埋められ、溢れたビットは破棄されます。

int a = 1;      // 0001
int b = a << 2;  // 0100 (1 * 2^2 = 4)
int c = 8;      // 1000
int d = c >> 1;  // 0100 (8 / 2^1 = 4)

2.2 応用: 2のべき乗の高速計算

左シフト演算は、数学的には2のべき乗への乗算に相当します。この特性を利用して、2のべき乗を高速に計算できます。

// 2の5乗を計算する
int power_of_two = 1 << 5; // 32

3. ビットAND: &

3.1 演算規則

ビットANDは、両方のオペランドの対応するビットが1の場合にのみ1を返します。

1 & 1 == 1
1 & 0 == 0
0 & 0 == 0

3.2 応用1: 2のべき乗の判定

ある数が2のべき乗であるかどうかを判定するには、その数と自身より1小さい数をAND演算し、結果が0になるか確認します。

bool is_power_of_two(int num) {
    // 2のべき乗の数は、その数-1とのANDが必ず0になる
    return (num & (num - 1)) == 0;
}

// 例
// 8 (1000) & 7 (0111) = 0
// 6 (0110) & 5 (0101) = 4 (0100) != 0

3.3 応用2: 1のビット数のカウント

数値のバイナリ表現に含まれる1のビット数を数えるための効率的な方法です。数値と自身より1小さい数をAND演算すると、最も右側の1のビットが消え、カウントを進めます。

int count_set_bits(int number) {
    int count = 0;
    while (number) {
        number &= (number - 1); // 最も右の1ビットをクリア
        count++;
    }
    return count;
}

// 例: 13 (1101) の1のビット数を数える
// 1回目: 1101 & 1100 = 1100 (count=1)
// 2回目: 1100 & 1011 = 1000 (count=2)
// 3回目: 1000 & 0111 = 0000 (count=3)

4. ビットOR: |

4.1 演算規則

ビットORは、少なくとも一方のオペランドの対応するビットが1の場合に1を返します。

1 | 1 == 1
1 | 0 == 1
0 | 0 == 0

5. ビットXOR: ^

5.1 演算規則

ビットXORは、オペランドの対応するビットが異なる場合に1を返します。

0 ^ 0 == 0
1 ^ 1 == 0
1 ^ 0 == 1

5.2 応用: 二つの数値の交換 (swap)

XOR演算を利用して、追加の変数を使わずに二つの数値を交換できます。

void swap_using_xor(int &x, int &y) {
    x ^= y; // x = x ^ y
    y ^= x; // y = y ^ (x ^ y) = x
    x ^= y; // x = (x ^ y) ^ x = y
}

// 使用例
int p = 10, q = 20;
swap_using_xor(p, q);
// p は 20, q は 10 になる