How to implement BitSet with Go by example?

Go: How to implement BitSet?

What is BitSet?

A BitSet is a data structure that stores a sequence of bits and supports operations like setting, clearing, flipping and checking the values of individual bits.

BitSet Example

Run This Code

package main

import "fmt"

type BitSet struct {
    data []uint64
}

func NewBitSet(size int) *BitSet {
    return &BitSet{make([]uint64, (size+63)>>6)}
}

func (set *BitSet) Set(bitIndex int) {
    idx := bitIndex >> 6
    if idx >= len(set.data) {
        return
    }
    bitMask := uint64(1) << uint(bitIndex&63)
    set.data[idx] |= bitMask
}

func (set *BitSet) Clear(bitIndex int) {
    idx := bitIndex >> 6
    if idx >= len(set.data) {
        return
    }
    bitMask := uint64(1) << uint(bitIndex&63)
    set.data[idx] &= ^bitMask
}

func (set *BitSet) Flip(bitIndex int) {
    idx := bitIndex >> 6
    if idx >= len(set.data) {
        return
    }
    bitMask := uint64(1) << uint(bitIndex&63)
    set.data[idx] ^= bitMask
}

func (set *BitSet) Get(bitIndex int) bool {
    idx := bitIndex >> 6
    if idx >= len(set.data) {
        return false
    }
    bitMask := uint64(1) << uint(bitIndex&63)
    return (set.data[idx] & bitMask) != 0
}

func main() {
    set := NewBitSet(100)
    set.Set(1)
    set.Set(2)
    set.Set(3)
    fmt.Println(set.Get(1)) // true
    fmt.Println(set.Get(2)) // true
    fmt.Println(set.Get(3)) // true
    set.Clear(2)
    fmt.Println(set.Get(2)) // false
    set.Flip(3)
    fmt.Println(set.Get(3)) // false
}

Explaination

  • Define the BitSet struct and its methods.
  • The NewBitSet function creates a new BitSet with the specified size (in bits). The Set, Clear, and Flip methods set, clear, and toggle the bit at the given index, respectively. The Get method returns the value of the bit at the given index.
  • In the main function, we create a new BitSet with 100 bits, set bits at indices 1, 2, and 3, and print their values. We then clear bit 2, flip bit 3, and print their values again.

I hope this example helps you implement BitSet in Go!