💨
GoでPopcntしたいときはbits.OnesCount()を使う
いつも忘れるのでメモ
Standard Libraryであるmath/bitsパッケージでBit操作を行える。
Popcunt(population count)を使いたい場合はbits.OnesCount()を使う
Bit幅は8 bits, 16 bits, 32 bits, 64 bitsが使える
func OnesCount(x uint) int
func OnesCount8(x uint8) int
func OnesCount16(x uint16) int
func OnesCount32(x uint32) int
func OnesCount64(x uint64) int
bits.OnesCount()の場合、CPUが32bitsか64bitsかを判定して、OnesCount32かOnesCount64を呼出している
サンプル
package main
import (
"fmt"
"math/bits"
)
func main() {
fmt.Println(bits.OnesCount(3)) // 2
}
実装の詳細
version go1.17.3
OnesCountのBit幅指定なしの場合は、uintが32bitsか64bitsかで判別して、それに対応したOnesCountを呼び出す
func OnesCount(x uint) int {
if UintSize == 32 {
return OnesCount32(uint32(x))
}
return OnesCount64(uint64(x))
}
8bitsのPopcntは保存されているテーブルを参照する方式
func OnesCount8(x uint8) int {
return int(pop8tab[x])
}
32bitsの場合、8bitsごとに分割して、それぞれのPopcntを求め、その合計値を返す。
func OnesCount32(x uint32) int {
return int(pop8tab[x>>24] + pop8tab[x>>16&0xff] + pop8tab[x>>8&0xff] + pop8tab[x&0xff])
}
64bitsはよくあるPopcntの方式。詳しくは"Hacker's Delight"を読んで！とコメントに書いてある
func OnesCount64(x uint64) int {
// Implementation: Parallel summing of adjacent bits.
// See "Hacker's Delight", Chap. 5: Counting Bits.
// The following pattern shows the general approach:
//
// x = x>>1&(m0&m) + x&(m0&m)
// x = x>>2&(m1&m) + x&(m1&m)
// x = x>>4&(m2&m) + x&(m2&m)
// x = x>>8&(m3&m) + x&(m3&m)
// x = x>>16&(m4&m) + x&(m4&m)
// x = x>>32&(m5&m) + x&(m5&m)
// return int(x)
//
// Masking (& operations) can be left away when there's no
// danger that a field's sum will carry over into the next
// field: Since the result cannot be > 64, 8 bits is enough
// and we can ignore the masks for the shifts by 8 and up.
// Per "Hacker's Delight", the first line can be simplified
// more, but it saves at best one instruction, so we leave
// it alone for clarity.
const m = 1<<64 - 1
x = x>>1&(m0&m) + x&(m0&m)
x = x>>2&(m1&m) + x&(m1&m)
x = (x>>4 + x) & (m2 & m)
x += x >> 8
x += x >> 16
x += x >> 32
return int(x) & (1<<7 - 1)
}
その他
github.com/hideo55/go-popcountというパッケージではハードウェアが提供しているPopcntを使える場合はハードウェアの方を使うみたい。
Discussion