Mapping bits to int

Question

I'm trying to map a uint64 array bit positions to an int array (see below). BitSet is a []uint64. Below is my code as currently setup. But I am wondering if there could be a std function in golang that can reduce this code. Other language has BitArray or other objects that makes life much easier.

So, in golang, do we have to code this? is there a better to do this?

// Indexes the index positions of '1' bits as an int array
func (b BitSet) Indexes() []int {
    // set up masks for bit ANDing
    masks := make([]uint64, _BitsPerUint64)
    for i := 0; i < _BitsPerUint64; i++ {
        masks[i] = (1 << uint(i))
    }
    // iterate bitset
    indexes := make([]int, 0, len(b)*4)
    for i := 0; i < len(b); i++ {
        for m := 0; m < _BitsPerUint64; m++ {
            if masks[m]&b[i] > 0 {
                indexes = append(indexes, i*_BitsPerUint64+m)
            }
        }
    }
    return indexes
}

Consider using [big.Int](https://godoc.org/math/big#Int) instead of writing your own type. Use [Int.BitLen](https://godoc.org/math/big#Int.BitLen) and [Int.Bit](https://godoc.org/math/big#Int.Bit) to implement Indexes(). — Charlie Tumahai, Jan 24 '19 at 05:36
There is a bitarray - see https://godoc.org/github.com/golang-collections/go-datastructures/bitarray BTW you don't need to mask just do shifts. I tried to put code here but it didn't format so see below. — Andrew W. Phillips, Jan 24 '19 at 05:46
@AndrewW.Phillips BitArray looks very good - though I did not see a NOT method or a combination that could achieve a NOT operation. Did I miss it? — Riyaz Mansoor, Jan 25 '19 at 07:05

score 2 · Accepted Answer · answered Jan 24 '19 at 05:48

2

func (b BitSet) Indexes() []int {
    retval := make([]int, 0, len(b)*64)
    for idx, value := range b {
        for i := 0; i < 64; i++ {
            if value & (1<<uint(i)) != 0 {
                retval = append(retval, idx*64 + i)
            }
        }
    }
    return retval
}

answered Jan 24 '19 at 05:48

Andrew W. Phillips

3,254
1
21
24

Quick Q: performance wise is bit shift <<1 equivalent <<60 . I ask as the iterating array can be very large – Riyaz Mansoor Jan 24 '19 at 07:17
> performance wise is bit shift <<1 equivalent <<60? < bit shift is a processor instruction which I will take the same time irrespective of how many bits you are shifting on modern processors (see https://stackoverflow.com/questions/9083743/is-bit-shifting-o1-or-on for more) – Andrew W. Phillips Jan 31 '19 at 00:18

score 0 · Answer 2 · answered Apr 01 '23 at 15:37

Here's how I would do it with a bitmask package (I'm the author):

// returns indexes of all set bits in a bitmask
func indexes(bm *BitMask) []int {
    indexes := make([]int, 0, bm.len)
    it := bm.Iterator()
    for {
        ok, isSet, index := it.Next()
        if !ok {
            break
        }
        // use the value
        if isSet {
            indexes = append(indexes, int(index))
        }
    }
    return indexes
}

Mapping bits to int

2 Answers2