整数の論理演算とビット操作
今回は F# のビット操作について説明します。
●ビット演算子
F# の場合、同じ記号を 3 つ続けたものがビット演算子になります。F# のビット演算子を下表に示します。
| 演算子 | 操作 |
|---|---|
| x &&& y | ビットごとの論理積 (AND) |
| x ||| y | ビットごとの論理和 (OR) |
| x ^^^ y | ビットごとの排他的論理和 (XOR) |
| ~~~x | ビットごとの否定 (NOT) |
| x <<< y | x を y ビット左シフト |
| x >>> y | x を y ビット右シフト |
演算子 &&& はビットごとの論理積を返します。
5 &&& 3 => 1
0101
AND 0011
---------
0001
演算子 ||| はビットごとの論理和を返します。
5 ||| 3 => 7
0101
OR 0011
--------
0111
演算子 ^^^ はビットごとの排他的論理和を返します。
5 ^^^ 3 => 6
0101
XOR 0011
---------
0110
演算子 ~~~ はビットごとの論理的な否定を返します。
~~~1 => -2 ~~~0 => -1
<<<, >>> はビットをシフトする演算子です。左シフトの場合、下位ビットには 0 が挿入されます。右シフトの場合、正の整数 (または無符号整数) では上位ビットに 0 が挿入されます。負の整数では 1 が挿入されます。これを「算術シフト」といいます。
1 <<< 8 => 256 1 <<< 16 => 65536 256 >>> 8 => 1 65536 >>> 8 => 256 -256 >>> 8 => -1
それでは簡単な例題として、基本的なビット操作関数を作ってみましょう。
> let testBit x n = x &&& (1 <<< n) <> 0;; val testBit: x: int -> n: int32 -> bool > let setBit x n = x ||| (1 <<< n);; val setBit: x: int -> n: int32 -> int > let clearBit x n = x &&& ~~~(1 <<< n);; val clearBit: x: int -> n: int32 -> int
testBit は整数 x の n 番目のビットが 1 ならば true を返します。最下位 (LSB) のビットが 0 番目になります。int32 (32 bit) の場合、n は 0 から 31 になります。1 を n ビット左シフトして、x との論理積が 0 でなければ、n 番目のビットは 1 であることがわかります。
setBit は x の n 番目のビットを 1 にセットします。1 を n ビット左シフトして、x との論理和を計算すれば、n 番目のビットを 1 にすることができます。clearBit は x の n 番目のビットを 0 にクリアします。これは n 番目以外のビットを 1 に、n 番目のビットを 0 にして、それと x の論理積を計算すれば、n 番目のビットをクリアすることができます。1 を n ビット左シフトして、その否定を計算すると、n 番目のビット以外は 1 になります。
それでは実際に試してみましょう。
> testBit 256 7;; val it: bool = false > testBit 256 8;; val it: bool = true > testBit 256 9;; val it: bool = false > for i = 0 to 7 do - let x = setBit 0 i - printfn "%d" x - clearBit x i |> printfn "%d" ;; 1 0 2 0 4 0 8 0 16 0 32 0 64 0 128 0 val it: unit = ()
●組み合わせの生成
組み合わせの生成は拙作のページ 順列と組み合わせ で取り上げました。このほかに、n 個の中から m 個を選ぶ組み合わせは、ビットの 0, 1 で表すことができます。たとえば、5 個の数字 (0 - 4) から 3 個を選ぶ場合、数字を 0 番目 から 4 番目のビットに対応させます。すると、1, 3, 4 という組み合わせは 11010 と表すことができます。簡単な例題として、ビットを使って組み合わせを求めてみましょう。
組み合わせを求めるプログラムは次のようになります。
リスト : 組み合わせの生成
let combinations func n m =
let rec comb n m a =
if m = 0 then func a
else if m = n then func (a ||| ((1 <<< m) - 1))
else (
comb (n - 1) m a
comb (n - 1) (m - 1) (a ||| (1 <<< (n - 1)))
)
comb n m 0
関数 combinations は n 個の中から m 個を選ぶ組み合わせを生成して、引数の関数 f に渡します。実際の処理は局所関数 comb で行います。組み合わせは引数 a にセットします。m が 0 になったら、組み合わせがひとつできたので func a を呼び出します。n が m と等しくなったならば、残り m 個を全て選びます。(1 <<< m) - 1 で m 個のビットをオンにして関数 f を呼び出します。
あとは comb を再帰呼び出しします。最初の呼び出しは n 番目の数字を選ばない場合です。n - 1 個の中から m 個を選びます。次の呼び出しが n 番目の数字を選ぶ場合で、a の n - 1 番目のビットをオンにします。そして、n - 1 個の中から m - 1 個を選びます。
それでは 5 個の中から 3 個を選ぶ組み合わせの実行例を示します。
> let combinations func n m = - let rec comb n m a = - if m = 0 then func a - else if m = n then func (a ||| ((1 <<< m) - 1)) - else ( - comb (n - 1) m a - comb (n - 1) (m - 1) (a ||| (1 <<< (n - 1))) - ) - comb n m 0;; val combinations: func: (int -> unit) -> n: int -> m: int -> unit > combinations (fun x -> printfn "%05B" x) 5 3;; 00111 01011 01101 01110 10011 10101 10110 11001 11010 11100 val it: unit = ()
この場合、最小値は 111 (0x07)1) で最大値は 11100 (0x1c) になります。このように、combinations は組み合わせを表す数を昇順で出力します。
●ちょっと便利なビット操作
最も右側 (LSB 側) にある 1 を 0 にクリアする、逆に最も右側にある 0 を 1 にセットすることは簡単にできます。
(1) 右側にある 1 をクリア => x &&& (- x) x : 1 1 1 1 x - 1 : 1 1 1 0 ---------------- AND : 1 1 1 0 x : 1 0 0 0 x - 1 : 0 1 1 1 ---------------- AND : 0 0 0 0 (2) 右側にある 0 を 1 にセット => x ||| (x + 1) x : 0 0 0 0 x + 1 : 0 0 0 1 ---------------- OR : 0 0 0 1 x : 0 1 1 1 x - 1 : 1 0 0 0 ---------------- OR : 1 1 1 1
上図 (1) を見てください。x から 1 を引くと、右側から連続している 0 は桁借りにより 1 になり、最初に出現する 1 が 0 になります。したがって、x &&& (x - 1) を計算すると、最も右側にある 1 を 0 にクリアすることができます。(2) の場合、x に 1 を足すと、右側から連続している 1 は桁上がりにより 0 になり、最初に出現する 0 が 1 になります。x ||| (x + 1) を計算すれば、最も右側にある 0 を 1 にセットすることができます。
また、最も右側にある 1 を取り出すことも簡単にできます。簡単な例として 4 ビットの整数値を考えてみます。負の整数を 2 の補数で表した場合、4 ビットで表される整数は -8 から 7 になります。次の図を見てください。
0 : 0000
1 : 0001 -1 : 1111 1 &&& (-1) => 0001
2 : 0010 -2 : 1110 2 &&& (-2) => 0010
3 : 0011 -3 : 1101 3 &&& (-3) => 0001
4 : 0100 -4 : 1100 4 &&& (-4) => 0100
5 : 0101 -5 : 1011 5 &&& (-5) => 0001
6 : 0110 -6 : 1010 6 &&& (-6) => 0010
7 : 0111 -7 : 1001 7 &&& (-7) => 0001
-8 : 1000
図 : 最も右側にある 1 を取り出す方法
2 の補数はビットを反転した値 (1 の補数) に 1 を加算することで求めることができます。したがって、x と -x の論理積 x &&& (-x) は、最も右側にある 1 だけが残り、あとのビットはすべて 0 になります。
●ビットが 1 の個数を求める
次は、ビットが 1 の個数を数える処理を作ってみましょう。プログラムは次のようになります。
リスト : ビットカウント
let bitCount n =
let rec iter m c =
if m = 0 then c
else iter (m &&& (m - 1)) (c + 1)
iter n 0
整数 n の右側から順番に 1 をクリアしていき、0 になるまでの回数を求めます。とても簡単ですね。32 個のビットを順番に調べるよりも高速です。
int を 32 bit とする場合、次の方法で 1 の個数をもっと高速に求めることができます。
リスト : ビットカウント (2) let bitCount1 n = let a = (n &&& 0x55555555) + ((n >>> 1) &&& 0x55555555) let b = (a &&& 0x33333333) + ((a >>> 2) &&& 0x33333333) let c = (b &&& 0x0f0f0f0f) + ((b >>> 4) &&& 0x0f0f0f0f) let d = (c &&& 0x00ff00ff) + ((c >>> 8) &&& 0x00ff00ff) (d &&& 0xffff) + (d >>> 16)
最初に、整数を 2 bit ずつに分割して、1 の個数を求めます。たとえば、整数 n を 4 bit で考えてみましょう。5 を 2 進数で表すと 0101 になり、n と論理積を計算すると 0, 2 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。同様に n を 1 ビット右シフトして論理積を計算すると、1, 3 番目のビットが 1 であれば、結果の 0, 2 番目のビットは 1 になります。あとは、それを足し算すれば 2 bit の中にある 1 の個数を求めることができます。
変数 a には 2 ビットの中の 1 の個数が格納されています。左隣の 2 ビットの値を足し算すれば、4 ビットの中の 1 の個数を求めることができます。次に、左隣の 4 ビットの値を足し算して 8 ビットの中の 1 の個数を求め、左隣の 8 ビットの値を足し算して、というように順番に値を加算していくと 32 ビットの中にある 1 の個数を求めることができます。
bitCount は 1 の個数が多くなると遅くなりますが、bitCount1 は 1 の個数に関係なく高速に動作します。興味のある方は試してみてください。
簡単な実行例を示します。
> let bitCount n = - let rec iter m c = - if m = 0 then c - else iter (m &mmap;&& (m - 1)) (c + 1) - iter n 0;; val bitCount: n: int -> int > let bitCount1 n = - let a = (n &mmap;&& 0x55555555) + ((n >>> 1) &mmap;&& 0x55555555) - let b = (a &mmap;&& 0x33333333) + ((a >>> 2) &mmap;&& 0x33333333) - let c = (b &mmap;&& 0x0f0f0f0f) + ((b >>> 4) &mmap;&& 0x0f0f0f0f) - let d = (c &mmap;&& 0x00ff00ff) + ((c >>> 8) &mmap;&& 0x00ff00ff) - (d &mmap;&& 0xffff) + (d >>> 16);; val bitCount1: n: int -> int > bitCount 0;; val it: int = 0 > bitCount1 0;; val it: int = 0 > bitCount 256;; val it: int = 1 > bitCount1 256;; val it: int = 1 > bitCount 65535;; val it: int = 16 > bitCount1 65535;; val it: int = 16 > bitCount 0x7fffffff;; val it: int = 31 > bitCount1 0x7fffffff;; val it: int = 31 > bitCount 0x7f00ff00;; val it: int = 15 > bitCount1 0x7f00ff00;; val it: int = 15
●パズル「ライツアウト」
それでは、例題として Puzzel DE Programming で取り上げた ライツアウト というパズルを F# で解いてみましょう。ライツアウトは光っているボタンをすべて消すことが目的のパズルです。ルールはとても簡単です。あるボタンを押すと、そのボタンと上下左右のボタンの状態が反転します。つまり、光っているボタンは消灯し消えていたボタンは点灯します。次の図を見てください。
図 : ライツアウトの点灯パターン
ボタンは 5 行 5 列に配置されています。上図のように、中央のボタン 12 を押すとそのボタンと上下左右のボタンの状態が反転します。ライツアウトはライトオン・オフの 2 種類の状態しかないので、盤面はリストよりもビットを使って表した方が簡単です。ライトオン・オフの状態を 1 と 0 で表し、各ビットとボタンの座標を対応させると、盤面は 0 から 33554431 の整数値で表すことができます。
ボタンを押してライトの状態を反転する処理も簡単です。たとえば、中央のボタン 12 を押した場合、7, 11, 12, 13, 17 のライトを反転させます。この場合、5 つのボタンのビットをオンにした値 0x23880 と、盤面を表す整数値の排他的論理和 (XOR) を求めれば、5 つのライトの状態を反転することができます。次の例を見てください。
0 XOR 0x23880 => 0x23880 % 消灯の状態でボタン 12 を押す（点灯する） #x23880 XOR 0x23880 => 0 % もう一度同じボタンを押す（消灯する）
このように、ライツアウトは同じボタンを二度押すと元の状態に戻ります。したがって、同じボタンは二度押さなくてよいことがわかります。また、実際にボタンを押してみるとわかりますが、ボタンを押す順番は関係がないことがわかります。たとえば、ボタン 0 と 1 を押す場合、0 -> 1 と押すのも 1 -> 0 と押すのも同じ結果になります。
この 2 つの法則から、ボタンを押す組み合わせは全部で 225 通りになります。ライツアウトを解くいちばん単純な方法は、ボタンを押す組み合わせを生成して、実際にライトが全部消えるかチェックすることです。最近のパソコンは高性能なので、単純な方法でも解くことができます。
●ライツアウトの解法
プログラムは次のようになります。
リスト : ライツアウトの解法 (lo.fsx)
// ボタンを押したときの反転パターン
let pattern = [|
0x0000023; 0x0000047; 0x000008e; 0x000011c; 0x0000218;
0x0000461; 0x00008e2; 0x00011c4; 0x0002388; 0x0004310;
0x0008c20; 0x0011c40; 0x0023880; 0x0047100; 0x0086200;
0x0118400; 0x0238800; 0x0471000; 0x08e2000; 0x10c4000;
0x0308000; 0x0710000; 0x0e20000; 0x1c40000; 0x1880000
|]
// 組み合わせの生成
let combinations func n m =
let rec comb n m a =
if m = 0 then func a
else if m = n then func (a ||| ((1 <<< m) - 1))
else (
comb (n - 1) m a
comb (n - 1) (m - 1) (a ||| (1 <<< (n - 1)))
)
comb n m 0
// 解答の表示
let printAnswer x =
for i = 0 to 24 do
printf (if x &&& (1 <<< i) <> 0 then "O " else ". ")
if (i + 1) % 5 = 0 then printfn ""
printfn ""
let check board x =
let mutable b = board
for i = 0 to 24 do
if x &&& (1 <<< i) <> 0 then b <- b ^^^ pattern.[i]
if b = 0 then printAnswer x
let lo board =
for i = 1 to 25 do
printfn "----- %d -----" i
combinations (fun x -> check board x) 25 i
関数 lo で関数 comnbinations を呼び出して、25 個の中から i 個のボタンを押す組み合わせを生成します。関数 check の引数 board が盤面を表し、引数 x が押すボタンの位置を表します。今回は board の値を書き換えたいので、mutable な変数 b を用意します。
ボタンはビットの位置で表されているので、for ループでビットが 1 の位置を調べます。あとは b と pattern.[i] の排他的論理和を求めれば、そのボタンを押したことになります。選んだボタンを全部押して b が 0 になれば関数 printAnswer で解を表示します。
あとは特に難しいところはないと思います。それでは実行してみましょう。ライトが全部点灯している状態 (0x1ffffff) を解いてみます。
> open Lo;; > lo 0x1ffffff;; ----- 1 ----- ----- 2 ----- ----- 3 ----- ----- 4 ----- ----- 5 ----- ----- 6 ----- ----- 7 ----- ----- 8 ----- ----- 9 ----- ----- 10 ----- ----- 11 ----- ----- 12 ----- ----- 13 ----- ----- 14 ----- ----- 15 ----- . O O . O . O O O . . . O O O O O . O O O O . . . . . . O O O O . O O O O O . . . O O O . O . O O . O O . . . O O . O O . . O O O . O O O . . O O . O O . O O . . O O O . O O O . . O O . O O . . . O O ----- 16 ----- ----- 17 ----- ----- 18 ----- ----- 19 ----- ----- 20 ----- ----- 21 ----- ----- 22 ----- ----- 23 ----- ----- 24 ----- ----- 25 ----- val it: unit = ()
4 通りの解が出力されました。ボタンが全部点灯している場合、ボタンを押す回数はどの解も 15 回になります。実は、これがライツアウトの最長手数なのです。
ライトの点灯パターンは 225 = 33554432 通りありますが、実際に解が存在するパターンは、その 1 / 4 の 8388608 通りしかありません。その中で最短回数が 15 回で解けるパターンは 7350 通りあり、そのうちのひとつがライトが全部点灯しているパターンなのです。ライツアウトの最長手数に興味のある方は、Puzzle DE Programming：ライツアウト の 最長手数を求める をお読みくださいませ。
●高速化
ライツアウトは次の図に示すように、ボタンを上から 1 行ずつ消灯していくという、わかりやすい方法で解くことができます。
図 : 1 行ずつボタンを消灯していく方法
(1) では、1 行目のボタンが 2 つ点灯しています。このボタンを消すには、真下にある 2 行目の B と D のボタンを押せばいいですね。すると (2) の状態になります。次に、2 行目のボタンを消します。3 行目の A, B, D, E のボタンを押して (3) の状態になります。
あとはこれを繰り返して 4 行目までのボタンを消したときに、5 行目のボタンも全部消えていれば成功となります。(4) のように、5 行目のボタンが消えない場合は失敗です。この場合は、1 行目のボタンを押して、点灯パターンを変更します。
2 - 5 行目のボタンの押し方は、1 行目の点灯パターンにより決定されるので、けっきょく 1 行目のボタンの押し方により、解けるか否かが決まります。この場合、ボタンの押し方は、25 = 32 通りしかありせん。つまり、たった 32 通り調べるだけでライツアウトの解を求めることができるのです。
プログラムは次のようになります。
リスト : ライツアウトの高速化
let lo1 board =
for i = 0 to 31 do
let mutable b = board
let mutable p = 0
// 1 行目を押す
for j = 0 to 4 do
if i &&& (1 <<< j) <> 0 then (
b <- b ^^^ pattern.[j]
p <- p ||| (1 <<< j)
)
// 2 - 5 行目を消す
for j = 0 to 19 do
if b &&& (1 <<< j) <> 0 then (
b <- b ^^^ pattern.[j + 5]
p <- p ||| (1 <<< (j + 5))
)
if b = 0 then printAnswer p
1 行目のボタンの押し方は 32 通りあるので、ボタンの押し方を 0 から 31 までの数値で表すことにします。値は 5 ビットで表すことができるので、ビットとボタンの位置を対応させて、ビットがオンであればそのボタンを押すことにします。盤面 board を mutable な変数 b にセットして、演算子 ^^^ で b の点灯パターンを変更します。押したボタンの位置は mutable な変数 p にセットします。
次は、1 行ずつ盤面 b のライトを消していきます。変数 j がチェックするボタンの位置を表します。b &&& (1 <<< j) で j の位置のビットを調べ、それがオンであればライトが点灯しいるので 1 行下のボタンを押します。押すボタンの位置は j + 5 で求めることができます。そして最後に盤面 b の値をチェックします。b が 0 であればライトが全部消えています。関数 printAnswer で解を出力します。
実行結果は同じなので省略させていただきます。興味のある方は試してみてください。なお、下記 URL によると、ライツアウトの解法は連立一次方程式を解くことに帰着させることができるそうです。
- 驚異のライツアウト解法ロジック, (高橋謙一郎さん)
- ライツアウト(３カラーパズル)の計算解法, (高橋謙一郎さん)
- ライツアウト ＆ ８めくりパズル, (deepgreen さん)
拙作のページ お気楽 Numpy プログラミング超入門 や Julia Programming: Puzzle DE Julia!! でも連立方程式によるライツアウトの解法を取り上げています。よろしければお読みくださいませ。
●参考 URL
ビットが 1 の個数を数える方法は フィンローダさん の 初級Ｃ言語Ｑ＆Ａ(15) を参考にさせていただきました。フィンローダさんに感謝いたします。
●プログラムリスト
//
// lo.fsx : ライツアウトの解法
//
// Copyright (C) 2022 Makoto Hiroi
//
// ボタンを押したときの反転パターン
let pattern = [|
0x0000023; 0x0000047; 0x000008e; 0x000011c; 0x0000218;
0x0000461; 0x00008e2; 0x00011c4; 0x0002388; 0x0004310;
0x0008c20; 0x0011c40; 0x0023880; 0x0047100; 0x0086200;
0x0118400; 0x0238800; 0x0471000; 0x08e2000; 0x10c4000;
0x0308000; 0x0710000; 0x0e20000; 0x1c40000; 0x1880000
|]
// 組み合わせの生成
let combinations func n m =
let rec comb n m a =
if m = 0 then func a
else if m = n then func (a ||| ((1 <<< m) - 1))
else (
comb (n - 1) m a
comb (n - 1) (m - 1) (a ||| (1 <<< (n - 1)))
)
comb n m 0
// 解答の表示
let printAnswer x =
for i = 0 to 24 do
printf (if x &&& (1 <<< i) <> 0 then "O " else ". ")
if (i + 1) % 5 = 0 then printfn ""
printfn ""
let check board x =
let mutable b = board
for i = 0 to 24 do
if x &&& (1 <<< i) <> 0 then b <- b ^^^ pattern.[i]
if b = 0 then printAnswer x
let lo board =
for i = 1 to 25 do
printfn "----- %d -----" i
combinations (fun x -> check board x) 25 i
// 高速化
let lo1 board =
for i = 0 to 31 do
let mutable b = board
let mutable p = 0
// 1 行目を押す
for j = 0 to 4 do
if i &&& (1 <<< j) <> 0 then (
b <- b ^^^ pattern.[j]
p <- p ||| (1 <<< j)
)
// 2 - 5 行目を消す
for j = 0 to 19 do
if b &&& (1 <<< j) <> 0 then (
b <- b ^^^ pattern.[j + 5]
p <- p ||| (1 <<< (j + 5))
)
if b = 0 then printAnswer p