How to implement a bit vector (bitset) (in Java)?

Question

Is there some good text, books, pdf or website that explains how to implement a bit vector, especially in Java?

I ask this question because I would like to make my own BitSet implementation in Java. The reason is that I want to add aditional features and tweak that cannot be done if I modify the BitSet Java class from java.util. Moreover, I want to make my own implementation so that I can use it in my open-source project without having to deal with licenses.

Thanks!

Answer 1

If you want fancy performance or other fancy features for your bit vector or bit set, then as some one already suggested, you should inherit an existing implementation of bit vector/set. Or, you may refer to some open source implementations. However, if you want to learn the mechanism of bit vector, it is rather simple. Here's an implementation as example:

class BitSet{
    private Byte[] p;

    private BitSet(){
        p = null;
    }

    public BitSet(int n){
        assert n > 0;
        p = new Byte[(n - 1) >> 3 + 1];
    }

    public BitSet Complement(){
        BitSet bs = new BitSet();
        bs.p = new Byte[p.length];
        for(int i = 0; i < p.length; i++){
            bs.p[i] = ~ p[i];
        }
        return bs;
    }

    public BitSet Union(BitSet bs2){
        assert p.length == bs2.p.length;
        BitSet bs = new BitSet();
        bs.p = new Byte[p.length];
        for(int i = 0; i < p.length; i++){
            bs.p[i] = p[i] | bs2.p[i];
        }
        return bs;
    }

    public BitSet Intersection(BitSet bs2){
        assert p.length == bs2.p.length;
        BitSet bs = new BitSet();
        bs.p = new Byte[p.length];
        for(int i = 0; i < p.length; i++){
            bs.p[i] = p[i] & bs2.p[i];
        }
        return bs;
    }
}

You may implement and add your own set-wise operation features into the above example.