Zenn
☝️

ビット演算テクニック集

2024/03/10に公開
C++
競技プログラミング
競プロ
tech

競技プログラミングで使えそうなビット演算のテクニックを書いていきます。
思いついたら追記していく予定です。
この記事で用いるコードの言語はC++ですが、言語特有のテクニックを用いることは殆どないです。
慣れていない場合は、論理演算子とビット演算子を混同しないようにだけ注意してください。

Bit Twiddling Hacks というサイトをかなり参考にしています。
ここに書いていないようなビット演算のテクニックが載っているので一度覗いてみると面白いと思います。

バグや間違いを見つけた場合や他の面白い実装方法を思いついた場合など、コメントをしていただけると嬉しいです。

ビット演算の基礎

ここでは、二進数で表した際の一番最初の桁を 0 桁目としています。
コードの bit に集合 S が、 MASK に集合 M が対応しています。

説明 コード 集合
bit の i 桁目が 1 かどうか bool((bit >> i) & 1) または bool(bit & (1 << i)) i \in S かどうか
bit の i 桁目を 1 にした値 bit | (1 << i) S \cup \{i\}
bit の i 桁目を 0 にした値 bit & ~(1 << i) S \setminus \{i\}
[0, i) 桁目が 1 である値 (1 << i) - 1 \{0, 1, \cdots, i-1\}
[i, j) 桁目が 1 である値 (1 << j) - (1 << i) \{i, i+1, \cdots, j-1\}
bit の MASK 部分のいずれかが 1 かどうか bool(bit & MASK) S \cap M \neq \emptyset かどうか
bit の MASK 部分の全てが 1 かどうか (bit & MASK) == MASK または (~bit & MASK) == 0 M \subseteq S かどうか
bit の MASK 部分を 1 にした値 bit | MASK S \cup M
bit の MASK 部分を 0 にした値 bit & ~MASK S \setminus M

特に説明はしませんが、まったく分からない方でも自分で例を作って試せば十分理解できると思います。
また、ここに書かれている方法は、私が良く見る実装だけを書いています。この他にも実装の仕方は色々ありますので、考えてみると楽しいかもしれないです。

ビット列に関するテクニック

1 になっているビットの個数

10011 のようなビット列であれば 3 となります。
いわゆる popcount です。

bit = (bit & 0x55555555) + ((bit >> 1) & 0x55555555);
bit = (bit & 0x33333333) + ((bit >> 2) & 0x33333333);
bit = (bit & 0x0f0f0f0f) + ((bit >> 4) & 0x0f0f0f0f);
bit = (bit & 0x00ff00ff) + ((bit >> 8) & 0x00ff00ff);
bit = (bit & 0x0000ffff) + ((bit >> 16) & 0x0000ffff);

上記のコードは 32bit の場合です。
例えば 8bit の値 11010001 で動きを確認してみます。
上記のコードでは16進数で書いているのに対して、下記のコードは2進数で書いていることに注意してください。

コード bit
初期値 11010001_{(2)}
bit = (bit & 0b01010101) + ((bit >> 1) & 0b01010101) 10010001_{(2)}
bit = (bit & 0b00110011) + ((bit >> 2) & 0b00110011) 00110001_{(2)}
bit = (bit & 0b00001111) + ((bit >> 4) & 0b00001111) 00000100_{(2)} = 4_{(10)}

このように、隣り合う 1, 2, 4, \cdots ビット同士で足す、というように分割統治法を行うことで目的の値を得ることができます。
以下のような再帰関数と同じことを、同じ深さの場所に対して並列で行っているのが、上記のアルゴリズムです。

int popcount(int bit, int size = 32) {
    if (size == 1) return bit & 1;
    size /= 2;
    int mask = (1 << size) - 1;
    int cntl = popcount((bit >> size) & mask, size);
    int cntr = popcount(bit & mask, size);
    return cntl + cntr;
}

C++20 からは popcount という関数があるので、これを用いれば良いと思います。

