Skip to content

Instantly share code, notes, and snippets.

@willf
Created May 11, 2011 01:47
Show Gist options
  • Save willf/965762 to your computer and use it in GitHub Desktop.
Save willf/965762 to your computer and use it in GitHub Desktop.
First implementation of bitsets
// Copyright 2011 Will Fitzgerald. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
/*
Package bitset implements bitsets.
It provides methods for making a bitset of an arbitrary
upper limit, setting and testing bit locations, and clearing
bit locations as well as the entire set.
bitsets are implmeented as arrays of uint64s, so it may be best
to limit the upper size to a multiple of 64. It is not an error
to set, test, or clear a bit within a 64 bit boundary.
Example use:
b := MakeBitSet(64000)
b.SetBit(1000)
if b.Bit(1000) {
b.ClearBit(1000)
}
*/
package bitset
// for MaxUint64
import (
"math"
)
// bitsets are arrays of uint64.
type bitset []uint64
// Make a bitset with an upper limit on size. Note this is the
// number of bits, not the number of uint64s, which is a kind of
// implementation detail.
func MakeBitSet(max_size uint) bitset {
if max_size % 64 == 0 {
s := make(bitset,max_size / 64)
s.Clear()
return s
}
s := make(bitset,max_size / 64 + 1)
s.Clear()
return s
}
/// Test whether bit i is set.
func (set bitset) Bit(i uint) bool {
return ((set[i/64] & (1<<(i%64)))!=0)
}
// Set bit i to 1
func (set bitset) SetBit(i uint) {
set[i/64]|=(1<<(i%64))
}
// Clear bit i to 0
func (set bitset) ClearBit( i uint) {
set[i/64]&=(1<<(i%64))^math.MaxUint64
}
// Clear entire bitset
func (set bitset) Clear() {
for i,_ := range set {
set[i] = 0
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment