func (h *Plus) decodeHash(k uint32) (uint32, uint8) {
	var r uint8
	if k&1 == 1 {
		r = uint8(bextr32(k, 1, 6)) + h.pp - h.p
	} else {
		r = uint8(bits.LeadingZeros32(k<<(32-h.pp+h.p-1)) + 1)
	}
	return h.getIndex(k), r
}
Decode a hash from the sparse representation.
package hll
import (
	"encoding/binary"
	"errors"
	"fmt"
	"math"
	"sort"
	"github.com/cespare/xxhash"
	"github.com/influxdata/influxdb/pkg/bits"
	"github.com/influxdata/influxdb/pkg/estimator"
)
const version uint8 = 2
const DefaultPrecision = 16
func beta(ez float64) float64 {
	zl := math.Log(ez + 1)
	return -0.37331876643753059*ez +
		-1.41704077448122989*zl +
		0.40729184796612533*math.Pow(zl, 2) +
		1.56152033906584164*math.Pow(zl, 3) +
		-0.99242233534286128*math.Pow(zl, 4) +
		0.26064681399483092*math.Pow(zl, 5) +
		-0.03053811369682807*math.Pow(zl, 6) +
		0.00155770210179105*math.Pow(zl, 7)
}
type Plus struct {
	hash func([]byte) uint64
	p  uint8  
	pp uint8  
	m  uint32  
	mp uint32  
	alpha float64  
	sparse bool  
	tmpSet set
	denseList  []uint8          
	sparseList *compressedList  
}
func NewPlus(p uint8) (*Plus, error) {
	if p > 18 || p < 4 {
		return nil, errors.New("precision must be between 4 and 18")
	}
	pp := uint8(25)
	hll := &Plus{
		hash:   xxhash.Sum64,
		p:      p,
		pp:     pp,
		m:      1 << p,
		mp:     1 << pp,
		tmpSet: set{},
		sparse: true,
	}
	hll.sparseList = newCompressedList(int(hll.m))
	switch hll.m {
	case 16:
		hll.alpha = 0.673
	case 32:
		hll.alpha = 0.697
	case 64:
		hll.alpha = 0.709
	default:
		hll.alpha = 0.7213 / (1 + 1.079/float64(hll.m))
	}
	return hll, nil
}
func NewDefaultPlus() *Plus {
	p, err := NewPlus(DefaultPrecision)
	if err != nil {
		panic(err)
	}
	return p
}
func MustNewPlus(p uint8) *Plus {
	hll, err := NewPlus(p)
	if err != nil {
		panic(err)
	}
	return hll
}
func (h *Plus) Clone() *Plus {
	var hll = &Plus{
		hash:       h.hash,
		p:          h.p,
		pp:         h.pp,
		m:          h.m,
		mp:         h.mp,
		alpha:      h.alpha,
		sparse:     h.sparse,
		tmpSet:     h.tmpSet.Clone(),
		sparseList: h.sparseList.Clone(),
	}
	hll.denseList = make([]uint8, len(h.denseList))
	copy(hll.denseList, h.denseList)
	return hll
}
func (h *Plus) Add(v []byte) {
	x := h.hash(v)
	if h.sparse {
		h.tmpSet.add(h.encodeHash(x))
		if uint32(len(h.tmpSet))*100 > h.m {
			h.mergeSparse()
			if uint32(h.sparseList.Len()) > h.m {
				h.toNormal()
			}
		}
	} else {
		i := bextr(x, 64-h.p, h.p)  
		w := x<<h.p | 1<<(h.p-1)    
		rho := uint8(bits.LeadingZeros64(w)) + 1
		if rho > h.denseList[i] {
			h.denseList[i] = rho
		}
	}
}
func (h *Plus) Count() uint64 {
	if h == nil {
		return 0  
	}
	if h.sparse {
		h.mergeSparse()
		return uint64(h.linearCount(h.mp, h.mp-uint32(h.sparseList.count)))
	}
	sum := 0.0
	m := float64(h.m)
	var count float64
	for _, val := range h.denseList {
		sum += 1.0 / float64(uint32(1)<<val)
		if val == 0 {
			count++
		}
	}
	return uint64((h.alpha * m * (m - count) / (beta(count) + sum)) + 0.5)
}
func (h *Plus) Merge(s estimator.Sketch) error {
	if s == nil {
		return nil
	}
	other, ok := s.(*Plus)
	if !ok {
		return fmt.Errorf("wrong type for merging: %T", other)
	}
	if h.p != other.p {
		return errors.New("precisions must be equal")
	}
	if h.sparse {
		h.toNormal()
	}
	if other.sparse {
		for k := range other.tmpSet {
			i, r := other.decodeHash(k)
			if h.denseList[i] < r {
				h.denseList[i] = r
			}
		}
		for iter := other.sparseList.Iter(); iter.HasNext(); {
			i, r := other.decodeHash(iter.Next())
			if h.denseList[i] < r {
				h.denseList[i] = r
			}
		}
	} else {
		for i, v := range other.denseList {
			if v > h.denseList[i] {
				h.denseList[i] = v
			}
		}
	}
	return nil
}
func (h *Plus) MarshalBinary() (data []byte, err error) {
	if h == nil {
		return nil, nil
	}
	data = append(data, version)
	data = append(data, byte(h.p))
	if h.sparse {
		data = append(data, byte(1))
		tsdata, err := h.tmpSet.MarshalBinary()
		if err != nil {
			return nil, err
		}
		data = append(data, tsdata...)
		sdata, err := h.sparseList.MarshalBinary()
		if err != nil {
			return nil, err
		}
		return append(data, sdata...), nil
	}
	data = append(data, byte(0))
	sz := len(h.denseList)
	data = append(data, []byte{
		byte(sz >> 24),
		byte(sz >> 16),
		byte(sz >> 8),
		byte(sz),
	}...)
	for i := 0; i < len(h.denseList); i++ {
		data = append(data, byte(h.denseList[i]))
	}
	return data, nil
}
func (h *Plus) UnmarshalBinary(data []byte) error {
	if len(data) < 12 {
		return fmt.Errorf("provided buffer %v too short for initializing HLL sketch", data)
	}
	_ = data[0]
	p := uint8(data[1])
	newh, err := NewPlus(p)
	if err != nil {
		return err
	}
	*h = *newh
	if data[2] == byte(1) {
		h.sparse = true
		tssz := binary.BigEndian.Uint32(data[3:7])
		h.tmpSet = make(map[uint32]struct{}, tssz)
		tsLastByte := int((tssz * 4) + 7)
		for i := 7; i < tsLastByte; i += 4 {
			k := binary.BigEndian.Uint32(data[i : i+4])
			h.tmpSet[k] = struct{}{}
		}
		return h.sparseList.UnmarshalBinary(data[tsLastByte:])
	}
	h.sparse = false
	dsz := int(binary.BigEndian.Uint32(data[3:7]))
	h.denseList = make([]uint8, 0, dsz)
	for i := 7; i < dsz+7; i++ {
		h.denseList = append(h.denseList, uint8(data[i]))
	}
	return nil
}
func (h *Plus) mergeSparse() {
	if len(h.tmpSet) == 0 {
		return
	}
	keys := make(uint64Slice, 0, len(h.tmpSet))
	for k := range h.tmpSet {
		keys = append(keys, k)
	}
	sort.Sort(keys)
	newList := newCompressedList(int(h.m))
	for iter, i := h.sparseList.Iter(), 0; iter.HasNext() || i < len(keys); {
		if !iter.HasNext() {
			newList.Append(keys[i])
			i++
			continue
		}
		if i >= len(keys) {
			newList.Append(iter.Next())
			continue
		}
		x1, x2 := iter.Peek(), keys[i]
		if x1 == x2 {
			newList.Append(iter.Next())
			i++
		} else if x1 > x2 {
			newList.Append(x2)
			i++
		} else {
			newList.Append(iter.Next())
		}
	}
	h.sparseList = newList
	h.tmpSet = set{}
}
func (h *Plus) toNormal() {
	if len(h.tmpSet) > 0 {
		h.mergeSparse()
	}
	h.denseList = make([]uint8, h.m)
	for iter := h.sparseList.Iter(); iter.HasNext(); {
		i, r := h.decodeHash(iter.Next())
		if h.denseList[i] < r {
			h.denseList[i] = r
		}
	}
	h.sparse = false
	h.tmpSet = nil
	h.sparseList = nil
}
func (h *Plus) encodeHash(x uint64) uint32 {
	idx := uint32(bextr(x, 64-h.pp, h.pp))
	if bextr(x, 64-h.pp, h.pp-h.p) == 0 {
		zeros := bits.LeadingZeros64((bextr(x, 0, 64-h.pp)<<h.pp)|(1<<h.pp-1)) + 1
		return idx<<7 | uint32(zeros<<1) | 1
	}
	return idx << 1
}