Python ビット演算 超入門

2進数に対して行うビット演算の初歩を説明します。説明にはPythonを使用します。

2進数

0bを付けて記述します。REPLで入力すると10進数に変換されます。

>>> 0b101
5

2進数に変換するにはbin()を使います。

>>> bin(5)
'0b101'

16進数

元の数値を16進数で記述すれば、16進数から2進数に変換できます。

>>> bin(0x12)
'0b10010'

16進数に変換するにはhex()を使います。

>>> hex(0b10010)
'0x12'

シフト

桁をずらします。方向により左シフトと右シフトがあります。

左シフト

演算子<<です。指定した桁だけ左にずらして、空いたビットには0が入ります。

右揃えに整形して例を示します。

入力	出力
bin(5<<0)	'0b101'
bin(5<<1)	'0b1010'
bin(5<<2)	'0b10100'
bin(5<<3)	'0b101000'

右シフト

演算子>>です。指定した桁だけ右にずらして、最下位より先に押し出されたビットは消えます。

右揃えに整形して例を示します。

入力	出力
bin(5>>0)	'0b101'
bin(5>>1)	'0b10'
bin(5>>2)	'0b1'
bin(5>>3)	'0b0'

論理演算

2進数の各桁に対する計算です。

基本的な考え方は真偽値による処理で、1を真、0を偽と見なします。

論理積 (AND)

演算子&です。両方が真(1)のときにしか成立(1)しません。1桁だけ見れば掛け算と同じです。

AND	掛け算	結果
0 & 0	0 * 0	0
0 & 1	0 * 1	0
1 & 0	1 * 0	0
1 & 1	1 * 1	1

複数桁では繰り上がりを一切考えずに、桁ごとに独立して掛け算します。

   10010010
&) 10100111
-----------
   10000010

Pythonで確認します。

>>> bin(0b10010010 & 0b10100111)
'0b10000010'

論理和 (OR)

演算子|です。どちらかが真(1)であれば成立(1)します。1桁だけ見れば足し算に似ていますが、計算結果の1以上はすべて1として扱います（2→1）。

OR	足し算	結果
0 | 0	0 + 0	0
0 | 1	0 + 1	1
1 | 0	1 + 0	1
1 | 1	1 + 1	2→1

複数桁では繰り上がりを一切考えずに、桁ごとに独立して足し算します。計算結果の1以上はすべて1として扱います（2→1）。

   10010010
|) 10100111
-----------
   10110111

Pythonで確認します。

>>> bin(0b10010010 | 0b10100111)
'0b10110111'

排他的論理和 (XOR)

演算子^です。片方だけが真(1)であれば成立(1)します（両立しない点が排他的）。2進数1桁だけ見れば繰り上りを捨てる足し算です（1+1=2=0b10 → 0）。

XOR	足し算	結果
0 ^ 0	0 + 0	0
0 ^ 1	0 + 1	1
1 ^ 0	1 + 0	1
1 ^ 1	1 + 1	2→0

複数桁では繰り上がりを一切考えずに、桁ごとに独立して足し算します。

   10010010
^) 10100111
-----------
   00110101

Pythonで確認します。

>>> bin(0b10010010 ^ 0b10100111)
'0b110101'

同じ値で2回XORすると元の値に戻るという性質があります。

• a ^ b ^ b → a

>>> bin(0b10010010 ^ 0b10100111 ^ 0b10100111)
'0b10010010'

元の値を消すこともできます。

• a ^ b ^ a → b

>>> bin(0b10010010 ^ 0b10100111 ^ 0b10010010)
'0b10100111'

反転 (NOT)

演算子~です。0と1を逆にします。

Pythonでは上の桁が無限に0で埋められていると見なして、反転も上の桁が無限に1で埋められているという想定でマイナスを返します。

>>> ~1
-2

この計算は 000...0001 → 111...1110 を意味しています。

後でANDとNOTの組み合わせで見るように、通常はビットだけに注目して具体的な数値（ここではマイナス）は意識しません。符号の考え方について興味がある方は次の記事を参照してください。

• @7shi: 符号あり数値の直感的な考え方 2014.10.8

値だけに注目して ~x→-(x+1) という式が紹介されることもあります。補数表現の流儀に関係がありますが、ここでは深く追求しません。

使用例

ビット演算は一部のビットだけを取り出すときなどによく使われます。

ビットマスク

ビットのうち必要な部分だけを取り出すとき、必要な部分だけを1にした数とANDします。

例: 101110から下位3ビット（太字の部分）を取り出す。

   101110
&) 000111
---------
   000110

シフトとの併用

途中のビットだけを抜き出したいときはシフトとマスクを併用します。

例: 101110から中央の2ビット（太字の部分）を取り出す。

>>> bin((0b101110 >> 2) & 0b11)
'0b11'

NOTとの併用

ANDと組み合わせてNOTを使う場合、NOTの結果がマイナスになることは気にしないで使えるということを示します。

NOTの計算結果をANDでマスクすれば、桁数を限定してマイナスを排除できます。

>>> bin(~1 & 0b1111)
'0b1110'

この計算は2進数4桁に限定することで 0001 → 1110 という反転を示しています。

NOTはマスク値の作成に使うことが多く、その場合もマイナスのことは意識しません。

