C++プログラマへの道 #24 - ビット操作

C++DSA

Last Edited: 2/1/2025

このブログ記事では、C++におけるビット操作を紹介します。

CPP Bit

結局のところ、すべてのデータはバイナリで表現されます。例えば、符号なし整数は4バイトまたは16ビットで表現できます。 そのため、ビットを直接操作することは一般的に高速です。本記事では、ビットを直接操作できるビット演算子について説明し、 これらの演算子がコードの高速化に役立つ場合を紹介します。

ビットシフト演算子

ビットを左右にシフトできるビットシフト演算子というものがあります。 例えば、左シフト演算子は0101を1010に、右シフト演算子は0101を0010にシフトできます。 符号なし整数の場合、各ビットは右から左に向かって1から始まる2の累乗を表すため、 ビットシフト演算子は2n2^n倍や2n2^nでの整数除算をnn回のシフトで実現できます。

int a = 5; // 0101
int b = a << 2; // 10100 = b = 5 * 2^2 = 20
int c = a >> 1; // => 0010 = c = 5 // 2*1 = 2

上記の例では、左シフト演算子<<と右シフト演算子>>を整数5に適用し、それぞれ2回と1回のシフトを行っています。 述べたように、左へnn回シフトすることは2n2^n倍すること、右へnn回シフトすることは 2n2^n で割ることに相当します。 ビットシフト演算子を使って2の倍数の乗算・除算を行うと高速化できることが多いですが、 コンパイラがコードをアセンブリにコンパイルする際、自動的に最適化を適用する場合もあります。 そのため、通常はb = a * 2を使うほうがb = a << 2よりも可読性の観点において良いです。

ビット論理演算子

ビット論理演算子には、AND(&)、OR(|)、XOR(^)、NOT(~)の4種類があります。 これらの演算子は、2つの数値の各ビットに対して個別に論理演算を適用します。 以下のコードは、ビット論理演算子がどのように動作するかを示しています。

int a = 5; // 0101
int b = 6; // 0110
 
// AND
int c = a & b; // => 0100 = 4
 
// OR
int d = a | b; // => 0111 = 7
 
// XOR
int e = a ^ b; // => 0011 = 3
 
// NOT
int f = ~a; // => 1010 = 10

AND 演算子は、対応するビットが両方とも1の場合のみ1を出力し、 OR 演算子は、どちらかのビットが1であれば1を出力します。 XOR 演算子は、2つのビットが異なる場合に1を出力し、 NOT 演算子はビットを反転させます。

実際の使用例

ビット演算は多くの場面で役に立つわけではありませんが、適切に使えば大幅な性能向上につながることがあります。 例えば、ある文字列の中から10文字の異なる文字の並びを見つける問題を考えます。 まず、ビット演算を使わずに、この問題を解く最も直感的な方法は、 ハッシュセット（またはunordered_set）を使うことです。 文字列を走査し、セットに10個の文字を追加しながら、そのセットの要素数を確認することで、 10文字の異なる文字が並んだ箇所を検出できます

int hash_approach(vector<char> input) {
    int index = 0;
    
    while (index != input.size() - 10) {
        unordered_set<char> set;
        for (int i = index; i < index + 10; i++) {
            set.insert(input[i]);
        }
        if (set.size() == 10) {
            return index + 10;
        }
        index++;
    }
    return EXIT_FAILURE;
};
 
int main () {
    char chars[18] = {'a','s','o','i','q','l','m','o','v','c','p','z','x','y','h','j','n','m'};
    vector<char> input(chars, chars + sizeof(chars) / sizeof(chars[0]));
 
    auto start = std::chrono::high_resolution_clock::now();
    int result = hash_approach(input);
    auto end = std::chrono::high_resolution_clock::now();
    cout << "Result: " << result << endl; // => Result: 13
    std::chrono::duration<double> duration = end - start;
    cout << "Time: " << duration.count() << " seconds" << endl; 
    // => Time: 3.3875e-05 seconds (in my config)
 
    return 0;
};

ハッシュセットは重複を排除するため、10個の異なる文字が揃った時点で終了できます。 この方法をchrono標準ライブラリを使って測定したところ、実行時間は3.39×10−53.39 \times 10^{-5}秒でした。 ハッシュセットの検索はO(1)O(1)なので、このアルゴリズムの時間計算量はO(n)O(n)です。 代わりに、ユニークな文字を格納する手段としてvectorを使用することもできます。

int vector_approach(vector<char> input) {
    int index = 0;
    
    while (index != input.size() - 10) {
        vector<char> vec;
        for (int i = index; i < index + 10; i++) {
            if (find(vec.begin(), vec.end(), input[i]) == vec.end()) {
                vec.push_back(input[i]);
            }
        }
        if (vec.size() == 10) {
            return index + 10;
        }
        index++;
    }
    return EXIT_FAILURE;
};

理論的にはvectorの検索はO(n)O(n)であり、O(1)O(1)のハッシュセットよりも遅いはずです。 しかし、時間計算量は入力サイズが増加した場合のスケーリングを示すものであり、 この場合のウィンドウサイズは固定なので、検索は定数時間で行えます。 実際、vectorを使用した実装はunordered_setよりも高速で、2.58×10−52.58 \times 10^{-5}秒という結果になりました。 この例は、時間計算量が常に実際のパフォーマンスを決定するわけではないことを示しています。

最後に、ビット演算を使ってこの問題を効率的に解く方法を考えます。 aからzまでの文字は ASCIIコードで97～122にマッピングされています。 この範囲を32で割った余りを取ることで、0 ～ 31の範囲の整数に変換できます。 この整数を1を左シフトすることで、特定のビットのみが1であるバイナリ表現を作成できます。

Bit Approach

10個の文字に対してXORを適用（ユニークな値を抽出）し、 1の数を数えることで、異なる文字の数を取得できます。 もし1の数がちょうど10であれば、現在のインデックスを返します。 そうでなければ、ウィンドウの末尾の文字に対応するビットをXORで反転させ、 新しい文字のビットをXORで追加します。 この処理を繰り返すことで、10個の異なる文字を検出できます。

int bit_approach(std::vector<char> input) {
    int filter = 0;
 
    for (int i = 0; i < 9; ++i) {
        filter ^= 1 << (input[i] % 32);
    }
 
    for (int i = 10; i < input.size(); ++i) {
        filter ^= 1 << (input[i] % 32);
        if (std::bitset<32>(filter).count() == 10) {
            return i + 1;
        }
        filter ^= 1 << (input[i - 9] % 32);
    }
 
    return EXIT_FAILURE;
};

vectorやunordered_setを使って文字を管理する代わりに、 整数1つを使ってバイナリとして扱うことができます。 1の個数は、整数をbitset<32>にキャストし、count()メソッドを使えば求められます。 この手法では実行時間が1.042×10−61.042 \times 10^{-6}秒となり、 従来の2つの方法よりも約30倍高速になりました。 （通常、アルゴリズムのベンチマークでは、さまざまな入力に対して複数回実行して比較します。） この例は、ビット演算を適切に活用することでパフォーマンスを大幅に向上できることを示していますが、 ビット操作を採用すべきかどうかは問題の文脈によります。

結論

本記事では、ビットシフト演算子、ビット論理演算子、およびビット演算の実用例を紹介しました。 繰り返しになりますが、ビット演算の適用はトレードオフを考慮しながら判断することが重要です。

リソース

TOPに戻る↑