1

Количество бит в 64-битном целом на языке Go можно вычислить так:

package main

import "fmt"

var pc [256]byte

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

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 main() {
    fmt.Printf("x = %b, w = %d\n", 3, PopCount(3))
    fmt.Printf("x = %b, w = %d\n", 127, PopCount(127))
    fmt.Printf("x = %b, w = %d\n", 256, PopCount(256))
}

Кроме того, что я получил неправильный результат, непонятна и логика работы и некоторые правила языка.

Результат:

x = 11, w = 3
x = 1111111, w = 25
x = 100000000, w = 4

Вопросы:

  1. Что происходит в функции init()? Почему используется индекс i/2?
  2. В выражении byte(x>>1*8), видимо, значение типа uint64 преобразуется в byte, чтобы использовать его как индекс. Что при этом происходит со значением uint64-числа? Какая его часть превращается в byte?
  3. Логика работы. Как понимаю, PopCount проходит по всем байтам и суммирует число битов в каждом. Почему результат неправильный?

1 ответ 1

4

Что происходит в функции init()?

В функции init производится подсчет бит для всех чисел от 0 до 255 и занесением этого количества в массив с соответствующим индексом

Почему используется индекс i/2?

Операция деления на 2, эквивалентна сдвигу вправо на один бит. Таком образом, количество бит в числе n равно количеству бит в числе n / 2 + значение последнего бита числа n

В выражении byte(x>>1*8), видимо, значение типа uint64 преобразуется в byte, чтобы использовать его как индекс. Что при этом происходит со значением uint64-числа? Какая его часть превращается в byte?

Выражение byte(x >> n) обозначает "сдвинуть число право на n бит и у получившегося числа взять младший байт

Логика работы. Как понимаю, PopCount проходит по всем байтам и суммирует число битов в каждом. Почему результат неправильный?

Фокус в том, что в Go операторы умножения * и побитового сдвига >> имеют одинаковый приоритет, а раз так, то они выполняются в порядке следования. Т.е. выражение

x >> 2 * 8

обозначает не "сдвинуть вправо на 2*8 бит", а сдвинуть вправо на два бита, а результат умножить на 8.

Если во всех выражениях расставить скобки

pc[byte( x >> (2 * 8))]

(вначале умножаем, потом - сдвигаем), то программа начинает работать правильно.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.