From the public account: Gopher refers to north

Hey, guys, please get out of the way. It’s a big outfit.

First of all, Xu would like to thank others for their recognition, which is the motivation for me to enjoy this, and I also need to reflect on it. This is still a bit of a euphemism, but in our Sichuan dialect, the title of the previous article is real Cuo.

Old xu decided to make waves after thinking repeatedly, exclamation mark double even named “surprised! What a nice little function in Go!” . Let’s take a look at some of the smaller functions that don’t quite fit the title.

Returns the nearest integer rounded up by a/b

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

This method should be used by many people, the most typical is paging.

Determine if x is 2 to the NTH power

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

And that’s pretty easy to understand, but the only thing to notice is that x has to be greater than 0, because 0 is also true.

Up/down rounds x to a multiple of a, and a must be 2 to the NTH power

// Round x to a multiple of a; for example, if x=6 and a=4, return 8
func alignUp(x, a uintptr) uintptr {
	return (x + a - 1) &^ (a - 1)}// Round x to a multiple of a; for example, if x=6 and a=4, return 4
func alignDown(x, a uintptr) uintptr {
	return x &^ (a - 1)}Copy the code

Here again xu makes it clear that two to the NTH power is one moved n places to the left. Then in the above code ^ is the monocular operation and the bitwise is inverted, then ^ (a-1) is the operation result of all the bits are 1 except the lowest n bits are 0. The rest is a simple addition and subtraction and bitwise and.

Each part of the above code is recognized separately, but taken together, it is confused. Fortunately, xu worked hard to find a way to understand.

Let’s take x=10 and a=4. A is going to be 2 to the second power so 1 moves 2 to the left. X can be viewed as the sum of two parts, the first part X1 is 0b1000, and the second part X2 is 0b0011. The split of x is determined by shifting 1 to the left by n bits to get a, so the lowest n bit of x is x2, and x1 is x minus x2. So x1 is equal to 0b10 2 bits left, so x1 is already an integer multiple of a, and if x2 is greater than 0 then x2 plus a minus 1 is always going to move forward by 1, so x1 plus 1 or x1 is just an integer multiple of a that x is rounding up, and then the sum to the power of a minus 1 is going to zero out the lowest 2 bits and get the final result.

Having said that, I can’t write such a logic, which makes me wonder how well the big guys understand computers. Such functions are awesome, but they should be used as little as possible in real development. The first is the use of scenarios (a must be 2 to the NTH power), and the second is not easy to understand, of course, except for showmanship and installs (performance requirements are also very high).

Boolean transformation plastic

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

Copy the code

If I had written this function, a normal switch would have done the trick, but now I have a way to pretend. In particular, Hsu notes that byte slices and strings can also be converted to each other in the same way described above.

Calculates the number of bits of the least significant 0 of different types

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
}
Copy the code

Ctz8, Ctz32, and Ctz64 respectively calculate the number of unsigned 8, 32, and 64 bits whose lowest value is 0, that is, the number of bits shifted to the left of a certain number.

The function can be understood through translation, I can also deeply understand that this is a typical space for time, but to ask why I can’t answer. However, Lao Xu has found the answer for you, and the answer is hidden in this paper Using de Bruijn Sequences to Index a 1 in a Computer Word. The giants are welcome to take on the challenge, and I just want to enjoy the benefits, so until the giants finish analyzing this paper, I’ll put these functions in my favorites column for later showoffs.

Here in particular, there is a specialty, we don’t have to know everything, but we want to know that there is such a thing. This is an interface that Xu found for himself not to study this paper, and it is also one of the meanings of writing this article (in case someone mentions the Bruijn Sequences keyword, we will not appear too ignorant).

Partial functions in the Math /bits package

If anyone knows about this bag, please forgive my ignorance and just skip this section. Old xu found that the package is originated from the runtime ntz8tab variables in the file/internal/sys/intrinsics_common. Go in a comment.

// Copied from math/bits to avoid dependence.
Copy the code

As a senior CV engineer, my first reaction when I saw this sentence was that I could finally stand up straight. Appropriate Copy code is not a shame!

Math /bits: Math /bits: Math /bits: Math /bits: Bits: Math /bits

LeadingZeros(x uint) int: returns the number of x with the highest order of 0.

TrailingZeros(x uint) int: returns the number of cases where the lowest value of x is 0.

OnesCount(x uint) int: returns the number of bits in x with bits of 1.

Reverse(x uint) uint: returns x in Reverse order of bits.

Len(x uint) int: returns the number of valid bits of x (0 in the high order is not counted).

ReverseBytes(x uint) uint: Returns x in the reverse order of every 8 bits.

Escape x into the heap

// 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{}}Copy the code

Old Xu found this call in reflect.valueof and thought it was interesting at the time. Now look back again also still admire. Reading a book is a conversation with the author, and reading the source code is a conversation with the developer. Seeing this function is like seeing the Go developers battling with the compiler.

Exits the current Processor


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

Copy the code

Release the current Processor and allow other Goroutines to execute. Hsu hasn’t seen a scenario in which this function is needed in actual development, but it’s always a good idea to be aware of it.

Finally, I sincerely hope that this article can be of some help to all readers.

Note:

  1. At the time of writing, the version of GO used by the author is GO1.16.6