Go で末尾の0ビットの数を取得するのに使われている de Bruijn アルゴリズム

Go の math/bits の bits.go に、deBruijn という定数や deBruijn32tab という配列が定義されている。

// --- TrailingZeros ---

// See http://supertech.csail.mit.edu/papers/debruijn.pdf
const deBruijn32 = 0x077CB531

var 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,
}

// 略

// 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)])
}

https://cs.opensource.google/go/go/+/refs/tags/go1.21.6:src/math/bits/bits.go;l=39-87

bits.TrailingZero32 のように、受け取った値の末尾の0ビットの数を返す関数で用いられている。

コメントに書かれているとおり TrailingZero64 内のコメントを見ると、以下のとおり記載されている。

	// If popcount is fast, replace code below with return popcount(^x & (x - 1)).
	//
	// x & -x leaves only the right-most bit set in the word. Let k be the
	// index of that bit. Since only a single bit is set, the value is two
	// to the power of k. Multiplying by a power of two is equivalent to
	// left shifting, in this case by k bits. The de Bruijn (64 bit) constant
	// is such that all six bit, consecutive substrings are distinct.
	// Therefore, if we have a left shifted version of this constant we can
	// find by how many bits it was shifted by looking at which six bit
	// substring ended up at the top of the word.
	// (Knuth, volume 4, section 7.3.1)

https://cs.opensource.google/go/go/+/refs/tags/go1.21.6:src/math/bits/bits.go;l=94-104

popcount が速ければそちらに置きかえるが、ここでは de Bruijn 定数を用いた処理になっていて、その内容が説明されている。

de Bruijn アルゴリズム

de Bruijn アルゴリズムは、de Bruijn シーケンスを用いてコンピュータのワード内の1のインデックスを見つけるためのアルゴリズムで、ポイントは以下。

• 与えられたワードについて、ワード内で1のビットのうち、最下位のものだけ1で他は0に簡素化
• ハッシュ関数を用意
  • ハッシュ関数を用いてハッシュテーブルにマッピング
• de Bruijn シーケンスを用いてテーブルをルックアップ

上記を念頭に、bits.TrailingZero32 で行われている int(deBruijn32tab[(x&-x)*deBruijn32>>(32-5)]) を分解しながら見てみる。

1. x&-x: 与えられたワード(x)について、ワード内で1のビットのうち、最下位のものだけ1で他は0に簡素化
   • xに対する-xは「xの2の補数」といい、xの各ビットを反転して1を加えることで得られるもの
   • ある値の2の補数は、ある値とビット列で比較すると、最下位ビットより上位は反転したものになっている
     • 例えば、ある値のビット列が「xxxx10..00」(xは0か1で、..部分はすべて0)のとき、この値の2の補数は、各ビットを反転した「yyyy011..11」(yはxを反転したもので、..部分はすべて1)に1を加算した「yyyy100..00」(yは同様で、..部分はすべて0)
   • ある値「xxxx10..00」とその2の補数「yyyy100..00」の論理積を取ると、ある値の1のビットのうち、最下位のものだけ1で他は0に変換された値が得られる
2. (x&-x)*deBruijn32>>(32-5): ハッシュ関数
   • 先のステップにより、(x&-x)はxの1のビットのうち最下位のものだけが1で他は0に変換された値で、この1のビットのインデックスをkとおくと、この値は2^(k-1)と表わせられる
     • kが取りうる値の範囲は1〜32(xがuint32のため)
   • (x&-x)*deBruijn32 は、deBruijn32 という定数に2^(k-1)を乗算している
   • ある値に対して2のべき乗を乗算することは、ある値を指数分左シフトすることと同じ
   • なのでここでは、deBruijn32 という定数をk-1ビット分左シフトして、それを >>(32-5) つまり27ビット右シフトしている
   • deBruijn32 は、「連続する5ビットを抜き出して得られる値が32種類ある」値になっている(下位ビットで足りないものは0で補完)
     • 0x077CB531 = 00000111011111001011010100110001
     • 先頭からみると 00000, 00001, 00011, 00111, 01110, 11101, ..., 10000 となり、これらは重複がない32種類の値になっている
   • kは1〜32より、(x&-x)*deBruijn32>>(32-5) は deBruijn32 という定数を0〜31ビット分左シフトした値を27ビット右シフトするということ(これは上で見たのと同じように連続する5ビットを抜き出している)
3. deBruijn32tab[(x&-x)*deBruijn32>>(32-5)]: de Bruijn シーケンスを用いてテーブルをルックアップ
   • 先のステップにより求めた値をインデックスとして deBruijn32tab という配列にアクセスして要素を返す

debruijn32tab はハッシュテーブルで、以下の操作で構築される。インデックスは先程見た (x&-x)*deBruijn32>>(32-5) と同じで、定数 deBruijn32 をiビット左シフトして27ビット右シフトしたもの。

idx := [32]int{}
for i := 0; i < 32; i++ {
	idx[(deBruijn32<<i)>>27&31] = i
}

https://go.dev/play/p/EGHrLzw-fbW

ハッシュテーブル構築のコードのiと、アルゴリズムを見るときに置いたkは同じものを指している。そのため、ハッシュテーブルの要素は与えられたワードの最下位ビットのインデックスになっている。
これにより、与えられたワードの末尾の0ビットの数を高速に算出することができる。

参考

• http://supertech.csail.mit.edu/papers/debruijn.pdf (1998年。math/bits/bits.go のコメントに記載)
• de Bruijn sequence