grzhan
4 天前
Golang 标准库 sys.TrailingZeros64
通过 deBruijn 序列快速计算一个 64 位二进制末尾有多少个 0：
var 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,
}
const deBruijn64 = 0x03f79d71b4ca8b09
// TrailingZeros64 returns the number of trailing zero bits in x; the result is 64 for x == 0.
func TrailingZeros64(x uint64) int {
if x == 0 {
return 64
}
// 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)
return int(deBruijn64tab[(x&-x)*deBruijn64>>(64-6)])
}
-------
1. (x & -x) 会把 x 除了最低位以外的 1 都清 0
2. deBrujin64 是一个德布鲁因数，它有个重要性质：它相当于一个循环的德布鲁因序列，每个长度为 6 的二进制子串在里面恰好出现一次，也就是说这个德布鲁因数包含所有的 6 位二进制数，且通过不同次数的位移可以恰好得到。
3. x 若有 k 个 0 ， 那么 (x & -x) * deBrujin64 就相当于 deBrujin64 << k ，注意左移是会回绕的，因此 (deBrujin64 << k) >> 58 可以恰好得到 k 在 deBrujin64 中对应的六位唯一二进制子序列
4. deBrujin64tab 就是 k 与对应六位二进制子序列（数）的映射，因此可以快速找到对应的 k ，也就是末尾多少个 0
据说该方法来自 Knuth 的 The Art of Computer Programming 7.3.1 ，回头找一下再学习下。
sys.TrailingZeros64 的性能在很多 Go 运行时场景都至关重要，Golang 有很多 free-list allocator ，比如 mspan 就会用 allocCache bitmap 位图来快速定位可以分配的 free object ，所以计算这个 bitmap 末尾有多少个 0 ，就能快速找到可以被重复利用分配的 free object