乐趣区

关于golang:惊Go里面居然有这样精妙的小函数

jiezi

来自公众号：Gopher 指北

各位哥麻烦腾个道，后面是大型装逼现场。


首先老许要感激别人的认同，这是我乐此不彼的能源，同时我也须要反思。这位小姐姐还是比拟婉转，但用咱们四川话来说，前一篇文章的题目是真的cuo。

老许重复思考后决定哗众取宠一波，感叹号双连取名曰“惊！Go 外面竟然有这样精妙的小函数！”。上面就让咱们来看看和题目没那么合乎的一些小函数。

返回 a / b 向上舍入最靠近的整数

func divRoundUp(n, a uintptr) uintptr {return (n + a - 1) / a
}

这个办法用过的人应该不少，最典型的就是分页计算。

判断 x 是否为 2 的 n 次幂

func isPowerOfTwo(x uintptr) bool {return x&(x-1) == 0
}

这个也挺容易了解的，惟一须要留神的是 x 须要大于 0，因为该等式 0 也是成立的。

向上 / 下将 x 舍入为 a 的倍数，且 a 必须是 2 的 n 次幂

// 向上将 x 舍入为 a 的倍数，例如：x=6，a= 4 则返回值为 8
func alignUp(x, a uintptr) uintptr {return (x + a - 1) &^ (a - 1)
}

// 向上将 x 舍入为 a 的倍数，例如：x=6，a= 4 则返回值为 4
func alignDown(x, a uintptr) uintptr {return x &^ (a - 1)
}

在这里老许再次明确一个概念， 2 的 n 次幂即为 1 左移 n 位 。而后上述代码中^ 为单目运算法按位取反，则 ^ (a - 1) 的运算后果是除了最低 n 位为 0 其余位全为 1。残余的局部则是一个简略的加减运算以及按位与。

上述代码离开来看每一部分都意识，合在一起就一脸懵逼了。侥幸的是，通过老许的不懈努力终于找到了一种可能了解的形式。

以 x=10，a=4 为例。a为 2 的 2 次幂即 1 左移 2 位。x可看作两局部之和，第一局部 x1 为 0b1000, 第二局部 x2 为0b0011。x 的拆分形式是 1 左移 n 位可失去 a 来决定的，即 x 的最低 n 位为 x2，x1 则为 x -x2。因而 x1 相当于 0b10 左移 2 位失去，即 x1 曾经是 a 的整数倍，此时 x2 只有大于 0 则 x2+a- 1 肯定会向后退 1，x1+1或 x1 不就是 x 向上舍入的 a 的整数倍嘛，最初和 ^ (a - 1) 进行与运算将最低 2 位清零失去最终的返回后果。

有一说一，我必定是写不出这样的逻辑，这也令我不得不感叹大佬们对计算机的了解几乎炉火纯青。这样的函数牛逼归牛逼，然而在理论开发中还是尽量少用。一是有应用场景的限度（a 必须为 2 的 n 次幂），二是不易了解，当然炫技和装逼除外（性能要求极高也除外）。

布尔转整形

// bool2int returns 0 if x is false or 1 if x is true.
func bool2int(x bool) int {return int(uint8(*(*uint8)(unsafe.Pointer(&x))))
}

如果让我来写这个函数，一个稀松平时的 switch 就完事儿，而当初我又多了一种装逼的套路。老许在这里特地情谊提醒，字节切片和字符串也可应用上述形式进行互相转换。

计算不同类型最低位 0 的位数

var ntz8tab = [256]uint8{0x08, ..., 0x00,}
// Ctz8 returns the number of trailing zero bits in x; the result is 8 for x == 0.
func Ctz8(x uint8) int {return int(ntz8tab[x])
}

const deBruijn32ctz = 0x04653adf

var deBruijnIdx32ctz = [32]byte{
    0, 1, 2, 6, 3, 11, 7, 16,
    4, 14, 12, 21, 8, 23, 17, 26,
    31, 5, 10, 15, 13, 20, 22, 25,
    30, 9, 19, 24, 29, 18, 28, 27,
}

// Ctz32 counts trailing (low-order) zeroes,
// and if all are zero, then 32.
func Ctz32(x uint32) int {
    x &= -x                       // isolate low-order bit
    y := x * deBruijn32ctz >> 27  // extract part of deBruijn sequence
    i := int(deBruijnIdx32ctz[y]) // convert to bit index
    z := int((x - 1) >> 26 & 32)  // adjustment if zero
    return i + z
}