例えば101110の中央の2ビット（太字の部分）だけを消したい場合、NOTを使うことで消したい部分に注目したコードとなります。

>>> bin(0b101110 & ~0b001100)
'0b100010'

比較対象としてNOTを使わないコードを示します。残したい部分に注目しています。

>>> bin(0b101110 & 0b110011)
'0b100010'

ビットの合成

複数の値を別々の位置に収めたいときはシフトとORを併用します。

例: 101と110を並べて1つの値に合成する。

>>> bin((0b101 << 3) | 0b110)
'0b101110'

ANDとの併用

合成したい箇所に既に別の値が入っている場合は、先にANDで消してからORします。

例: 101101の下位3ビット（太字の部分）を011に置き替える。

   101101
&) 111000
---------
   101000
|)    011
---------
   101011

Pythonで確認します。

>>> bin(0b101101 & 0b111000 | 0b011)
'0b101011'

この手法は画像の生成で背景とキャラクターの合成にも使われます。

間違い探し

XORを使うと2つの数のうち異なるビットが分かります。

   11101011101110101
^) 11101101101110101
--------------------
   00000110000000000

Pythonで確認します。

>>> bin(0b11101011101110101 ^ 0b11101101101110101)
'0b110000000000'

値の入れ替え

実用性というより、知識としての紹介です。

多重XORの応用で、変数の値を交換するテクニックがあります。

• XOR交換アルゴリズム - Wikipedia

Pythonで確認します。

>>> a = 12
>>> b = 34
>>> a, b
(12, 34)
>>> a = a ^ b
>>> b = a ^ b
>>> a = a ^ b
>>> a, b
(34, 12)

実用上はタプルを使った方が簡単です。

>>> a, b = b, a

計算との関係

ビット演算ではある種の計算が代用できます。よく使われるものを取り上げます。

掛け算

2進数は桁が上がることに値が2倍になります。

2進数	10進数	左シフト	計算
0b1	1	1 << 0	$2^0$
0b10	2	1 << 1	$2^1$
0b100	4	1 << 2	$2^2$
0b1000	8	1 << 3	$2^3$

つまり 1 << n は $2^n$ と等しいです。

任意の数を1ビット左シフトするごとに2倍になります。

左シフト	掛け算	出力
bin(5<<0)	bin(5)	'0b101'
bin(5<<1)	bin(5*2)	'0b1010'
bin(5<<2)	bin(522)	'0b10100'
bin(5<<3)	bin(522*2)	'0b101000'

つまり『nビットの左シフト』は『$2^n$との掛け算』と同じ結果です。

割り算

逆の理屈で『nビットの右シフト』は『$2^n$での割り算（切り捨て）』と同じ結果です。

右シフト	割り算	出力
bin(45>>0)	bin(45)	'0b101101'
bin(45>>1)	bin(45/2)	'0b10110'
bin(45>>2)	bin(45/2/2)	'0b1011'
bin(45>>3)	bin(45/2/2/2)	'0b101'

割り算の余り

『$2^n$ による割り算の余り』は『$2^n-1$とのAND』に等しいです。

• x % (2 ** n) == x & ((2 ** n) - 1)

例: x % 8 == x & 7

この関係は任意の除数（$a÷b$の$b$）では成り立ちません。除数は$2$の階乗に限定されます。

説明

これが成り立つ理由をなるべく直感的に説明します。

0b110101を3ビット右シフトするのは、$2^3=8$で割って切り捨てたのと等しいです。

>>> bin(0b110101 >> 3)
'0b110'
>>> bin(0b110101 / 8)
'0b110'

このときにシフトで押し出された下位3ビット101が割り算の余りに相当します。111でマスクすると取り出せます。

>>> bin(0b110101 & 0b111)
'0b101'
>>> bin(0b110101 % 8)
'0b101'

0b111は7で、つまり8-1です。これにより次の関係を確認しました。

• x % 8 == x & 7

$2$の階乗ではビットが$1$になる桁は1つだけで、その数から$1$を引けばビットは$1$が並ぶことを意識すれば理解しやすいです。

例: $8 - 1 = 7$ (0x1000 - 1 = 0x111)

切り下げ

『下位nビットのクリア』は『$2^n$での切り下げ』に相当します。

例としてシフトによる$2^3=8$での切り下げを示します。右シフトで下位3ビットを押し出して、左シフトで元のビット幅に戻しています。

>>> 15 >> 3 << 3
8
>>> 16 >> 3 << 3
16
>>> 17 >> 3 << 3
16

特定のビットを消すのはANDとNOTの組み合わせでも可能です。最初は分かりにくいかもしれませんが、シフトよりもこの方法がよく使われます。

>>> 15 & ~0b111
8
>>> 16 & ~0b111
16
>>> 17 & ~0b111
16

0b111は7で、つまり8-1です。これは先に見た余りを求める方法にも出て来た関係です。

~7 → -8 の関係を使うと、8での切り下げを-8で表現できます。

>>> 15 & -8
8
>>> 16 & -8
16
>>> 17 & -8
16

これを初めて見ると意味が分からないかもしれません。とりあえず「こういう式で表記することもある」とだけ認識しておけば良いです。