shock! There is such a neat little function in Go!

# Dear brothers, please clear the way, there is a large-scale show-off scene ahead.

First of all, Lao Xu would like to thank others for their recognition. This is the motivation for me to enjoy it. At the same time, I also need to reflect. This young lady is still relatively tactful, but in our Sichuan dialect, the title of the previous article is really cuo.

After thinking over and over again, Lao Xu decided to make a splash and named it with double exclamation marks: "Shocking! There is such a wonderful little function in Go! ". Let's take a look at some small functions that don't quite fit the title.

Return a/b to the nearest integer rounded up

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

There should be many people who have used this method, the most typical one is paging calculation.

Determine whether x is the nth power of 2

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

This is also quite easy to understand. The only thing to note is that x needs to be greater than 0, because the equation 0 is also established.

Round x up/down to a multiple of a, and a must be the nth power of 2

// 向上将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。剩余的部分则是一个简单的加减运算以及按位与。

上述代码分开来看每一部分都认识，合在一起就一脸懵逼了。幸运的是，经过老许的不懈努力终于找到了一种能够理解的方式。

Take x=10, a=4 as an example. a is the 2nd power of 2, that is, 1 is shifted to the left by 2 bits. x can be seen as the sum of two parts, the first part x1 is 0b1000, and the second part x2 is 0b0011. The splitting method of x is determined by shifting n bits to the left by 1 to get a, that is, the lowest n bits of x are x2, and x1 is x-x2. Therefore, x1 is equivalent to 0b10 shifted left by 2 bits, that is, x1 is already an integer multiple of a. At this time, as long as x2 is greater than 0, x2 a-1 will definitely move forward by 1, x1 1 or x1 Isn’t it just an integer multiple of a that is rounded up by x? Finally, perform an AND operation with ^ (a - 1) to clear the lowest 2 bits to get the final return result.

One thing to say, I definitely cannot write such logic, which also makes me have to lament that the big guys have such a superb understanding of computers. Such a function is awesome, but it should be used as little as possible in actual development. One is that there are restrictions on usage scenarios (a must be the nth power of 2), and the other is that it is difficult to understand, except for showing off skills and showing off (except for extremely high performance requirements).

Boolean to integer

// 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执行。在实际的开发当中老许还未遇到需要使用此函数的场景，但多了解总是有备无患。

The above is the detailed content of shock! There is such a neat little function in Go!. For more information, please follow other related articles on the PHP Chinese website!