ch2/ch2-06

[giscus[bot]]

ch2/ch2-06

中文版

https://gopl-zh.github.io/ch2/ch2-06.html

[zb81]

练习 2.3

package main

import (
	"fmt"
	"time"
)

// 0-255 每个数值包含的 1 的位数（八位数值）
var pc = func() (pc [256]byte) {
	for i := range pc {
		pc[i] = pc[i>>1] + byte(i&1)
	}
	return
}()

func PopCount(x uint64) int {
	return int(pc[byte(x>>(0*8))] + // 最低 8 位
		pc[byte(x>>(1*8))] +
		pc[byte(x>>(2*8))] +
		pc[byte(x>>(3*8))] +
		pc[byte(x>>(4*8))] +
		pc[byte(x>>(5*8))] +
		pc[byte(x>>(6*8))] +
		pc[byte(x>>(7*8))]) // 最高 8 位
}

func main() {
	arr := make([]int, 10000000)
	for i := range arr {
		arr[i] = i + 1
	}
	start := time.Now()
	for _, v := range arr {
		PopCount(uint64(v))
	}
	fmt.Printf("pc cost: %d ms\n", time.Since(start).Milliseconds()) // 1ms

	start = time.Now()
	for _, v := range arr {
		PopCount2(uint64(v))
	}
	fmt.Printf("loop cost: %d ms\n", time.Since(start).Milliseconds()) // 48ms

}

func PopCount2(x uint64) int {
	count := 0
	for x != 0 {
		if x&1 == 1 {
			count++
		}
		x >>= 1
	}
	return count
}

[chenchenchenmo]

go真难写，没有python好写

[SuperZ3]

package main

import (
	"fmt"
)

func main() {
	fmt.Println(PopCount(9999))
	fmt.Println(PopCountEach1(9999))
	fmt.Println(PopCountEach8(9999))
	fmt.Println(PopCount0(9999))
}

var pc [256]byte

func init() {
    for i := range pc {
        pc[i] = pc[i/2] + byte(i&1)
    }
}

// PopCount returns the population count (number of set bits) of x.
func PopCount(x uint64) int {
    return int(pc[byte(x>>(0*8))] +
        pc[byte(x>>(1*8))] +
        pc[byte(x>>(2*8))] +
        pc[byte(x>>(3*8))] +
        pc[byte(x>>(4*8))] +
        pc[byte(x>>(5*8))] +
        pc[byte(x>>(6*8))] +
        pc[byte(x>>(7*8))])
}

func PopCountEach1(x uint64) int {
	var res int
	for x > 0 {
		if x&1 > 0 {
			res++
		}
		x = x>>1
	}
	return res
}

func PopCountEach8(x uint64) int {
    var res int
	for step := 7; step >= 0; step-- {
		res += int(pc[byte(x>>(8 * step))])
	}
	return res
}

func PopCount0(x uint64) int {
	var res int
	for x > 0 {
		x &= x-1
		res++
	}
	return res
}

[Fi-tang]

