BUGFIX-66

Bug 25: Sparse Bit Vector A Bit Broken

This code implements a bit vector that is able to compress long runs of zero bits.
A binary tree is used. The depth of the tree is determined when the bit vector is created.
Each leaf node of the tree explicitly represents 128 bits as a pair of uint64 slice elements.
Each non-leaf node of the tree is a pair of uint64 indexes. A nonzero index points to another node.
A zero index means that all the bits within the subtree are zero.

Fix The Tiny Bug In This Go Code:

type Bits struct { dat []uint64 mid uint64 } func NewBits(n int) *Bits { var ( have = uint64(128) need = uint64(n) ) for have < need { have <<= 1 } return &Bits{ dat: []uint64{0, 0}, mid: have >> 1, } } func (b *Bits) Set(i, to int) { var ( idx = uint64(i) at = uint64(0) mid = b.mid ) for ; ; mid >>= 1 { if idx >= mid { idx -= mid at++ } if mid == 64 { bit := uint64(1) << idx if to == 0 { b.dat[at] &^= bit } else { b.dat[at] |= bit } return } down := b.dat[at] if down == 0 { if to == 0 { return } down = uint64(len(b.dat)) b.dat[at] = down b.dat = append( b.dat, 0, 0, ) } at = down } } func (b *Bits) Bit(i int) int { var ( idx = uint64(i) at = uint64(0) mid = b.mid ) for ; ; mid >>= 1 { if idx >= mid { idx -= mid at++ } at := b.dat[at] if mid == 64 { bit := at >> idx & 1 return int(bit) } else if at == 0 { return 0 } } }

To receive a hint, submit unfixed code.