整数の論理演算とビット操作
関数型言語や Scala では、データを表すのにリストがよく使われます。ところが、問題によってはリストよりもビットで表した方が、プログラムを作るのに都合がよい場合もあります。今回は Scala のビット操作について説明します。
●ビット演算子
Scala のビット演算子は Java と同じです。
| 演算子 | 操作 |
|---|---|
| x & y | ビットごとの論理積 |
| x | y | ビットごとの論理和 |
| x ^ y | ビットごとの排他的論理和 |
| ~x | ビットごとの否定 |
| x << y | x を y ビット左シフト |
| x >> y | x を y ビット右シフト (算術シフト) |
| x >>> y | x を y ビット右シフト |
演算子 & はビットごとの論理積を返します。
scala> 5 & 3 val res0: Int = 1
0101
AND 0011
---------
0001
演算子 l はビットごとの論理和を返します。
scala> 5 | 3 val res1: Int = 7
0101
OR 0011
--------
0111
演算子 ^ はビットごとの排他的論理和を返します。
scala> 5 ^ 3 val res2: Int = 6
0101
XOR 0011
---------
0110
演算子 ~ はビットごとの論理的な否定を返します。
scala> ~1 val res3: Int = -2 scala> ~0 val res4: Int = -1
<<, >>, >>> はビットをシフトする演算子です。>> は算術シフトなので、負の数で i ビット右シフトしたあと、上位 i 個のビットは 1 になります。>>> の場合、上位ビットには 0 が挿入されます。
scala> 1 << 8 val res5: Int = 256 scala> 1 << 16 val res6: Int = 65536 scala> 256 >> 8 val res7: Int = 1 scala> 65536 >> 8 val res8: Int = 256 scala> -256 >> 8 val res9: Int = -1 scala> -256 >>> 8 val res10: Int = 16777215
それでは簡単な例題として、基本的なビット操作関数を作ってみましょう。次のリストを見てください。
リスト : 基本的なビット操作 // ビットのテスト def testBit(x: Int, n: Int): Boolean = (x & (1 << n)) != 0 // ビットセット def setBit(x: Int, n: Int): Int = x | (1 << n) // ビットクリア def clearBit(x: Int, n: Int): Int = x & ~(1 << n)
testBit は整数 x の n 番目のビットが 1 ならば true を返します。最下位 (LSB) のビットが 0 番目になります。Int (32 bit) の場合、n は 0 から 31 になります。1 を n ビット左シフトして、x との論理積が 0 でなければ、n 番目のビットは 1 であることがわかります。
bitSet は x の n 番目のビットを 1 にセットします。1 を n ビット左シフトして、x との論理和を計算すれば、n 番目のビットを 1 にすることができます。clearBit は x の n 番目のビットを 0 にクリアします。これは n 番目以外のビットを 1 に、n 番目のビットを 0 にして、それと x の論理積を計算すれば、n 番目のビットをクリアすることができます。1 を n ビット左シフトして、その否定を計算すると、n 番目のビット以外は 1 になります。
それでは実際に試してみましょう。
scala> testBit(256, 7) val res0: Boolean = false scala> testBit(256, 8) val res1: Boolean = true scala> testBit(256, 9) val res2: Boolean = false scala> for (i <- 0 to 16) println(setBit(0, i)) 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 scala> for (i <- 0 to 15) println(clearBit(65535, i)) 65534 65533 65531 65527 65519 65503 65471 65407 65279 65023 64511 63487 61439 57343 49151 32767
●組み合わせの生成
組み合わせの生成は拙作のページ 順列と組み合わせ で説明しました。このほかに、n 個の中から m 個を選ぶ組み合わせは、ビットの 0, 1 で表すことができます。たとえば、5 個の数字 (0 - 4) から 3 個を選ぶ場合、数字を 0 番目 から 4 番目のビットに対応させます。すると、1, 3, 4 という組み合わせは 11010 と表すことができます。簡単な例題として、ビットを使って組み合わせを求めてみましょう。
組み合わせを求めるプログラムは次のようになります。
リスト : 組み合わせの生成
def combinations(f: Int => Unit, n: Int, m: Int, a: Int = 0): Unit = {
if (m == 0) f(a)
else if (m == n) f(a | ((1 << m) - 1))
else {
combinations(f, n - 1, m, a)
combinations(f, n - 1, m - 1, setBit(a, n - 1))
}
}
関数 combinations は n 個の中から m 個を選ぶ組み合わせを生成して、引数の関数 f に渡します。組み合わせは引数 a にセットします。m が 0 になったら、組み合わせがひとつできたので f(a) を呼び出します。n が m と等しくなったならば、残り m 個を全て選びます。(1 << m) - 1 で m 個のビットをオンにして関数 f を呼び出します。
あとは combinations を再帰呼び出しします。最初の呼び出しは n 番目の数字を選ばない場合です。n - 1 個の中から m 個を選びます。次の呼び出しが n 番目の数字を選ぶ場合で、a の n - 1 番目のビットをオンにします。そして、n - 1 個の中から m - 1 個を選びます。
それでは 5 個の中から 3 個を選ぶ combinations(5, 3) の実行例を示します。
scala> combinations(println, 5, 3) 7 11 13 14 19 21 22 25 26 28
この場合、最小値は 7 (111) で最大値は 28 (11100) になります。このように、combinations は組み合わせを表す数を昇順で出力します。
●組み合わせに番号を付ける方法
次は、N 通りある組み合わせに 0 から N - 1 までの番号を付ける方法を紹介しましょう。たとえば、6 個の中から 3 個を選ぶ組み合わせは 20 通りありますが、この組み合わせに 0 から 19 までの番号を付けることができます。1 1 1 0 0 0 を例題に考えてみましょう。次の図を見てください。
図 : 6Ｃ3 の組み合わせ
最初に 5 をチェックします。5 を選ばない場合は 5Ｃ3 = 10 通りありますね。この組み合わせに 0 から 9 までの番号を割り当てることにすると、5 を選ぶ組み合わせの番号は 10 から 19 までとなります。
次に、4 をチェックします。4 を選ばない場合は、4Ｃ2 = 6 通りあります。したがって、5 を選んで 4 を選ばない組み合わせに 10 から 15 までの番号を割り当てることにすると、5 と 4 を選ぶ組み合わせには 16 から 19 までの番号となります。
最後に、3 をチェックします。同様に 3 を選ばない場合は 3 通りあるので、これに 16 から 18 までの番号を割り当て、5, 4, 3 を選ぶ組み合わせには 19 を割り当てます。これで組み合わせ 1 1 1 0 0 0 の番号を求めることができました。
では、0 0 0 1 1 1 はどうなるのでしょうか。左から順番にチェックしていくと、最初の 1 が見つかった時点で、その数字を選ばない組み合わせは存在しません。つまり、残りの数字をすべて選ぶしかないわけです。したがって、これが 0 番目となります。
このように、数字を選ぶときに、数字を選ばない場合の組み合わせの数を足し算していけば、その組み合わせの番号を求めることができるのです。
●組み合わせを番号に変換
組み合わせを番号に変換するプログラムは次のようになります。
リスト : 組み合わせを番号に変換
// 組み合わせの数
def combNum(n: Int, r: Int): Int =
if (n == r || r == 0)
1
else
combNum(n, r - 1) * (n - r + 1) / r
// 組み合わせを番号に変換
def combToNum(c: Int, n: Int, r: Int, value: Int = 0): Int =
if (r == 0 || n == r) value
else if (testBit(c, n - 1))
combToNum(c, n - 1, r - 1, value + combNum(n - 1, r))
else
combToNum(c, n - 1, r, value)
関数 combNum は組み合わせの数を求めます。combToNum の引数 c はビットのオンオフで表した組み合わせ、引数 n と r は nＣr の n と r を表しています。引数 value は求める番号を表します。n と r の値が同じになるか、もしくは r が 0 になれば、組み合わせの番号を計算できたので value を返します。
そうでない場合、c の n - 1 ビットの値を調べます。ビットがオンであれば、value に combNum(n - 1, r) の値を足し算し、r を -1 して combToNum を再帰呼び出しします。そうでなければ、value と r の値はそのままで combToNum を再帰呼び出しします。
簡単な実行例を示します。
scala> combToNum(7, 5, 3) val res2: Int = 0 scala> combToNum(21, 5, 3) val res3: Int = 5 scala> combToNum(28, 5, 3) val res4: Int = 9
●番号を組み合わせに変換
逆に、番号から組み合わせを求めるプログラムも簡単に作ることができます。次のリストを見てください。
リスト : 番号を組み合わせに変換
def numToComb(value: Int, n: Int, r: Int, c: Int = 0): Int =
if (r == 0) c
else if (n == r) c | ((1 << n) - 1)
else {
val k = combNum(n - 1, r)
if (value >= k)
numToComb(value - k, n - 1, r - 1, setBit(c, n - 1))
else
numToComb(value, n - 1, r, c)
}
引数 value が番号で、引数 n と r は nＣr の n と r を表しています。引数 c が求める組み合わせです。たとえば、n = 5, r = 3 の場合、ビットが 1 になるのは 4C2 = 6 通りあり、0 になるのは 4C3 = 4 通りあります。したがって、数値が 0 - 3 の場合はビットを 0 にし、4 - 9 の場合はビットを 1 にすればいいわけです。
ビットを 0 にした場合、残りは 4C3 = 4 通りになるので、同様に次のビットを決定します。ビットを 1 にした場合、残りは 4C2 = 6 通りになるので、value から 4 を引いて numToComb を再帰呼び出しして次のビットを決定します。
r が 0 の場合は、組み合わせが完成したので c を返します。n と r が等しい場合は、残りのビットをすべて 1 にセットしてから c を返します。それ以外の場合は、n-1Cr の値を combNum(n - 1, r) で求めて変数 k にセットします。value が k 以上であれば変数 c のビットを 1 にセットし、value から k を引き算して numToComb を再帰呼び出しします。そうでなければ、numToComb を再帰呼び出しするだけです。
それでは、n = 5, r = 3 の場合の実行例を示します。
scala> for (i <- 0 to 9) println(numToComb(i, 5, 3)) 7 11 13 14 19 21 22 25 26 28
正常に動作していますね。この方法を使うと、n 個ある組み合わせの中の i 番目 (0 <= i < n) の組み合わせを簡単に求めることができます。
●ちょっと便利なビット操作
最も右側 (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 の個数を数える処理を作ってみましょう。データ型を Int とすると、プログラムは次のようになります。
リスト : ビットカウント
def bitCount(n: Int): Int = {
var c = 0
var m = n
while (m != 0) {
m &= m - 1
c += 1
}
c
}
整数 n の右側から順番に 1 をクリアしていき、0 になるまでの回数を求めます。とても簡単ですね。32 個のビットを順番に調べるよりも高速です。
Int を 32 bit とする場合、次の方法で 1 の個数をもっと高速に求めることができます。
リスト : ビットカウント (2)
def bitCount1(n: Int): Int = {
val a = (n & 0x55555555) + ((n >>> 1) & 0x55555555)
val b = (a & 0x33333333) + ((a >>> 2) & 0x33333333)
val c = (b & 0x0f0f0f0f) + ((b >>> 4) & 0x0f0f0f0f)
val 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 の個数に関係なく高速に動作します。興味のある方は試してみてください。
●BitSet
Scala には scala.collection.immutable に BitSet というビットで集合を表すクラスが用意されています。集合の要素は 0 以上の整数値になります。使い方は immutable なセット (Set) と同じです。
簡単な例を示しましょう。
scala> import scala.collection.immutable.{BitSet}
import scala.collection.immutable.BitSet
scala> val s = BitSet(1, 2, 3, 4, 5)
val s: scala.collection.immutable.BitSet = BitSet(1, 2, 3, 4, 5)
scala> s(0)
val res0: Boolean = false
scala> s(5)
val res1: Boolean = true
scala> s + 6
val res2: scala.collection.immutable.BitSet = BitSet(1, 2, 3, 4, 5, 6)
scala> s + (6, 7, 8, 9)
^
warning: method + in trait SetOps is deprecated (since 2.13.0):
Use ++ with an explicit collection argument instead of + with varargs
val res3: scala.collection.immutable.BitSet = BitSet(1, 2, 3, 4, 5, 6, 7, 8, 9)
scala> s - 1
val res4: scala.collection.immutable.BitSet = BitSet(2, 3, 4, 5)
scala> s - (1, 2, 3)
^
warning: method - in trait SetOps is deprecated (since 2.13.0):
Use &- with an explicit collection argument instead of - with varargs
val res5: scala.collection.immutable.BitSet = BitSet(4, 5)
以前のバージョンでは、タプルに格納した複数の要素をまとめて追加 (または削除) することができたのですが、ver 2.13 から非推奨になりました。複数の要素を追加する場合は演算子 ++ (削除する場合は演算子 --) を使ってください。
scala> s ++ List(6, 7, 8, 9) val res7: scala.collection.immutable.BitSet = BitSet(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> s -- List(1, 2, 3) val res8: scala.collection.immutable.BitSet = BitSet(4, 5)
BitSet を使うと組み合わせの生成は次のようになります。
リスト : 組み合わせの生成 (BitSet 版)
def combinationSet(f: BitSet => Unit, n: Int, m: Int, a: BitSet = BitSet()): Unit = {
if (m == 0) f(a)
else if (m == n) f(a ++ Range(1, m + 1))
else {
combinationSet(f, n - 1, m, a)
combinationSet(f, n - 1, m - 1, a + n)
}
}
プログラムは簡単ですね。それでは実行してみましょう。
scala> combinationSet(println, 5, 3) BitSet(1, 2, 3) BitSet(1, 2, 4) BitSet(1, 3, 4) BitSet(2, 3, 4) BitSet(1, 2, 5) BitSet(1, 3, 5) BitSet(2, 3, 5) BitSet(1, 4, 5) BitSet(2, 4, 5) BitSet(3, 4, 5)
●参考 URL
ビットが 1 の個数を数える方法は フィンローダさん の 初級Ｃ言語Ｑ＆Ａ(15) を参考にさせていただきました。フィンローダさんに感謝いたします。
●プログラムリスト
//
// testbit.scala : ビット演算の簡単な例題
//
// Copyright (C) 2014-2021 Makoto Hiroi
//
import scala.collection.immutable.{BitSet}
object testbit {
// 基本的なビット操作
def testBit(x: Int, n: Int): Boolean = (x & (1 << n)) != 0
def setBit(x: Int, n: Int): Int = x | (1 << n)
def clearBit(x: Int, n: Int): Int = x & ~(1 << n)
// 組み合わせの生成
def combinations(f: Int => Unit, n: Int, m: Int, a: Int = 0): Unit = {
if (m == 0) f(a)
else if (m == n) f(a | ((1 << m) - 1))
else {
combinations(f, n - 1, m, a)
combinations(f, n - 1, m - 1, setBit(a, n - 1))
}
}
// BitSet 版
def combinationSet(f: BitSet => Unit, n: Int, m: Int, a: BitSet = BitSet()): Unit = {
if (m == 0) f(a)
else if (m == n) f(a ++ Range(1, m + 1))
else {
combinationSet(f, n - 1, m, a)
combinationSet(f, n - 1, m - 1, a + n)
}
}
// 組み合わせの数
def combNum(n: Int, r: Int): Int =
if (n == r || r == 0)
1
else
combNum(n, r - 1) * (n - r + 1) / r
// 組み合わせを番号に変換
def combToNum(c: Int, n: Int, r: Int, value: Int = 0): Int =
if (r == 0 || n == r) value
else if (testBit(c, n - 1))
combToNum(c, n - 1, r - 1, value + combNum(n - 1, r))
else
combToNum(c, n - 1, r, value)
// 番号を組み合わせに変換
def numToComb(value: Int, n: Int, r: Int, c: Int = 0): Int =
if (r == 0) c
else if (n == r) c | ((1 << n) - 1)
else {
val k = combNum(n - 1, r)
if (value >= k)
numToComb(value - k, n - 1, r - 1, setBit(c, n - 1))
else
numToComb(value, n - 1, r, c)
}
// ビット 1 の個数を数える
def bitCount(n: Int): Int = {
var c = 0
var m = n
while (m != 0) {
m &= m - 1
c += 1
}
c
}
// 高速版
def bitCount1(n: Int): Int = {
val a = (n & 0x55555555) + ((n >>> 1) & 0x55555555)
val b = (a & 0x33333333) + ((a >>> 2) & 0x33333333)
val c = (b & 0x0f0f0f0f) + ((b >>> 4) & 0x0f0f0f0f)
val d = (c & 0x00ff00ff) + ((c >>> 8) & 0x00ff00ff)
(d & 0xffff) + (d >>> 16)
}
}
改訂 2021 年 4 月 11 日
図 : 8 クイーンの解答例
図 : 斜めの利き筋のチェック