Jak zaimplementować wektor bitowy (bitset) (w Javie)?

Question

Czy jest jakiś dobry tekst, książki, pdf lub strona internetowa, która wyjaśnia, jak zaimplementować wektor bitowy, szczególnie w Javie?

Zadaję to pytanie, ponieważ chciałbym stworzyć własną implementację BitSet w Javie. Powodem jest to, że chcę dodać dodatkowe funkcje i ulepszenia, których nie da się zrobić, jeśli zmodyfikuję klasę Java BitSet z java.util. Co więcej, chcę stworzyć własną implementację, aby móc jej używać w moim projekcie open source bez konieczności zajmowania się licencjami.

Dzięki!

Answer 1

Jeśli chcesz uzyskać fantazyjną wydajność lub inne ciekawe funkcje dla wektora bitów lub zestawu bitów, to jak już zasugerowano, powinieneś dziedziczyć istniejącą implementację wektora/zestawu bitów. Lub możesz odwoływać się do niektórych implementacji open source. Jednakże, jeśli chcesz nauczyć się mechanizmu wektora bitów, jest to raczej proste. Oto przykład wykonania:

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

Możesz wdrożyć i dodać własne funkcje ustawiania operacji w powyższym przykładzie.

Answer 2

Szybkie wdrożenie do Twoich wymagań. Mam nadzieję, że to pomoże.

public class BitSet 
    { 
     int[] numbers; 
     public BitSet(int k){ 
      numbers = new int[(k >> 5) + 1]; 
     } 
     public void set(int k) 
     { 
      int remender = k & 0x1F; 
      int devide = k >> 5; 
      result[devide] = result[devide] | (1<<remender); 
     } 

     public void unset(int k) 
     { 
      int remender = k & 0x1F; 
      int devide = k >> 5; 
      result[devide] = result[devide] & (~(1<<remender)); 
     } 

     public boolean isSet(int k) 
     { 
      int remender = k & 0x1F; 
      int devide = k >> 5; 
      return (result[devide] & (1<<remender))!=0; 
     } 
    }