public class BitVector extends PersistentObject
Individual indexed bits can be examined, set, or cleared. Subranges can
quickly be extracted, copied and replaced. Quick iteration over subranges is
provided by optimized internal iterators (forEach() methods). One
BitVector
may be used to modify the contents of another
BitVector
through logical AND, OR, XOR and other similar
operations.
All operations consider the bits 0..size()1 and nothing else. Operations involving two bitvectors (like AND, OR, XOR, etc.) will throw an IllegalArgumentException if the secondary bit vector has a size smaller than the receiver.
A BitVector is never automatically resized, but it can manually be grown or shrinked via setSize(...).
For use cases that need to store several bits per information entity, quick accessors are provided that interpret subranges as 64 bit long integers.
Why this class? Fist, boolean[] take one byte per stored bit. This class takes one bit per stored bit. Second, many applications find the semantics of java.util.BitSet not particularly helpful for their needs. Third, operations working on all bits of a bitvector are extremely quick. For example, on NT, Pentium Pro 200 Mhz, SunJDK1.2.2, java classic, for two bitvectors A,B (both much larger than processor cache), the following results are obtained.
Note that this implementation is not synchronized.
QuickBitVector
,
BitMatrix
,
BitSet
,
Serialized FormConstructor and Description 

BitVector(int size)
Constructs a bit vector that holds size bits.

BitVector(long[] bits,
int size)
You normally need not use this method.

Modifier and Type  Method and Description 

void 
and(BitVector other)
Performs a logical AND of the receiver with another bit vector (A
= A & B).

void 
andNot(BitVector other)
Clears all of the bits in receiver whose corresponding bit is set in the
other bitvector (A = A \ B).

int 
cardinality()
Returns the number of bits currently in the true state.

void 
clear()
Clears all bits of the receiver.

void 
clear(int bitIndex)
Changes the bit with index bitIndex to the "clear" (
false) state.

Object 
clone()
Cloning this
BitVector produces a new BitVector
that is equal to it. 
BitVector 
copy()
Returns a deep copy of the receiver; calls
clone() and casts
the result. 
long[] 
elements()
You normally need not use this method.

void 
elements(long[] bits,
int size)
You normally need not use this method.

boolean 
equals(Object obj)
Compares this object against the specified object.

boolean 
forEachIndexFromToInState(int from,
int to,
boolean state,
IntProcedure procedure)
Applies a procedure to each bit index within the specified range that
holds a bit in the given state.

boolean 
get(int bitIndex)
Returns from the bitvector the value of the bit with the specified index.

long 
getLongFromTo(int from,
int to)
Returns a long value representing bits of the receiver from index
from to index to.

boolean 
getQuick(int bitIndex)
Returns from the bitvector the value of the bit with the specified index;
WARNING: Does not check preconditions.

int 
hashCode()
Returns a hash code value for the receiver.

int 
indexOfFromTo(int from,
int to,
boolean state)
Returns the index of the first occurrence of the specified state.

void 
not()
Performs a logical NOT on the bits of the receiver (A = ~A).

void 
or(BitVector other)
Performs a logical OR of the receiver with another bit vector (A =
A  B).

BitVector 
partFromTo(int from,
int to)
Constructs and returns a new bit vector which is a copy of the given
range.

void 
put(int bitIndex,
boolean value)
Sets the bit with index bitIndex to the state specified by
value.

void 
putLongFromTo(long value,
int from,
int to)
Sets bits of the receiver from index
from to index
to to the bits of value . 
void 
putQuick(int bitIndex,
boolean value)
Sets the bit with index bitIndex to the state specified by
value; WARNING: Does not check preconditions.

void 
replaceFromToWith(int from,
int to,
BitVector source,
int sourceFrom)
Replaces the bits of the receiver in the given range with the bits of
another bit vector.

void 
replaceFromToWith(int from,
int to,
boolean value)
Sets the bits in the given range to the state specified by value
.

void 
set(int bitIndex)
Changes the bit with index bitIndex to the "set" (true)
state.

void 
setSize(int newSize)
Shrinks or expands the receiver so that it holds newSize bits.

int 
size()
Returns the size of the receiver.

String 
toString()
Returns a string representation of the receiver.

void 
xor(BitVector other)
Performs a logical XOR of the receiver with another bit vector (A
= A ^ B).

public BitVector(long[] bits, int size)
A bitvector is modelled as a long array, i.e. long[] bits holds bits of a bitvector. Each long value holds 64 bits. The ith bit is stored in bits[i/64] at bit position i % 64 (where bit position 0 refers to the least significant bit and 63 refers to the most significant bit).
IllegalArgumentException
 if size < 0  size > bits.length*64.public BitVector(int size)
size
 the number of bits the bit vector shall have.IllegalArgumentException
 if size < 0.public void and(BitVector other)
true
if and only if it already had the value
true
and the corresponding bit in the other bit vector
argument has the value true
.other
 a bit vector.IllegalArgumentException
 if size() > other.size().public void andNot(BitVector other)
other
 a bitvector with which to mask the receiver.IllegalArgumentException
 if size() > other.size().public int cardinality()
public void clear()
public void clear(int bitIndex)
bitIndex
 the index of the bit to be cleared.IndexOutOfBoundsException
 if bitIndex<0  bitIndex>=size()public Object clone()
BitVector
produces a new BitVector
that is equal to it. The clone of the bit vector is another bit vector
that has exactly the same bits set to true
as this bit
vector and the same current size, but independent state.clone
in class PersistentObject
public BitVector copy()
clone()
and casts
the result.public long[] elements()
A bitvector is modelled as a long array, i.e. long[] bits holds bits of a bitvector. Each long value holds 64 bits. The ith bit is stored in bits[i/64] at bit position i % 64 (where bit position 0 refers to the least significant bit and 63 refers to the most significant bit).
public void elements(long[] bits, int size)
A bitvector is modelled as a long array, i.e. long[] bits holds bits of a bitvector. Each long value holds 64 bits. The ith bit is stored in bits[i/64] at bit position i % 64 (where bit position 0 refers to the least significant bit and 63 refers to the most significant bit).
bits
 the backing bits of the bit vector.size
 the number of bits the bit vector shall hold.IllegalArgumentException
 if size < 0  size > bits.length*64.public boolean equals(Object obj)
true
if and only if the argument is not null
and is a BitVector
object that has the same size as the
receiver and the same bits set to true
as the receiver. That
is, for every nonnegative int
index k
,
((BitVector) obj).get(k) == this.get(k)must be true.
public boolean forEachIndexFromToInState(int from, int to, boolean state, IntProcedure procedure)
Optimized for speed. Particularly quick if one of the following conditions holds
from
 the leftmost search position, inclusive.to
 the rightmost search position, inclusive.state
 element to search for.procedure
 a procedure object taking as argument the current bit index.
Stops iteration if the procedure returns false,
otherwise continues.IndexOutOfBoundsException
 if (
size()>0 && (from<0  from>to  to>=size())
).public boolean get(int bitIndex)
bitIndex
 the bit index.IndexOutOfBoundsException
 if bitIndex<0  bitIndex>=size()public long getLongFromTo(int from, int to)
from
, ..., bit
tofrom
set to bit to
. All other bits of the
return value are set to 0. If tofrom+1==0 then returns zero (
0L).from
 index of start bit (inclusive).to
 index of end bit (inclusive).IndexOutOfBoundsException
 if
from<0  from>=size()  to<0  to>=size()  tofrom+1<0  tofrom+1>64public boolean getQuick(int bitIndex)
Provided with invalid parameters this method may return invalid values without throwing any exception. You should only use this method when you are absolutely sure that the index is within bounds. Precondition (unchecked): bitIndex >= 0 && bitIndex < size().
bitIndex
 the bit index.public int hashCode()
Suppose the bits in the receiver were to be stored in an array of
long
integers called, say, bits
, in such a
manner that bit k
is set in the receiver (for nonnegative
values of k
) if and only if the expression
((k >> 6) < bits.length) && ((bits[k >> 6] & (1L << (bit & 0x3F))) != 0)is true. 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; i >= 0;) { h ˆ= bits[i] * (i + 1); } return (int) ((h >> 32) ˆ h); }Note that the hash code values change if the set of bits is altered.
public int indexOfFromTo(int from, int to, boolean state)
1
if the receiver does not contain this state. Searches
between from
, inclusive and to
, inclusive.
Optimized for speed. Preliminary performance (200Mhz Pentium Pro, JDK 1.2, NT): size=10^6, from=0, to=size1, receiver contains matching state in the very end > 0.002 seconds elapsed time.
state
 state to search for.from
 the leftmost search position, inclusive.to
 the rightmost search position, inclusive.1
if the element is not found.IndexOutOfBoundsException
 if (
size()>0 && (from<0  from>to  to>=size())
).public void not()
public void or(BitVector other)
true
if and only if it either already had the value
true
or the corresponding bit in the other bit vector
argument has the value true
.other
 a bit vector.IllegalArgumentException
 if size() > other.size().public BitVector partFromTo(int from, int to)
from
 the start index within the receiver, inclusive.to
 the end index within the receiver, inclusive.IndexOutOfBoundsException
 if
size()>0 && (from<0  from>to  to>=size()))
.public void put(int bitIndex, boolean value)
bitIndex
 the index of the bit to be changed.value
 the value to be stored in the bit.IndexOutOfBoundsException
 if bitIndex<0  bitIndex>=size()public void putLongFromTo(long value, int from, int to)
from
to index
to
to the bits of value
. Bit from
is set to bit 0 of value
, ..., bit to
is set to
bit tofrom
of value
. All other bits stay
unaffected. If tofrom+1==0 then does nothing.value
 the value to be copied into the receiver.from
 index of start bit (inclusive).to
 index of end bit (inclusive).IndexOutOfBoundsException
 if
from<0  from>=size()  to<0  to>=size()  tofrom+1<0  tofrom+1>64
.public void putQuick(int bitIndex, boolean value)
Provided with invalid parameters this method may set invalid values without throwing any exception. You should only use this method when you are absolutely sure that the index is within bounds. Precondition (unchecked): bitIndex >= 0 && bitIndex < size().
bitIndex
 the index of the bit to be changed.value
 the value to be stored in the bit.public void replaceFromToWith(int from, int to, BitVector source, int sourceFrom)
Optimized for speed. Preliminary performance (200Mhz Pentium Pro, JDK 1.2, NT): replace 10^6 ill aligned bits > 0.02 seconds elapsed time.
from
 the start index within the receiver, inclusive.to
 the end index within the receiver, inclusive.source
 the source bitvector to copy from.sourceFrom
 the start index within source, inclusive.IndexOutOfBoundsException
 if
size()>0 && (from<0  from>to  to>=size()  sourceFrom<0  sourceFrom+tofrom+1>source.size()))
.public void replaceFromToWith(int from, int to, boolean value)
Optimized for speed. Preliminary performance (200Mhz Pentium Pro, JDK 1.2, NT): replace 10^6 ill aligned bits > 0.002 seconds elapsed time.
from
 the start index, inclusive.to
 the end index, inclusive.value
 the value to be stored in the bits of the range.IndexOutOfBoundsException
 if
size()>0 && (from<0  from>to  to>=size())
.public void set(int bitIndex)
bitIndex
 the index of the bit to be set.IndexOutOfBoundsException
 if bitIndex<0  bitIndex>=size()public void setSize(int newSize)
newSize
 the number of bits the bit vector shall have.IllegalArgumentException
 if size < 0.public int size()
public String toString()
public void xor(BitVector other)
true
if and only if one of the following statements holds:
true
, and the
corresponding bit in the argument has the value false
.
false
, and the
corresponding bit in the argument has the value true
.
other
 a bit vector.IllegalArgumentException
 if size() > other.size().Jump to the Parallel Colt Homepage