Решение для упражнения Go из книги "Язык программирования Go" - PullRequest
Новая
       1

Решение для упражнения Go из книги "Язык программирования Go"

0 голосов
/ 11 октября 2019

Я начал читать книгу «Язык программирования Go» и наткнулся на упражнение 2.6.2 из главы 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 22 3 2 3 3 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 1 2 2 3 2 3 4 4 2 3 3 4 3 4 4 5 2 3 3 43 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 33 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 64 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 55 6 5 6 6 7 4 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 шага? А аргумент x в PopCount (x) - что будет продемонстрировано?

Будем благодарны за расширенный ответ!

1 Ответ

0 голосов
/ 12 октября 2019

В разделе 2.6.2 приведен код попкорна: 

// 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 добавляет это для каждого байта из 8 байтов в uint64.

Упражнения, следующие за этим разделом, просят вас реализовать различные варианты подсчета популярности и сравнить их производительность с этим фрагментом.

В частности, упражнение 2.4 спрашивает о переходе через 64-битные позиции. Для 64-битного типа int вы запускаете цикл, который повторяется 64 раза, в каждой итерации проверяется отдельный бит uint64. Он считает, что все биты, которые он видит, установлены в 1. Вы должны реализовать это и сравнить производительность.

...