// Convenience function: return two bitsets ordered by
// increasing length. Note: neither can be nil
764530
func sortByLength(a *BitSet, b *BitSet) (ap *BitSet, bp *BitSet) {
	if a.length <= b.length {
		ap, bp = a, b
	} else {
		ap, bp = b, a
	}
	return
}
540450
func (b *BitSet) SymmetricDifference(compare *BitSet) (result *BitSet) {
	panicIfNull(b)
	panicIfNull(compare)
	b, compare = sortByLength(b, compare)
	// compare is bigger, so clone it
	result = compare.Clone()
	for i, word := range b.set {
		result.set[i] = word ^ compare.set[i]
	}
	return
}
1026358
func bitsetEncodeBytes(data []byte) []byte {
	// Empty slices get compressed to nil
	if len(data) == 0 {
		return nil
	}
	// One byte slices compress to nil or retain the single byte
	if len(data) == 1 {
		if data[0] == 0 {
			return nil
		}
		return data
	}
	// Calculate the bitset of set bytes, and gather the non-zero bytes
	nonZeroBitset := make([]byte, (len(data)+7)/8)
	nonZeroBytes := make([]byte, 0, len(data))

	for i, b := range data {
		if b != 0 {
			nonZeroBytes = append(nonZeroBytes, b)
			nonZeroBitset[i/8] |= 1 << byte(7-i%8)
		}
	}
	if len(nonZeroBytes) == 0 {
		return nil
	}
	return append(bitsetEncodeBytes(nonZeroBitset), nonZeroBytes...)
}
642035
func (b *Bitset) Append(other *Bitset) {
	b.ensureCapacity(other.numBits)

	for i := 0; i < other.numBits; i++ {
		if other.At(i) {
			b.bits[b.numBits/8] |= 0x80 >> uint(b.numBits%8)
		}
		b.numBits++
	}
}
1274320
func (s *Subnet) Bits() (ones int, zeros int) {
	for _, b := range []byte(s.mask) {
		for i := uint(0); i < 8; i++ {
			if b&(1<<i) == 0 {
				zeros++
			} else {
				ones++
			}
		}
	}
	return
}
1042765
func SliceShiftRight(s1 []byte, bits uint) []byte {
	l := len(s1)
	s := make([]byte, l)

	r := bits / 8
	rs := bits - r*8

	for i := 0; i < l; i++ {
		// relative index
		ri := i - int(r)
		bl := byte(0)
		if ri >= 1 {
			bl = s1[ri-1] << (8 - rs)
		}

		bu := byte(0)
		if ri >= 0 {
			bu = s1[ri] >> rs
		}
		s[i] = bl | bu
	}

	return s
}
1174756
func (b *OpenBitSet) NextSetBit(index int64) int64 {
	assert(index >= 0)
	i := int(uint64(index) >> 6)
	if i >= b.wlen {
		return -1
	}
	subIndex := int(index & 0x3f)                      // index within the word
	word := int64(uint64(b.bits[i]) >> uint(subIndex)) // skip all the bits to the right of index

	if word != 0 {
		return (int64(i) << 6) + int64(subIndex) + int64(NumberOfTrailingZeros(word))
	}

	for i++; i < b.wlen; i++ {
		word = b.bits[i]
		if word != 0 {
			return (int64(i) << 6) + int64(NumberOfTrailingZeros(word))
		}
	}

	return -1
}
1346520
func (s *Bitset) Diff(b *Bitset) *Bitset {
	return s.bitsetOp(
		b,

		func(s, b *Bitset, length *uint) {
			if *length > s.Length(0) {
				*length = s.Length(0)
			} else {
				b.unsetTop()
			}
		},

		func(s, b *Bitset, index uint) {
			s.set[index] &= ^b.set[index]
		},
	)
}
575696
func DecodeBitsString(s string, bits int) ([]byte, error) {
	if bits < 0 {
		return nil, errors.New("cannot decode a negative bit count")
	}
	return decodeString(s, bits)
}
1193990
func NewBitSet(size int) (bs *BitSet) {
	bs = &BitSet{}
	bs.size = size
	if size%8 == 0 {
		bs.set = make([]uint8, size/8)
	} else {
		bs.set = make([]uint8, (size/8)+1)
	}
	return
}
907131
func (b *BitSet) NextSet(i uint) (uint, bool) {
	x := int(i >> log2WordSize)
	if x >= len(b.set) {
		return 0, false
	}
	w := b.set[x]
	w = w >> (i & (wordSize - 1))
	if w != 0 {
		return i + trailingZeroes64(w), true
	}
	x = x + 1
	for x < len(b.set) {
		if b.set[x] != 0 {
			return uint(x)*wordSize + trailingZeroes64(b.set[x]), true
		}
		x = x + 1

	}
	return 0, false
}
1109925
func Int2Bytes(v int) []byte {
	ret := make([]byte, 4)
	Int2BytesTo(v, ret)
	return ret
}
1175974
func CountBitsBytes(b []byte) int {
	c := 0
	for _, x := range b {
		c += CountBitsByte(x)
	}
	return c
}
541682
func (b *BitSet) All() bool {
	panicIfNull(b)
	return b.Count() == b.length
}
885563
func bitPos(s []byte, bit bool) int {
	for i, b := range s {
		for j, set := range toBits(b) {
			if set == bit {
				return i*8 + j
			}
		}
	}
	return -1
}
1174173
func CountBitsInt64s(b []int64) int {
	c := 0
	for _, x := range b {
		c += CountBitsInt64(x)
	}
	return c
}
1364180
func (b *BitSet) Get(o int) bool {
	bucketID := o / 8
	oInBucket := uint8(o % 8)
	if o >= b.size {
		return false
	}
	return (b.set[bucketID]&(0x1<<oInBucket))>>oInBucket == 0x1
}