Sto rappresentando l'insieme di alfabeti inglesi come una stringa di bit a 26 bit. Il primo bit corrisponde a 'a', il bit impostato a 'b' e così via. Così,
La stringa di ab è rappresentato come 11000000000000000000000000
Ora, dato due stringhe di bit, voglio verificare se stringa di bit 1 è un sottoinsieme di stringa di bit 2. Che è, in tutti i luoghi stringa di bit 1 ha un '1', po la stringa 2 dovrebbe anche avere un '1'. Ciò significa che tutti i caratteri in stringa1 sono presenti anche in stringa2. Qualcuno può per favore farmi sapere il modo migliore per farlo?
Conosco un modo semplice come segue: iterare attraverso il bit string1 e controllare il bit corrispondente nel bit string2. Tuttavia, mi chiedo se questo può essere fatto utilizzando alcuni po 'operatore di saggio in modo più efficienteStringhe di bit: verifica se una bit-string è un sottoinsieme di un'altra
risposta
Se davvero si utilizza solo 26 bit, è possibile utilizzare un numero intero (32 bit) per rappresentare il bitset, e utilizzare l'operatore bitwise AND (&), per ottenere il intersection dei due set.
Se a & b == a
, a
è un sottoinsieme di b
Se si sarebbe utilizzando BitSet
invece di byte
, è possibile utilizzare il and
o xor
operatori.
BitSet
ha varie operazioni di bit, ad eccezione di shift
, sfortunatamente.
http://docs.oracle.com/javase/1.4.2/docs/api/java/util/BitSet.html#xor%28java.util.BitSet%29
primo set xor
seconda serie dovrebbe essere 0.
Dal momento che si usa solo 26 caratteri, si può fare lo stesso con un semplice int
, anche. Basta impostare i singoli bit è un po 'più disordinata:
a |= 1 << offset;
questo controlla per l'uguaglianza, non sottoinsieme! – TimeToCodeTheRoad
Per l'uso secondario 'a e b = a', per l'uguaglianza' a xor b = 0'. –
Come è memorizzato, come 'STRING' o come valore integrale (' Integer') che occupa i primi 26 bit? Se quest'ultimo, le operazioni bitwise semplici dovrebbero fare il trucco, altrimenti più complicato .. – Nim