go - 《 Go编程语言》一书中的Go练习解决方案

Question

我已经开始阅读“Go编程语言”这本书，并从第2章关于按位操作的练习2.6.2开始。我完全不了解这项任务。因此，从书“... PopCount返回设置的位数为1”。什么意思init()函数返回以下内容:

var pc [256]byte

func init() {
    for i := range pc {
        pc[i] = pc[i/2] + byte(i&1)
        fmt.Printf("%d ", pc[i])
    }
}

0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 1 2 2 3 2 3 3 4 4 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 1 2 2 3 2 3 3 4 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 4 5 3 4 4 5 4 5 5 6 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 1 2 2 3 2 3 3 4 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 7 5 5 6 5 6 6 7 5 6 6 7 6 7 7 8

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

从本书“...使用init()初步计算所有可能的8位值的结果表”。请给我解释一下此操作。下一位作者写了约64个步骤...他的意思是？什么是64步？在PopCount(x)中使用参数x-将演示什么？

将不胜感激!

Answer 1

第2.6.2节列出了popcount代码:

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

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

这是一个优化的版本。 init为每个可能的字节建立填充计数(二进制表示的位数设置为1的位数)的查找表，并且PopCount将uint64的8个字节中的每个字节加起来。

本节后面的练习要求您实现弹出计数的不同变体，并将其效果与该片段进行比较。

具体而言，练习2.4询问如何在64位位置上移位。给定一个64位的int，您运行一个循环，该循环迭代64次，在每次迭代中检查uint64的不同位。它会将看到的所有位都计数为1。您应该实现它并比较性能。