Goでビットの操作やカウントの実装を見てみる
この記事は Go Advent Calendar 2021 の6日目の記事です。
こんにちは、こんばんは。なんだかんだ Go をはじめて書いたときから9年が経っている kaneshin です。最初は誰かが作成したツールのリポジトリへ何かしらの修正を加えた Pull Request がメインで、2014年の夏ごろから自分でもツール作成をしていたようです。
はじめてのツールは DigitalOcean に Droplet を Vagrantfile を基にしてデプロイするツールで、『開発用のインスタンスをサクッと作りたかったんだろうか🤔』といった具合にモチベーションもよくわからないです。（※既にアーカイブしています）
さて、主題に戻ります。みなさんはビットを処理するコードって書いたりしていますか？
ビット演算のオペレータについては、大体どの言語でも扱っているので基本的なことは知っていると思います。ただ、実務ではビット演算のコードを書いてみたことが無い人も職種によっていたりするのではないでしょうか。
今日は基本的なオペレータについては触れませんが、ビットにまつわるちょっとしたアルゴリズムを Go の内部にあるコードから紹介したいと思います。
Binary Literals
10を基数とした 16 を2を基数とした基数変換（2進数変換）すると、 10000 になるのはご存知だと思います。
Goでは2を基数として数値表現を 0b からはじめることによって表現することができるのと、 fmt.Printf などで出力するときのフォーマットで値が整数型ならば %b でビット（つまり2進数）で出力することができます。
package mainimport "fmt"func main() {
const value = 0b0010000
fmt.Printf("decimal number: %d\n", value)
fmt.Printf(" binary number: %08b\n", value)
}
浮動小数点型 (floating-point) の場合は出力が異なるので気をつけてください。
Floating-point and complex constituents:
%b decimalless scientific notation with exponent a power of two,
in the manner of strconv.FormatFloat with the ‘b’ format,
e.g. -123456p-78
math/bits package, standard library
math パッケージの中には、符号なし整数型 (unsigned integer type) をビットとして操作やカウントを行うための bits パッケージが標準ライブラリとして提供されています。
このパッケージの由来は、アセンブリを Go のコードにインライン化できないことで発生するパフォーマンス影響を考えて実装された組み込み関数 (Intrinsic function) です。これらはビットの中にどれだけ 1 がフラグとして立っているかをカウントすることや操作をする重要な機能であり、最近の CPU ではネイティブハードウェアの命令として実装されており、CPU アーキテクチャと Go のバージョンに応じて、ネイティブハードウェアの命令に置き換えられます。この辺りは Dave Cheney 氏の記事を読むと良いと思います。
ちなみに、C言語ならば gcc によって下記のようにアセンブリをインライン化することができます。
void do_something()
{
int src = 1;
int dst;asm ("mov %1, %0\n\t"
"add $1, %0"
: "=r" (dst)
: "r" (src)); printf("%d\n", dst);
}
さて、そんな背景のある math/bits パッケージなので、Goコード上も癖のあるコードがあるので、それを紹介したいと思います。
Counting Bits
上にリンクをした Dave Cheney 氏の記事にも “Ones count” というセクションで触れられており、なおかつ、 bits.OneCount64関数はネイティブハードウェア命令を使用するところまでコンパイラが最適化しているのかを確認しています。
ここでは、その文中にある Hacker’s Delight の実装が math/bits としてGoに実装されている紹介です。少しだけ引用（見やすいようにコメントを消しています）してきましたが、見ればわかる通り一瞬だと何もわかりません。（一瞬でわかったら頭の中に演算装置ありますね）
const m0 = 0x5555555555555555 // 01010101 ...
const m1 = 0x3333333333333333 // 00110011 ...
const m2 = 0x0f0f0f0f0f0f0f0f // 00001111 ...
const m3 = 0x00ff00ff00ff00ff // etc.
const m4 = 0x0000ffff0000fffffunc OnesCount32(x uint32) int {
return int(pop8tab[x>>24] + pop8tab[x>>16&0xff] + pop8tab[x>>8&0xff] + pop8tab[x&0xff])
}func OnesCount64(x uint64) int {
const m = 1<<64 - 1
x = x>>1&(m0&m) + x&(m0&m)
x = x>>2&(m1&m) + x&(m1&m)
x = (x>>4 + x) & (m2 & m)
x += x >> 8
x += x >> 16
x += x >> 32
return int(x) & (1<<7 - 1)
}
※ Reference: math/bits/bits.go;l=102–162
従来、ビットが立っているものを計算 — Population count (popcount), Hamming Weight (counting non-zero) — は簡単に思いつくものだと、ループとシフト演算を合わせたアルゴリズムを考えつくはずです。
func popcount(x uint64) int {
count := 0
for ; x != 0; x >>= 1 {
if x&0b1 != 0 {
count++
}
}
return count
}見てわかる通り、時間的なコストが非常に大きく掛かるため実戦向きのアルゴリズムではありません。
他に考えつくものだと、シフト演算をしないように特定の範囲（例：0~255）のビットによるカウントテーブルを作成していたりもしますが、他には特定のビットを用いて、四則演算や剰余計算、シフト演算を用いてカウントしていく方法が確立していきます。
const m0 = 03333333333
const m1 = 0707070707func popcount(bits uint64) uint64 {
var count uint64 = 0
count = (bits >> 1) & m0
count = bits - count - ((count >> 1) & m0)
count = ((count + (count >> 3)) & m1) % 077
return count
}
上の例は一例で、考案された中でも剰余計算を減らしたりしたものが Hacker’s Delight で紹介されている、 bits.OnesCount64 関数の中にコメントとして記載されているものです：
// Implementation: Parallel summing of adjacent bits.
// See "Hacker's Delight", Chap. 5: Counting Bits.
// The following pattern shows the general approach:
//
// x = x>>1&(m0&m) + x&(m0&m)
// x = x>>2&(m1&m) + x&(m1&m)
// x = x>>4&(m2&m) + x&(m2&m)
// x = x>>8&(m3&m) + x&(m3&m)
// x = x>>16&(m4&m) + x&(m4&m)
// x = x>>32&(m5&m) + x&(m5&m)
// return int(x)Goの bits.OnesCount64 では、カウントの結果は64を超えることがないことを前提として、わかりやすく、また危険性がないように実装されたものとなっています。
ここまで出してきた Hacker’s Delight はオライリーか、Amazonで日本語訳のものが手に入ります。
de Bruijn Sequence / Graph
ド・ブラウン（ド・ブリューエイン）というオランダ人数学者が開発したグラフ理論で用いられることのあるものです。
ビット操作の話から急に数学者が出てきているのは、僕が数学好きだからという理由もあります（笑）。すこし先述しましたが、パフォーマンスの関心事から math/bits パッケージが提供されているため、別の bits.OnesCount64 関数以外にも最適化されたアルゴリズムが実装されています。
その最適なアルゴリズムとして bits.TrailingZeros 関数に実装されているのが de Bruijn Sequence を使った手法です。de Bruijn Sequence (de Bruijn Graph) はグラフ理論でNP困難な問題と言われているハミルトン閉路問題 (Hamiltonian path problem) を効率的な解法をもつ問題（オイラーパス問題）に帰着させることができます。
※ハミルトン閉路問題は探索するグラフの頂点数が多ければ多いほど、指数関数的に計算量が増えていくものです。
このグラフ理論の話については今回省きますが、興味のある方は勉強してみてください。
上の Wikipedia にある de Bruijn Sequence のページにも記載がある数列がGoのコードに実装されています：
// --- TrailingZeros ---// See http://supertech.csail.mit.edu/papers/debruijn.pdf
const deBruijn32 = 0x077CB531var deBruijn32tab = [32]byte{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,
}const deBruijn64 = 0x03f79d71b4ca8b09var deBruijn64tab = [64]byte{
0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4,
62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5,
63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11,
54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,
}// TrailingZeros32 returns the number of trailing zero bits in x; the result is 32 for x == 0.
func TrailingZeros32(x uint32) int {
if x == 0 {
return 32
}
// see comment in TrailingZeros64
return int(deBruijn32tab[(x&-x)*deBruijn32>>(32-5)])
}func TrailingZeros64(x uint64) int {
if x == 0 {
return 64
}
return int(deBruijn64tab[(x&-x)*deBruijn64>>(64-6)])
}
Reference: math/bits/bits.go;l=35–100
de Bruijn sequence について Kaoriya さんが別の話題で記事にしているので読んでみると理解の助けになるはずです。
おわりに
ビットの操作をコードに書く機会は少ないと思いますが、Goに実装されたコードを何かのモチベーションで読み込んでみると、面白い発見につながることが多いので、これからくる年末年始に観るものがなくなったら是非コードリーディングネタとすると良いかもしれません。
途中、自分の好物である数学を出してしまいましたが、サイエンスとエンジニアリングは切っても切り離せない関係なのは楽しいところがありますね。
それでは、年末までの残りの師走を駆け抜けていきましょう
