Come implementare un vettore bit (bitset) (in Java)?

Question

C'è del buon testo, libri, pdf o sito web che spiega come implementare un vettore bit, specialmente in Java?

Ho fatto questa domanda perché mi piacerebbe realizzare la mia implementazione BitSet in Java. La ragione è che voglio aggiungere funzionalità aggiuntive e modifiche che non possono essere eseguite se modifico la classe BitSet Java da java.util. Inoltre, voglio realizzare la mia implementazione in modo da poterla utilizzare nel mio progetto open-source senza dover gestire licenze.

Grazie!

Answer 1

Se si desidera prestazioni di fantasia o altre caratteristiche di fantasia per il proprio vettore bit o bit impostato, come già suggerito da alcuni, è necessario ereditare un'implementazione esistente di vettore/set di bit. Oppure, puoi fare riferimento ad alcune implementazioni open source. Tuttavia, se vuoi imparare il meccanismo del vettore bit, è piuttosto semplice. Ecco un applicazione come ad esempio:

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

Si possono implementare e aggiungere il proprio funzionamento set-saggio presenta nel esempio di cui sopra.

Answer 2

Una rapida implementazione per le vostre esigenze. Spero che sia d'aiuto.

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