const deBruijn64ctz = 0x0218a392cd3d5dbf

var deBruijnIdx64ctz = [64]byte{
    0, 1, 2, 7, 3, 13, 8, 19,
    4, 25, 14, 28, 9, 34, 20, 40,
    5, 17, 26, 38, 15, 46, 29, 48,
    10, 31, 35, 54, 21, 50, 41, 57,
    63, 6, 12, 18, 24, 27, 33, 39,
    16, 37, 45, 47, 30, 53, 49, 56,
    62, 11, 23, 32, 36, 44, 52, 55,
    61, 22, 43, 51, 60, 42, 59, 58,
}

// Ctz64 counts trailing (low-order) zeroes,
// and if all are zero, then 64.
func Ctz64(x uint64) int {
    x &= -x                       // isolate low-order bit
    y := x * deBruijn64ctz >> 58  // extract part of deBruijn sequence
    i := int(deBruijnIdx64ctz[y]) // convert to bit index
    z := int((x - 1) >> 57 & 64)  // adjustment if zero
    return i + z
}

Ctz8、Ctz32和 Ctz64 别离计算无符号 8、32、64 位数最低位为 0 的个数，即某个数左移的位数。

函数的作用通过翻译倒是能了解，我也能粗浅的明确这是典型的空间换工夫，然而要问一句为什么我是万万答不上来的。不过老许曾经替你们找好了答案，答案就藏在这篇 Using de Bruijn Sequences to Index a 1 in a Computer Word 论文中。欢送巨佬们去挑战一下，而我只想不劳而获，那么在巨佬们剖析完这篇论文之前就让这些函数安家在我的珍藏栏里不便当前炫技。

这里特地阐明，术业有专攻，咱们不肯定要所有货色都会，但要尽可能晓得有这么一个货色存在。这即是老许为本人找的一个不去钻研此论文的接口，也是写下此篇文章的意义之一（万一有人提到了 Bruijn Sequences 关键词，咱们也不至于显得过分无知）。

math/bits 包中的局部函数

如果有人晓得这个包，那请原谅我的无知间接跳过本局部即可。老许发现这个包是源于 ntz8tab 变量所在文件 runtime/internal/sys/intrinsics_common.go 中的一句正文。

// Copied from math/bits to avoid dependence.

作为一个资深的 CV 工程师，看到这句的第一反馈就是我终于能够挺直腰杆了。适当 Copy 代码不丢人！

math/bits这个包函数较多，老许挑几个介绍即可，其余的还请各位读者自行开掘。

LeadingZeros(x uint) int: 返回 x 所有高位为 0 的个数。

TrailingZeros(x uint) int: 返回 x 最低位为 0 的个数。

OnesCount(x uint) int：返回 x 中 bit 位为 1 的个数。

Reverse(x uint) uint: 将 x 按 bit 位倒序后再返回。

Len(x uint) int: 返回示意 x 的无效 bit 位个数（高位中的 0 不计数）。

ReverseBytes(x uint) uint: 将 x 依照每 8 位一组倒序后返回。

将 x 逃逸至堆

// Dummy annotation marking that the value x escapes,
// for use in cases where the reflect code is so clever that
// the compiler cannot follow.
func escapes(x interface{}) {
    if dummy.b {dummy.x = x}
}

var dummy struct {
    b bool
    x interface{}}

老许是在 reflect.ValueOf 函数中发现此函数的调用，过后就觉着挺有意思。现在再次回顾也仍旧拜服不已。读书是和作者的对话，浏览源码是和开发者的对话，看到此函数就好像看到 Go 语言开发者们和编译器斗智斗勇的场景。

让出以后 Processor


// Gosched yields the processor, allowing other goroutines to run. It does not
// suspend the current goroutine, so execution resumes automatically.
func Gosched() {checkTimeouts()
    mcall(gosched_m)
}

让出以后的 Processor，容许其余 goroutine 执行。在理论的开发当中老许还未遇到须要应用此函数的场景，但多理解总是有恃无恐。

最初，衷心希望本文可能对各位读者有肯定的帮忙。

注：

  1. 写本文时，笔者所用 go 版本为: go1.16.6
退出移动版