アルゴリズムの効率性を最大化するためのビット演算の体系的な解説。状態圧縮やマスク操作、空間複雑度O(1)の最適化手法を、大手企業の実際問題を通じて学習します。

一、ビット演算子の基本操作

二、代表的な6つの応用パターン

パターン1：偶奇判定

bool isEven(int value) {
    return (value & 1) == 0;
}

パターン2：3変数不要の交換処理

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

パターン3：セットビットカウント

int countSetBits(uint32_t num) {
    int total = 0;
    while (num) {
        num &= num - 1;
        total++;
    }
    return total;
}

パターン4：Nクイーン問題の最適化

int solveNQueens(int size) {
    int result = 0;
    auto traverse = [&](int row, int col_mask, int diag1, int diag2) {
        if (row == size) {
            result++;
            return;
        }
        int available = (~ (col_mask | diag1 | diag2)) & ((1 << size) - 1);
        while (available) {
            int position = available & -available;
            traverse(row+1, col_mask | position, (diag1 | position) << 1, (diag2 | position) >> 1);
            available &= available - 1;
        }
    };
    traverse(0, 0, 0, 0);
    return result;
}

パターン5：高速べき乗計算

long long powerMod(long long base, int exponent, int modulus) {
    long long outcome = 1;
    while (exponent) {
        if (exponent & 1) outcome = (outcome * base) % modulus;
        base = (base * base) % modulus;
        exponent >>= 1;
    }
    return outcome;
}

パターン6：重複要素の検出

int findUniqueElement(vector<int>& elements) {
    int unique = 0;
    for (int val : elements) unique ^= val;
    return unique;
}

三、実際問題への応用

問題1：バイナリ加算

string binarySum(string a, string b) {
    int i = a.length()-1, j = b.length()-1, carry = 0;
    string sum;
    while (i >= 0 || j >= 0 || carry) {
        int total = carry;
        if (i >= 0) total += a[i--] - '0';
        if (j >= 0) total += b[j--] - '0';
        sum.push_back((total & 1) + '0');
        carry = total >> 1;
    }
    reverse(sum.begin(), sum.end());
    return sum;
}

問題2：サブセット生成

vector<vector<int>> generateSubsets(vector<int>& data) {
    int n = data.size();
    vector<vector<int>> all_subsets;
    for (int pattern = 0; pattern < (1 << n); ++pattern) {
        vector<int> current;
        for (int k = 0; k < n; ++k) {
            if (pattern & (1 << k)) current.push_back(data[k]);
        }
        all_subsets.push_back(current);
    }
    return all_subsets;
}

四、最適化手法

五、注意事項

1. 演算子優先順位 if (n & 1 == 0) → if ((n & 1) == 0) と修正が必要

2. シフトオーバーフロー 1 << 32 は32bitシステムで未定義

3. 符号拡張 符号付き型の右シフトは予期しない結果を生じる

4. 型変換の落とし穴 ~0 はchar型では-1になる

5. 無限ループ 負数の右シフトは無限ループに陥る可能性あり

六、関連トピック

性能向上効果：

• 定数時間操作の実現
• パラレルビット処理の活用
• 状態圧縮によるメモリ最適化

進階課題：

1. 浮動小数点数のビット演算応用
2. ブロムフィルタの設計
3. 暗号理論における応用例

練習問題：

• 191. 1のビット数
• 231. 2の累乗
• 371. 二整数和