// Package bits provides various constructs that work with bits package bits import ( "strconv" ) var hamming = [256]byte{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, 2, 2, 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, 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, 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, 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, 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, 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, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8} // Returns the number of raised bits in the given byte func Hamming(b byte) byte { return hamming[b] } // The Vector interface defines methods on the bit vector type Vector interface { // Retrieves the bit at the designated position Peek(uint) bool // Sets the bit at the designated position Poke(uint, bool) // Flips the bit at the designated position Flip(uint) // Returns the total number of elements supported by the vector Len() uint } // A Vector type that simply stores booleans in a slice type boolvector []bool // Retrieves the bit at the designated position func (v boolvector) Peek(pos uint) bool { return v[pos] } // Sets the bit at the designated position func (v boolvector) Poke(pos uint, val bool) { v[pos] = val } // Flips the bit at the designated position func (v boolvector) Flip(pos uint) { v[pos] = !v[pos] } // Returns the total number of elements supported by the vector func (v boolvector) Len() uint { return uint(len(v)) } func NewBool(size uint) Vector { var slice []bool = make([]bool, size) return boolvector(slice) } type vector []uint // Retrieves the bit at the designated position func (v vector) Peek(pos uint) bool { var slot, offset uint = at(pos) return (v[slot] & (1 << offset)) > 0 } // Sets the bit at the designated position func (v vector) Poke(pos uint, val bool) { var slot, offset uint = at(pos) if val { v[slot] |= (1 << offset) } else { v[slot] &^= (1 << offset) } } // Flips the bit at the designated position func (v vector) Flip(pos uint) { var slot, offset uint = at(pos) v[slot] ^= (1 << offset) } // Returns the total number of elements supported by the vector func (v vector) Len() uint { return uint(len(v) * strconv.IntSize) } func at(pos uint) (uint, uint) { return pos / strconv.IntSize, pos % strconv.IntSize } // Create a new bit vector sized up to the desired number of elements func NewBit(size uint) Vector { var length uint = size / strconv.IntSize if size%strconv.IntSize > 0 { // Allocate one additional slot if the desired // size is does not divide by 32/64 length++ } var slice []uint = make([]uint, length) return vector(slice) }