ビット演算の様々な使い方

はじめに

競技プログラミング等で役に立つかもしれない、ビット演算の様々なテクニックを紹介します。
また、この記事で用いるコードの言語は C++ ですが、言語特有のテクニックを用いることはしません。
適宜、慣れている言語に置き換えてください。

ただし、この記事では論理演算子やビット演算子そのものについては知っているものとし、説明はしません。

ビット演算の基礎

様々なテクニックを紹介する前に、基礎的なビット演算の処理について軽く列挙しておきます。

以下の表では、集合とビット列を対応させて説明しています。
例えば $\{4, 3, 2, 1, 0\}$ の整数を全体集合とするとき、集合 $\{3, 1, 0\}$ はビット列 $01011$ に対応します。

また、最下位ビットを $0$ 桁目としています。
そして、コードの変数 bit と集合 $S$ が、コードの変数 mask と集合 $M$ が対応しています。

簡易な説明	コード	集合
bit の $i$ 桁目が $1$ かどうか	((bit >> i) & 1) != 0 または (bit & (1 << i)) != 0	$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$ かどうか	(bit & mask) != 0	$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, 2^N$ ビット同士で足す、というように分割統治法と似たことを行うことで目的の値を得ることができます。
つまり、以下のような再帰関数と同じことを、同じ深さの場所に対して並列で行っているのが、上記のアルゴリズムです。

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;
}

多くの言語では 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$ となることが分かります。

ここでの $\oplus$ は xor を意味しています。

なので 8bit の場合で動きを追ってみます。

コード	$7, 6, 5, 4$ 桁目	$3$ 桁目	$2$ 桁目	$1$ 桁目	$0$ 桁目
初期値	$a_7, a_6, a_5, a_4$	$a_3$	$a_2$	$a_1$	$a_0$
bit ^= bit >> 4	-	$a_7 \oplus a_3$	$a_6 \oplus a_2$	$a_5 \oplus a_1$	$a_4 \oplus a_0$
bit ^= bit >> 2	-	-	-	$$\bigoplus_{i=0}^{3} a_{2i+1}$$	$$\bigoplus_{i=0}^{3} a_{2i}$$
bit ^= bit >> 1	-	-	-	-	$$\bigoplus_{i=0}^{7} a_i$$

感覚的には、紙を半分に切って重ねる(重なっている場所で演算をする)といった感じです。

ビットの並びの反転

これは 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の補数表現において、ある値とその値の符号を反転させた値を 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 にした値を作ることで、目的の値を簡単に得ることができます。

集合の走査

部分集合を走査

いわゆる 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} {}_n\mathrm{C}_i 2^i = (2+1)^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$ を部分集合として持つ全ての $S$ の部分集合を走査するアルゴリズムです。

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 を使った処理を書く
}

これは、2 進数において昇順となるように目的の部分集合を走査するアルゴリズムです。
しっかり説明を書くと、それだけで一つの記事になりそうだったので、それぞれの操作が何を意味するのかを簡単に書いておきます。

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

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

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

おわりに

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

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