1 になっているビットの偶奇

先ほどの popcount を 2 で割ったあまりです。
popcount が求められるなら、特に下記のコードを書く理由はないと思います。

bit ^= bit >> 16;
bit ^= bit >> 8;
bit ^= bit >> 4;
bit ^= bit >> 2;
bit ^= bit >> 1;
bit &= 1;

上記のコードは 32bit の場合です。
これは i 桁目を a_i \in \{0, 1\} と置いて操作を追うと、最初のビットが a_0 \oplus a_1 \oplus \cdots \oplus a_n となることが簡単にわかると思います。

ビットの並びの反転

10110 のようなビット列であれば 01101 となります。

bit = ((bit & 0x55555555) << 1) | ((bit >> 1) & 0x55555555);
bit = ((bit & 0x33333333) << 2) | ((bit >> 2) & 0x33333333);
bit = ((bit & 0x0f0f0f0f) << 4) | ((bit >> 4) & 0x0f0f0f0f);
bit = ((bit & 0x00ff00ff) << 8) | ((bit >> 8) & 0x00ff00ff);
bit = (bit << 16) | (bit >> 16);

上記のコードは 32bit の場合です。
これは popcount で見たような、分割統治法を並列化したアルゴリズムです。
文字列の並びを反転させる関数 rev(S) が、文字列 S, T に対して rev(S+T) = rev(T) + rev(S) を満たすため、上記のアルゴリズムは成立します。

最も右にある 1 のみにした値

10100 のようなビット列であれば 00100 となります。
元の値を割り切る最大の 2 の冪乗の数、と言い換えることもできます。

bit & -bit

2の補数表現において、ある値とその値の符号を反転させた値を二進数の計算で足したときに、溢れたビットを除いて全て 0 になるように負の値を定めていることを考えると、理解できるかと思います。
あるいは -bit が ~bit + 1 に等しい、と言い換えた方が分かりやすいかもしれません。

最も左にある 1 のみにした値

01011 のようなビット列であれば 01000 となります。
元の値以下の最大の 2 の冪乗の数、と言い換えることもできます。

bit |= bit >> 1;
bit |= bit >> 2;
bit |= bit >> 4;
bit |= bit >> 8;
bit |= bit >> 16;
bit ^= bit >> 1;

上記のコードは 32bit の場合です。
例えば 8bit の値 01000011 で動きを確認してみます。

コード bit
初期値 01000011_{(2)}
bit |= bit >> 1 01100011_{(2)}
bit |= bit >> 2 01111011_{(2)}
bit |= bit >> 4 01111111_{(2)}
bit ^= bit >> 1 01000000_{(2)}

このように、右側を全て 1 にした値を作ることで、目的の値を簡単に得ることができます。

最も右にある 1 の位置

10100 のようなビット列であれば 2 となります(0 から始まることに注意してください)。
右から連続している 0 の数、と言い換えることもできます。

かなり説明が面倒なので、書く気力が起きたら追記しておきます。
de Bruijn sequence を利用します。
もちろん二分探索でも実装はできますが、条件分岐がない分 de Bruijn sequence を用いる方が高速です。

とりあえず、以下の実装を参考にすればよいと思います。
https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightMultLookup

C++20 から countr_zero という関数があるので、これを用いれば良いと思います。

最も左にある 1 の位置

01011 のようなビット列であれば 3 となります。

上と同様に、書く気力が起きたら追記しておきます。
最も右にある 1 の位置が取得できれば、左も簡単に取得できます。

C++20 から countl_zero という関数があるので、これとビット数から計算することができます。

集合の走査

部分集合を走査

いわゆる bit 全探索です。
集合 S = \{0, 1, \cdots, n-1\} の部分集合全てを走査するアルゴリズムです。

int n = 10;

for (int bit = 0; bit < (1 << n); ++bit) {
    // Todo: 集合 bit を使った処理を書く
}

