ビット演算のイディオムに関する私的メモ

ビット演算に関するメモです。

本記事では、汎整数拡張、通常の算術変換、既定の実引数拡張（にともなう符号拡張）の話題はスコープ外としますが、Cでビット演算をする場合はそれらに気を付けてください。暗黙の型変換にともなう符号拡張の影響により、素朴な直観に反する結果となる場合があります。

#「2の補数をとる」ことのビットイメージ

基本情報技術者試験で、2の補数は「ビット反転+1」と暗記した思い出がありますが、その効果をビットイメージであらわすと

• 最右のビット1より左側にあるビットをすべて反転させる。全ビットが0のときは0を返す。（例：1010 1000 -> 0101 1000）

2の補数のビットイメージ

`^^^^`で示すビットのみが反転

    x     ->    -x
---------    ---------
1010 1000 -> 0101 1000
^^^^         ^^^^
1001 0100 -> 0110 1100
^^^^ ^       ^^^^ ^
1111 1111 -> 0000 0001
^^^^ ^^^     ^^^^ ^^^
0000 0000 -> 0000 0000

紙とペンを使って、何パターンかビット反転+1をやってみると、この効果が成立するワケが腑に落ちるかと思います。

#x+1のビットイメージ

「1の加算」は、手計算しても分かるように「最右のビット0から最下位ビットまでをビット反転する」ことに等しいです。

最右のビット0から最下位ビットまでをビット反転

    x     ->   x + 1
---------    ---------
1010 1000 -> 1010 1001
        ^            ^
1001 0111 -> 1001 1000
     ^^^^         ^^^^
0000 0000 -> 0000 0001
        ^            ^
1111 1111 -> 0000 0000
^^^^ ^^^^    ^^^^ ^^^^

#x-1のビットイメージ

「1の減算」は、手計算しても分かるように「最右のビット1から最下位ビットまでをビット反転する」ことに等しいです。

最右のビット1から最下位ビットまでをビット反転

    x     ->   x - 1
---------    ---------
1010 1000 -> 1010 0111
     ^^^^         ^^^^
1001 0111 -> 1001 0110
        ^            ^
0000 0000 -> 1111 1111
^^^^ ^^^^    ^^^^ ^^^^
1111 1111 -> 1111 1110
        ^            ^

#「-~x」が「x+1」、「~-x」が「x-1」に等しい理由

Nビットにおける「xのビット反転（1の補数）」を数式で表現すると、以下に等しいです。

2^N - 1 - x

Nビットにおける「xの2の補数」を数式で表現すると、以下に等しいです。

2^N - x

以上をふまえると-~xは

\begin{align}
2^N - (2^N - 1 - x)&= 2^N - 2^N + 1 + x\\ &= x + 1
\end{align}

同様に~-xは

\begin{align}
2^N - 1 - (2^N - x)&= 2^N - 1 - 2^N + x\\ &= x - 1
\end{align}

#ビット演算イディオム集

この性質を利用して、いくつかイディオムを作ってみました（以下表）。

個人的には、-(-x｜~x)が「最右のビット1を最下位ビットに移動する」のが、ビットの動きがあって面白いなーと思いました。

最右のビット1を最下位ビットに移動

    x     -> -(-x|~x)
---------    ---------
1000 1000 -> 1000 0001
     ^               ^

#	式	説明	例
1	x^x	定数0を返す。	1010 1011 -> 0000 0000
2	-~(x^x)	定数1を返す。	1010 1011 -> 0000 0001
3	~x｜x ~(x^x) x ^ ~x	全ビット1を返す。	1010 1011 -> 1111 1111
4	-~x	x + 1を返す。	1010 1011 -> 1010 1100
5	~-x	x - 1を返す。	1010 1100 -> 1010 1011
6	-(-x｜~x)	最右の1を、最下位ビットに移動。 ・x=0のとき1を返す。	1010 1000 -> 1010 0001
7	~(x｜-x)	末尾の連続する0を保存するマスクを作成。 ・x=0のときすべてのビットが1となる。 ・xの最下位ビットが1のとき0を返す。	1010 1000 -> 0000 0111
8	x ^ (x & -~x)	末尾の連続する1を保存するマスクを作成。 ・xの最下位ビットが0のとき0を返す。	0100 1111 -> 0000 1111
9	x ^ (~-x)	最右の1と末尾の連続する0を保存するマスクを作成。 ・x=0のときすべてのビットが1となる。 xの最下位ビットが1のとき1を返す。	1010 1000 -> 0000 1111
10	x ^ (-~x)	最右の0と末尾の連続する1を保存するマスクを作成。 ・全ビットが1のときxを返す。	0101 0111 -> 0000 1111
11	-(x&-x)	最上位ビット～最右の1までを保存するマスクを作成。 ・x=0のとき0を返す。	0110 1000 -> 1111 1000
12	x & -x	最右の1をピックアップするマスクを作成。 ・x=0のとき0を返す。	1010 1000 -> 0000 1000
13	~x & (-~x)	最右の0をピックアップするマスクを作成。 ・全ビットが1のとき0を返す。	0100 1011 -> 0000 0100
14	x ^ (-~(x｜~-x) & x)	最右の連続する1を保存するマスクを作成。 ・x=0のとき0を返す。	0100 1110 -> 0000 1110
15	x ^ (~-(x｜-~x)｜x)	最右の連続する0を保存するマスクを作成。 ・全ビットが1のとき0を返す。	0100 0011 -> 0011 1100
16	~(-x｜~x) x & ~-x	最右の1を0にする。 ・x=0のとき0を返す。	1010 1000 -> 1010 0000
17	x ｜ -~x	最右の0を1にする。 ・全ビットが1のときxを返す。	1010 0111 -> 1010 1111
18	-x & ~x	「末尾の連続する0」以外のビットをすべて反転する。 ・最下位ビットが1のとき全ビットを反転	1010 1000 -> 0101 0000
19	x & -~x	末尾の連続する1を0にする。 ・xの最下位ビットが0のときxを返す。	0100 1111 -> 0100 0000
20	x ｜ ~-x	末尾の連続する0を1にする。 ・最下位ビットが1のときxを返す。	0100 1000 -> 0100 1111
21	-~(x｜~-x) & x	最右の連続する1を0にする。 ・x=0のとき0を返す。	0100 1110 -> 0100 0000
22	~-(x｜-~x)｜x	最右の連続する0を1にする。 ・全ビットが1のときxを返す。	0101 0011 -> 0101 1111

#【参考1】ビットダンプ関数

bit_dump(C99)

#include <stdio.h>
#include <limits.h>

void bit_dump(unsigned char x)
{
    for(size_t pos = sizeof(x) * CHAR_BIT; pos--;)
        printf("%d", !!(x & 1<<pos));
}

#【参考2】ビット演算の演算子の優先順位

優先順位	演算子	結合性
1	単項+、単項-、~、!	右結合
2	<<、>>	左結合
3	&	左結合
4	^	左結合
5	｜	左結合
6	&&	左結合
7	｜｜	左結合

#【参考3】参考文献

• 「ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか」