|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectjava.util.BitSet
public class BitSet
This class can be thought of in two ways. You can see it as a
vector of bits or as a set of non-negative integers. The name
BitSet
is a bit misleading.
It is implemented by a bit vector, but its equally possible to see
it as set of non-negative integer; each integer in the set is
represented by a set bit at the corresponding index. The size of
this structure is determined by the highest integer in the set.
You can union, intersect and build (symmetric) remainders, by
invoking the logical operations and, or, andNot, resp. xor.
This implementation is NOT synchronized against concurrent access from
multiple threads. Specifically, if one thread is reading from a bitset
while another thread is simultaneously modifying it, the results are
undefined.
Constructor Summary | |
---|---|
BitSet()
Create a new empty bit set. |
|
BitSet(int nbits)
Create a new empty bit set, with a given size. |
Method Summary | |
---|---|
void |
and(BitSet bs)
Performs the logical AND operation on this bit set and the given set . |
void |
andNot(BitSet bs)
Performs the logical AND operation on this bit set and the complement of the given bs . |
int |
cardinality()
Returns the number of bits set to true. |
void |
clear()
Sets all bits in the set to false. |
void |
clear(int pos)
Removes the integer pos from this set. |
void |
clear(int from,
int to)
Sets the bits between from (inclusive) and to (exclusive) to false. |
Object |
clone()
Create a clone of this bit set, that is an instance of the same class and contains the same elements. |
boolean |
equals(Object obj)
Returns true if the obj is a bit set that contains
exactly the same elements as this bit set, otherwise false. |
void |
flip(int index)
Sets the bit at the index to the opposite value. |
void |
flip(int from,
int to)
Sets a range of bits to the opposite value. |
boolean |
get(int pos)
Returns true if the integer bitIndex is in this bit
set, otherwise false. |
BitSet |
get(int from,
int to)
Returns a new BitSet composed of a range of bits from
this one. |
int |
hashCode()
Returns a hash code value for this bit set. |
boolean |
intersects(BitSet set)
Returns true if the specified BitSet and this one share at least one common true bit. |
boolean |
isEmpty()
Returns true if this set contains no true bits. |
int |
length()
Returns the logical number of bits actually used by this bit set. |
int |
nextClearBit(int from)
Returns the index of the next false bit, from the specified bit (inclusive). |
int |
nextSetBit(int from)
Returns the index of the next true bit, from the specified bit (inclusive). |
void |
or(BitSet bs)
Performs the logical OR operation on this bit set and the given set . |
void |
set(int pos)
Add the integer bitIndex to this set. |
void |
set(int index,
boolean value)
Sets the bit at the given index to the specified value. |
void |
set(int from,
int to)
Sets the bits between from (inclusive) and to (exclusive) to true. |
void |
set(int from,
int to,
boolean value)
Sets the bits between from (inclusive) and to (exclusive) to the specified value. |
int |
size()
Returns the number of bits actually used by this bit set. |
String |
toString()
Returns the string representation of this bit set. |
void |
xor(BitSet bs)
Performs the logical XOR operation on this bit set and the given set . |
Methods inherited from class java.lang.Object |
---|
finalize, getClass, notify, notifyAll, wait, wait, wait |
Constructor Detail |
---|
public BitSet()
public BitSet(int nbits)
0
to nbits-1
.
nbits
- the initial size of the bit set
NegativeArraySizeException
- if nbits < 0Method Detail |
---|
public void and(BitSet bs)
set
. This means it builds the intersection
of the two sets. The result is stored into this bit set.
bs
- the second bit set
NullPointerException
- if bs is nullpublic void andNot(BitSet bs)
bs
. This means it
selects every element in the first set, that isn't in the
second set. The result is stored into this bit set and is
effectively the set difference of the two.
bs
- the second bit set
NullPointerException
- if bs is nullpublic int cardinality()
public void clear()
public void clear(int pos)
pos
from this set. That is
the corresponding bit is cleared. If the index is not in the set,
this method does nothing.
pos
- a non-negative integer
IndexOutOfBoundsException
- if pos < 0public void clear(int from, int to)
from
- the start range (inclusive)to
- the end range (exclusive)
IndexOutOfBoundsException
- if from < 0 || to < 0 ||
from > topublic Object clone()
clone
in class Object
Cloneable
public boolean equals(Object obj)
obj
is a bit set that contains
exactly the same elements as this bit set, otherwise false.
equals
in class Object
obj
- the object to compare to
Object.hashCode()
public void flip(int index)
index
- the index of the bit
IndexOutOfBoundsException
- if index is negativepublic void flip(int from, int to)
from
- the low index (inclusive)to
- the high index (exclusive)
IndexOutOfBoundsException
- if from > to || from < 0 ||
to < 0public boolean get(int pos)
bitIndex
is in this bit
set, otherwise false.
pos
- a non-negative integer
IndexOutOfBoundsException
- if the pos is negativepublic BitSet get(int from, int to)
BitSet
composed of a range of bits from
this one.
from
- the low index (inclusive)to
- the high index (exclusive)
IndexOutOfBoundsException
- if from > to || from < 0 ||
to < 0public int hashCode()
bits
, in such a manner that
bit k
is set in the BitSet (for non-negative values
of k
) if and only if
((k/64) < bits.length)
&& ((bits[k/64] & (1L << (bit % 64))) != 0)
Then the following definition of the hashCode method
would be a correct implementation of the actual algorithm:
public int hashCode() { long h = 1234; for (int i = bits.length-1; i >= 0; i--) { h ^= bits[i] * (i + 1); } return (int)((h >> 32) ^ h); }Note that the hash code values changes, if the set is changed.
hashCode
in class Object
Object.equals(Object)
,
System.identityHashCode(Object)
public boolean intersects(BitSet set)
set
- the set to check for intersection
NullPointerException
- if set is nullpublic boolean isEmpty()
public int length()
public int nextClearBit(int from)
from
- the start location
IndexOutOfBoundsException
- if from is negativepublic int nextSetBit(int from)
for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) { // operate on i here }
from
- the start location
IndexOutOfBoundsException
- if from is negativepublic void or(BitSet bs)
set
. This means it builds the union
of the two sets. The result is stored into this bit set, which
grows as necessary.
bs
- the second bit set
NullPointerException
- if bs is nullpublic void set(int pos)
bitIndex
to this set. That is
the corresponding bit is set to true. If the index was already in
the set, this method does nothing. The size of this structure
is automatically increased as necessary.
pos
- a non-negative integer.
IndexOutOfBoundsException
- if pos is negativepublic void set(int index, boolean value)
index
- the position to setvalue
- the value to set it to
IndexOutOfBoundsException
- if index is negativepublic void set(int from, int to)
from
- the start range (inclusive)to
- the end range (exclusive)
IndexOutOfBoundsException
- if from < 0 || from > to ||
to < 0public void set(int from, int to, boolean value)
from
- the start range (inclusive)to
- the end range (exclusive)value
- the value to set it to
IndexOutOfBoundsException
- if from < 0 || from > to ||
to < 0public int size()
public String toString()
toString
in class Object
Object.getClass()
,
Object.hashCode()
,
Class.getName()
,
Integer.toHexString(int)
public void xor(BitSet bs)
set
. This means it builds the symmetric
remainder of the two sets (the elements that are in one set,
but not in the other). The result is stored into this bit set,
which grows as necessary.
bs
- the second bit set
NullPointerException
- if bs is null
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |