algorithm - 如何实现位向量(bitset)(Java)？

Question

是否有一些很好的文本、书籍、pdf 或网站可以解释如何实现位向量，尤其是在 Java 中？

我问这个问题是因为我想用 Java 实现自己的 BitSet。原因是我想添加额外的功能和调整，如果我从 java.util 修改 BitSet Java 类则无法完成。此外，我想自己实现，这样我就可以在我的开源项目中使用它，而无需处理许可证。

谢谢!

Answer 1

如果您希望位向量或位集具有出色的性能或其他奇特的功能，那么正如有人已经建议的那样，您应该继承位向量/位集的现有实现。或者，您可以引用一些开源实现。但是，如果你想学习位向量的机制，那就比较简单了。下面是一个实现示例:

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;
    }
}

您可以在上面的示例中实现和添加您自己的集合操作功能。