onebitcount.go
'''go
package onebitcount

var onebitMap [256]byte

func init(){
for i, _ := range onebitMap{
onebitMap[i] = onebitMap[i] + byte(i & 1)
}
}

func OnebitFoundamental(x uint64) int {
return int(
onebitMap[byte(x >> ( 0 * 8))] +
onebitMap[byte(x >> ( 1 * 8))] +
onebitMap[byte(x >> ( 2 * 8))] +
onebitMap[byte(x >> ( 3 * 8))] +
onebitMap[byte(x >> ( 4 * 8))] +
onebitMap[byte(x >> ( 5 * 8))] +
onebitMap[byte(x >> ( 6 * 8))] +
onebitMap[byte(x >> ( 7 * 8))],
)
}

func Onebit23(x uint64) int {
var num int
for i := 0; i < 8; i++ {
num += int(onebitMap[byte(x >> (i * 8))])
}
return num
}

func OnebitShift24(x uint64) int {
var num int
for x != 0 {
num += int(x & 1)
x >>= 1
}
return num
}

// x & (x - 1) 能够将 x 的最后一个非 零 bit 位清零
func OnebitClear25(x uint64) int {
var count int
for x != 0 {
x = x & (x - 1)
count++
}
return count
}```
测试程序

/*
练习 2.5:
表达式 x & (x - 1) 用于将 x 的最低一个非零的 bit 位清零。
使用这个算法重写 PopCount 函数，然后比较性能

结果: 统一来说
testFoundamental: 1.378473526 s
testLoop23: 18.059520553 s
testShift24: 24.736205763 s
testClear25: 18.931325779 s

总结来说，查表最快，其次将查表写成循环的速度约等于 x & (x - 1), 最慢的是每次移动最后一位 x >>= 1 的做法
*/
package main 

import (
	"fmt"
	"onebitcount"
	"time"
)

func testFoundamental(){
	start := time.Now()
	var i uint64
	for i = 0; i < 1024 * 1024 * 1024; i++ {
		onebitcount.OnebitFoundamental(i)
	}
	fmt.Printf("testFoundamental: %vs\n", time.Since(start).Seconds())
}

func test23(){
	start := time.Now()
	var i uint64
	for i = 0; i < 1024 * 1024 * 1024; i++ {
		onebitcount.Onebit23(i)
	}
	fmt.Printf("testLoop23: %vs\n", time.Since(start).Seconds())
}

func test24(){
	start := time.Now()
	var i uint64
	for i = 0; i < 1024 * 1024 * 1024; i++ {
		onebitcount.OnebitShift24(i)
	}
	fmt.Printf("testShift24: %vs\n", time.Since(start).Seconds())
}

func test25(){
	start := time.Now()
	var i uint64
	for i = 0; i < 1024 * 1024 * 1024; i++ {
		onebitcount.OnebitClear25(i)
	}
	fmt.Printf("testClear25: %vs\n", time.Since(start).Seconds())
}

func main(){
	testFoundamental()
	test23()
	test24()
	test25()
}

文件目录结构 onebitcount / onebitcount.go
test 文件夹 test.go
使用的编译命令行
在 onebitcount 文件夹里输入

go mod init onebitcount

在 test 文件夹里输入

go build test.go

[newarabbit]

2.2
// Package main
package main

import (
"fmt"
"os"
"strconv"
)

type Meter float64
type Kilometer float64

func (m Meter) String() string { return fmt.Sprintf("%gM", m) }
func (km Kilometer) String() string { return fmt.Sprintf("%gKM", km) }

// MToKm converts a Meter temperature to Kilometer.
func MToKm(m Meter) Kilometer { return Kilometer(m * 0.001) }

func KmToM(km Kilometer) Meter { return Meter(km * 1000) }

func main() {
for _, arg := range os.Args[1:] {
t, err := strconv.ParseFloat(arg, 64)
if err != nil {
fmt.Fprintf(os.Stderr, "cf: %v\n", err)
os.Exit(1)
}
m := Meter(t)
km := Kilometer(t)
fmt.Printf("%s=%s,%s=%s\n\n", m, MToKm(m), km, KmToM(km))
}
}

[lwc18]

package main

import (
"fmt"
"time"
)

// pc[i] is the population count of i.
var pc [256]byte

func init() {
for i := range pc {
pc[i] = pc[i/2] + byte(i&1)
}
}

// PopCount1 returns the population count (number of set bits) of x.
func PopCount1(x uint64) int {
return int(pc[byte(x>>(08))] +
pc[byte(x>>(18))] +
pc[byte(x>>(28))] +
pc[byte(x>>(38))] +
pc[byte(x>>(48))] +
pc[byte(x>>(58))] +
pc[byte(x>>(68))] +
pc[byte(x>>(78))])
}

// PopCount2 returns the population count (number of set bits) of x.
func PopCount2(x uint64) int {
var count int
for x > 0 {
x = x & (x - 1)
count++
}
return count
}

func main() {
const num = 1000000000
x := uint64(1234567890)
fmt.Println(PopCount1(x))
fmt.Println(PopCount2(x))
start := time.Now()
for i := 0; i < num; i++ {
PopCount1(x)
}
elapsed := time.Since(start)
fmt.Printf("PopCount1 took %s\n", elapsed)

start = time.Now()
for i := 0; i < num; i++ {
	PopCount2(x)
}
elapsed = time.Since(start)
fmt.Printf("PopCount2 took %s\n", elapsed)

}

[allenjlma]

这段翻译不太准确。
原文是：

In Go, as in any other programming language, one builds large programs from a small set of basic constructs. Variables store values. Simple expressions are combined into larger ones with operations like addition and subtraction. Basic types are collected into aggregates like arrays and structs. Expressions are used in statements whose execution order is determined by control-flow statements like if and for. Statements are grouped into functions for isolation and reuse. Functions are gathered into source files and packages

应该翻译成：
如很多其他编程语言一样，Go语言中的大程序都是从一小组基础组件构建而来：变量存储值；简单表达式通过加法和减法等操作组合成更大的表达式；基本类型被聚合成数组和结构体；表达式被语句（statements）所使用，这些语句（statements）的执行顺序由if和for等控制流语句来决定；为了隔离和复用，语句又被组织成函数；函数又更进一步被组织成源文件和包。

[allenjlma]

简单表达式->复杂表达式->语句->函数->包; 基础数据类型->聚合体 层层递进，组成大程序

[zhaoyanggh]

func PopCountLoop(x uint64) int {
res := 0
for i := 0; i < 8; i++ {
res += int(Pc[byte(x>>(i*8))])
}
return res
}

func PopCountMove(x uint64) int {
res := 0
for x > 0 {
if x%2 == 1 {
res++
x--
}
x /= 2
}
return res
}

func PopCountClean(x uint64) int {
res := 0
for x > 0 {
x = x & (x - 1)
res++
}
return res
}

[siqi47-a]

打卡

[Apahno]

GPT时代打卡

[skyfisher]

package main

import (
"crypto/sha256"
"fmt"
)

func count(c1 [32]byte, c2 [32]byte) int {
cnt := 0
for i := 0; i < len(c1); i++ {
cnt += popcount(c1[i], c2[i])
}

return cnt

}

// 逐位进行比较
func popcount(x, y uint8) int {
c := 0
for i := 0; i < 8; i++ {
fmt.Printf("%d,%d\n", x%2, y%2)
if x%2 != y%2 {
c += 1
}
x = x >> 1
y = y >> 1
}
return c
}

func main() {
c1 := sha256.Sum256([]byte("x"))
c2 := sha256.Sum256([]byte("X"))
fmt.Printf("%x\n%x\n%t\n%T\n", c1, c2, c1 == c2, c1)
fmt.Printf("%d\n", count(c1, c2))
// Output:
// 2d711642b726b04401627ca9fbac32f5c8530fb1903cc4db02258717921a4881
// 4b68ab3847feda7d6c62c1fbcbeebfa35eab7351ed5e78f4ddadea5df64b8015
// false
// [32]uint8
}

[leolin49]

package main

import "fmt"
import "time"

var pc [256]byte = func() (p [256]byte) {
	for i := range p {
		p[i] = p[i>>1] + byte(i&1)
	}
	return
}()

func PopCount1(x uint64) int {
    return int(pc[byte(x>>(0*8))] +
        pc[byte(x>>(1*8))] +
        pc[byte(x>>(2*8))] +
        pc[byte(x>>(3*8))] +
        pc[byte(x>>(4*8))] +
        pc[byte(x>>(5*8))] +
        pc[byte(x>>(6*8))] +
        pc[byte(x>>(7*8))])
}

func PopCount2(x uint64) (cnt int) {
	for i := 0; i < 8; i++ {
		cnt += int(pc[byte(x>>(8*i))])
	}
	return
}

func PopCount3(x uint64) (cnt int) {
	for x > 0 {
		if x&1 > 0 {
			cnt++
		}
		x >>= 1
	}
	return
}

func PopCount4(x uint64) (cnt int) {
	for x > 0 {
		cnt++
		x &= x-1
	}
	return
}

func test1() {
	start := time.Now()
	var i uint64
	for i = 0; i < 1024 * 1024 * 1024; i++ {
		PopCount1(i)
	}
	fmt.Printf("test1: %vs\n", time.Since(start).Seconds())
}

func test2() {
	start := time.Now()
	var i uint64
	for i = 0; i < 1024 * 1024 * 1024; i++ {
		PopCount2(i)
	}
	fmt.Printf("test2: %vs\n", time.Since(start).Seconds())
}

func test3() {
	start := time.Now()
	var i uint64
	for i = 0; i < 1024 * 1024 * 1024; i++ {
		PopCount3(i)
	}
	fmt.Printf("test3: %vs\n", time.Since(start).Seconds())
}

func test4(){
	start := time.Now()
	var i uint64
	for i = 0; i < 1024 * 1024 * 1024; i++ {
		PopCount4(i)
	}
	fmt.Printf("test4: %vs\n", time.Since(start).Seconds())
}

func main(){
	test1()
	test2()
	test3()
	test4()
}