集合 S の部分集合の個数が 2^n であり、 1 << n が 2^n であることからも明らかです。
計算量は O(2^n) です。

ある部分集合の部分集合を走査

集合 S = \{0, 1, \cdots, n-1\} の部分集合 T が与えられたときに、集合 T の部分集合全てを走査するアルゴリズムです。
蟻本の 3-2 の COLUMN に載っています。

int n = 10;
int subset = 0b1011010100;

for (int bit = subset; bit >= 0; --bit) {
    bit &= subset;
    
    // Todo: 集合 bit を使った処理を書く
}

--bit と bit &= subset が肝です。
これらの操作で bit が狭義単調減少になっていることは明らかなので、この走査に被りがないことが分かります。
bit から 1 を引くと、最も右の 1 になっているビットが 0 になり、それよりも右のビットが全て 1 になります。これに subset でマスクをとることで、不要な走査をせず、漏れなく走査することができます。

計算量は O(2^{|T|}) です。

この操作を集合 S = \{0, 1, \cdots, n-1\} の全ての部分集合に対して行うと、計算量は O(3^n) になります。
これは \sum_{i=0}^{n} \binom{n}{i} 2^i = (1+2)^n = 3^n であることから導かれます。
具体的なコードは以下の通りです。

int n = 10;

for (int subset = 0; subset < (1 << n); ++subset) {
    for (int bit = subset; bit >= 0; --bit) {
        bit &= subset;
	
        // Todo: 集合 bit を使った処理を書く
    }
}

ある部分集合を包含する部分集合を走査

集合 S = \{0, 1, \cdots, n-1\} の部分集合 T が与えられたときに、集合 T を部分集合として持つ全ての集合を走査するアルゴリズムです。

int n = 10;
int subset = 0b1011010100;

for (int bit = subset; bit < (1 << n); bit = (bit + 1) | subset) {
    // Todo: 集合 bit を使った処理を書く
}

計算量は O(2^{n-|T|}) です。

考え方は先ほどのアルゴリズムと殆ど同じです。

要素数 k の部分集合を走査

集合 S = \{0, 1, \cdots, n-1\} の部分集合の中で、要素数が k であるもの全てを走査するアルゴリズムです。
これも蟻本に載っています。

int x, y;
for (int bit = (1 << k) - 1; bit < (1 << n);
     x = bit & -bit, y = bit + x, bit = (((bit & ~y) / x) >> 1) | y) {
    // Todo: 集合 bit を使った処理を書く
}

これは、二進数において昇順となるように目的の部分集合を走査するアルゴリズムです。
簡単なアルゴリズムから改善していく形で説明を書こうと思ったのですが、かなり長くなってしまったため、それぞれの操作が何をするのかを簡単に列挙するだけにしておきます。

  1. bit = (1 << k) - 1 : popcount が k となる最小の値
  2. x = bit & -bit : 最も右にある 1 のみにした値 (01101110_{(2)} \rightarrow 00000010_{(2)})
  3. y = bit + x : bit に対する足し算において、繰り上がりが発生する最小の値 (01101110_{(2)} \rightarrow 01110000_{(2)})
  4. bit & ~y : 最も右にある"連続した" 1 の部分のみを取り出した値 (01101110_{(2)} \rightarrow 00001110_{(2)})
  5. (bit & ~y) / x : 右の 0 が無くなるように右シフトした値 (00001110_{(2)} \rightarrow 00000111_{(2)})
  6. (((bit & ~y) / x) >> 1) : 上記からもう一つ右シフトした値 (00000111_{(2)} \rightarrow 00000011_{(2)})
  7. bit = (((bit & ~y) / x) >> 1) | y : popcount が k となるような辞書順で次の値 (01101110_{(2)} \rightarrow 01110011_{(2)})

popcount を k より大きくしない方法を考えてから k より小さくしない方法を考えると、上記のアルゴリズムが思いつきやすくなるかと思います。

計算量は O({}_n\mathrm{C}_k) です。

Discussion