public interface BitVector extends RandomAccess, BooleanBigList
This interface define several operations on finite sequences of bits.
Efficient implementations, such as LongArrayBitVector
,
use approximately one bit of memory for each bit in the vector, but this is not enforced.
Operation of a bit vector are partially of boolean nature
(e.g., logical operations between vectors),
partially of languagetheoretical nature (e.g., concatenation), and
partially of settheoretical nature (e.g., asking which bits are set to one).
To accomodate all these points of view, this interface extends
BooleanList
, but also provides an
asLongSet()
method that exposes a BitSet
like view
and a asLongBigList(int)
method that provides integerlike access to
blocks of bits of given width.
Most, if not all, classical operations on bit vectors can be seen as standard
operations on these two views: for instance, the number of bits set to one is just
the number of elements of the set returned by asLongSet()
(albeit a direct count()
method
is provided, too). The standard Collection.addAll(java.util.Collection)
method
can be used to concatenate bit vectors, and sublist views
make it easy performing any kind of logical operation on subvectors.
The only caveat is that sometimes the standard interface naming clashes slightly
with standard usage: for instance, clear(long)
will not set to zero
all bits (use fill(0)
for that purpose), but rather will set the
vector length to zero. Also, add(long, int)
will not add logically a value at
the specified index, but rather will insert a new bit with the specified value at the specified
position.
The AbstractBitVector
class provides a fairly complete
abstract implementation that provides all methods except for the most
basic operations. Of course, the methods of AbstractBitVector
are
very inefficient, but implementations such as LongArrayBitVector
have their own optimised implementations.
Modifier and Type  Method and Description 

void 
add(int value)
Adds a bit with specified value at the end of this bit vector.

void 
add(long index,
boolean value)
Adds a bit with specified value at the specified index (optional operation).

void 
add(long index,
int value)
Adds a bit with specified integer value at the specified index (optional operation).

BitVector 
and(BitVector v)
Performs a logical and between this bit vector and another one, leaving the result in this vector.

BitVector 
append(BitVector bitVector)
Appends another bit vector to this bit vector.

BitVector 
append(long value,
int k)
Appends the less significant bits of a long integer to this bit vector.

LongBigList 
asLongBigList(int width)
Returns a view of this bit vector as a list of nonnegative integers of specified width.

LongSortedSet 
asLongSet()
Returns a view of this bit vector as a sorted set of long integers.

long[] 
bits()
Returns the bits in this bit vector as an array of longs, not to be modified.

void 
clear(long index)
Clears a bit in this bit vector (optional operation).

BitVector 
copy()
Returns a copy of this bit vector.

BitVector 
copy(long from,
long to)
Returns a copy of a part of this bit vector.

long 
count()
Counts the number of bits set to true in this bit vector.

boolean 
equals(BitVector v,
long from,
long to)
Checks for equality with a segment of another vector.

BitVector 
fast()
Returns a fast version of this bit vector.

void 
fill(boolean value)
Sets all bits this bit vector to the given boolean value (optional operation).

void 
fill(int value)
Sets all bits this bit vector to the given integer value (optional operation).

void 
fill(long from,
long to,
boolean value)
Fills a range of bits in this bit vector (optional operation).

void 
fill(long from,
long to,
int value)
Clears a range of bits in this bit vector (optional operation).

long 
firstOne()
Returns the position of the first bit set in this vector.

long 
firstZero()
Returns the position of the first bit unset in this vector.

void 
flip()
Flips all bits in this bit vector (optional operation).

void 
flip(long index)
Flips a bit in this bit vector (optional operation).

void 
flip(long from,
long to)
Flips a range of bits in this bit vector (optional operation).

boolean 
getBoolean(long index)
Returns the value of the specified bit.

int 
getInt(long index)
Returns the value of the specified bit as an integer.

long 
getLong(long from,
long to)
Returns the specified bit range as a long.

int 
hashCode()
Returns a hash code for this bit vector.

boolean 
isPrefix(BitVector v)
Returns true if this vector is a prefix of the specified vector.

boolean 
isProperPrefix(BitVector v)
Returns true if this vector is a proper prefix of the specified vector.

long 
lastOne()
Returns the position of the last bit set in this vector.

long 
lastZero()
Returns the position of the last bit unset in this vector.

long 
length()
Returns the number of bits in this bit vector.

BitVector 
length(long newLength)
Sets the number of bits in this bit vector.

long 
longestCommonPrefixLength(BitVector v)
Returns the length of the greatest common prefix between this and the specified vector.

long 
nextOne(long index)
Returns the position of the first bit set after the given position.

long 
nextZero(long index)
Returns the position of the first bit unset after the given position.

BitVector 
or(BitVector v)
Performs a logical or between this bit vector and another one, leaving the result in this vector.

long 
previousOne(long index)
Returns the position of the first bit set before or at the given position.

long 
previousZero(long index)
Returns the position of the first bit unset before or at the given position.

boolean 
removeBoolean(long index)
Removes a bit with specified index (optional operation).

BitVector 
replace(BitVector bitVector)
Replaces the content of this bit vector with another bit vector.

void 
set(long index)
Sets a bit in this bit vector (optional operation).

boolean 
set(long index,
boolean value)
Sets the value of the specified bit (optional operation).

void 
set(long index,
int value)
Sets the value of the specified bit as an integer (optional operation).

BitVector 
subVector(long from)
Returns a subvector view specified by initial index and running up to the end of this vector.

BitVector 
subVector(long from,
long to)
Returns a subvector view specified by initial and final index.

BitVector 
xor(BitVector v)
Performs a logical xor between this bit vector and another one, leaving the result in this vector.

addAll, addAll, addAll, addElements, addElements, getElements, indexOf, iterator, lastIndexOf, listIterator, listIterator, removeElements, subList
add, addAll, get, indexOf, lastIndexOf, remove, set, size
add, addAll, booleanIterator, contains, containsAll, rem, removeAll, retainAll, toArray, toArray, toBooleanArray, toBooleanArray
add, addAll, clear, contains, containsAll, equals, isEmpty, parallelStream, remove, removeAll, removeIf, retainAll, size, spliterator, stream, toArray
compareTo
void set(long index)
index
 the index of a bit.void clear(long index)
index
 the index of a bit.void flip(long index)
index
 the index of a bit.void fill(long from, long to, boolean value)
from
 the first index (inclusive).to
 the last index (not inclusive).value
 the value (true or false).void fill(long from, long to, int value)
from
 the first index (inclusive).to
 the last index (not inclusive).value
 the value (zero or nonzero).void fill(boolean value)
void fill(int value)
void flip(long from, long to)
from
 the first index (inclusive).to
 the last index (not inclusive).void flip()
BitVector replace(BitVector bitVector)
bitVector
 a bit vector.BitVector subVector(long from, long to)
The object returned by this method is a bit vector representing a view of this bit vector restricted to the given indices. Changes to the subvector will be reflected in the main vector.
from
 the first index (inclusive).to
 the last index (not inclusive).BitVector subVector(long from)
from
 the first index (inclusive).subVector(long, long)
LongSortedSet asLongSet()
More formally, this bit vector is infinitely extended to the
left with zeros (e.g., all bits beyond length(long)
are
considered zeroes). The resulting infinite string is interpreted as the
characteristic function of a set of integers.
Note that, in particular, the resulting string representation is
exactly that of a BitSet
.
LongBigList asLongBigList(int width)
More formally, getLong(p)
will return
the nonnegative integer defined by the bits starting at p * width
(bit 0, inclusive)
and ending at (p + 1) * width
(bit width
− 1, exclusive).
boolean getBoolean(long index)
This method is semantically equivalent to BooleanList.getBoolean(int)
,
but it gives access to long indices.
getBoolean
in interface BooleanBigList
index
 the index of a bit.int getInt(long index)
This method is a useful synonym for getBoolean(long)
.
index
 the index of a bit.long getLong(long from, long to)
Note that bit 0 of the returned long will be bit from
of this bit vector.
Implementations are invited to provide highspeed implementations for
the case in which from
is a multiple of Long.SIZE
and to
is from
+ Long.SIZE
(or less,
in case the vector length is exceeded). This behaviour make it possible to
implement highspeed hashing, copies, etc.
from
 the starting bit (inclusive).to
 the ending bit (exclusive).boolean set(long index, boolean value)
This method is semantically equivalent to BooleanList.set(int,boolean)
,
but it gives access to long indices.
set
in interface BooleanBigList
index
 the index of a bit.value
 the new value.void set(long index, int value)
This method is a useful synonym for set(long, boolean)
.
index
 the index of a bit.value
 the new value (any nonzero integer for setting the bit, zero for clearing the bit).void add(long index, boolean value)
This method is semantically equivalent to BooleanList.add(int,boolean)
,
but it gives access to long indices.
add
in interface BooleanBigList
index
 the index of a bit.value
 the value that will be inserted at position index
.boolean removeBoolean(long index)
This method is semantically equivalent to BooleanList.removeBoolean(int)
,
but it gives access to long indices.
removeBoolean
in interface BooleanBigList
index
 the index of a bit.void add(long index, int value)
This method is a useful synonym for add(long, boolean)
.
index
 the index of a bit.value
 the value that will be inserted at position index
(any nonzero integer for a true bit, zero for a false bit).void add(int value)
This method is a useful synonym for BooleanList.add(boolean)
.
value
 the new value (any nonzero integer for a true bit, zero for a false bit).BitVector append(long value, int k)
value
 a value to be appendedk
 the number of less significant bits to be added to this bit vector.BitVector append(BitVector bitVector)
bitVector
 a bit vector to be appended.long length()
If the number of bits in this vector is smaller than or equal to Integer.MAX_VALUE
, this
method is semantically equivalent to List.size()
. In any case, this method is semantically
equivalent to Size64.size64()
.
BitVector length(long newLength)
It is expected that this method will try to allocate exactly the necessary space.
If the number of bits in this vector is smaller than
or equal to Integer.MAX_VALUE
, this
method is semantically equivalent to BooleanList.size(int)
. In any case, this method is semantically
essentially equivalent to BigList.size(long)
.
long count()
BitVector and(BitVector v)
v
 a bit vector.BitVector or(BitVector v)
v
 a bit vector.BitVector xor(BitVector v)
v
 a bit vector.long firstOne()
long lastOne()
long nextOne(long index)
index
(inclusive), or 1 if no such bit exists.long previousOne(long index)
long firstZero()
long lastZero()
long nextZero(long index)
index
(inclusive), or 1 if no such bit exists.long previousZero(long index)
long longestCommonPrefixLength(BitVector v)
v
 a bit vector.boolean isPrefix(BitVector v)
v
 a bit vector.v
.boolean isProperPrefix(BitVector v)
v
 a bit vector.v
(i.e., it is a prefix but not equal).boolean equals(BitVector v, long from, long to)
v
 a bit vector.from
 the starting bit, inclusive.to
 the ending bit, not inclusive.from
..to
).BitVector copy(long from, long to)
from
 the starting bit, inclusive.to
 the ending bit, not inclusive.from
(inclusive) to bit to
(not inclusive)BitVector copy()
long[] bits()
length()
bits contain the bits of
this bit vector. The array cannot be modified.int hashCode()
Hash codes for bit vectors are defined as follows:
final long length = length(); long fullLength = length  length % Long.SIZE; long h = 0x9e3779b97f4a7c13L ^ length; for( long i = 0; i < fullLength; i += Long.SIZE ) h ^= ( h << 5 ) + getLong( i, i + Long.SIZE ) + ( h >>> 2 ); if ( length != fullLength ) h ^= ( h << 5 ) + getLong( fullLength, length ) + ( h >>> 2 ); (int)( ( h >>> 32 ) ^ h );
The last value is the hash code of the bit vector. This hashing is based on shiftaddxor hashing (M.V. Ramakrishna and Justin Zobel, “Performance in practice of string hashing functions”, Proc. of the Fifth International Conference on Database Systems for Advanced Applications, 1997, pages 215−223).
The returned value is not a highquality hash such as Jenkins's, but it can be computed very quickly; in any case, 32 bits are too few for a highquality hash to be used in largescale applications.
Important: all bit vector implementations are required to return the value defined here.
The simplest way to obtain this result is to subclass AbstractBitVector
.
hashCode
in interface Collection<Boolean>
hashCode
in class Object
BitVector fast()
Different implementations of this interface might provide different level of efficiency.
For instance, views on other data structures (e.g., strings) might implement
getLong(long, long)
efficiently on multiples of Long.SIZE
, but might
fail to provide a generic, truly efficient random access.
This method returns a (possibly immutable) bit vector with the same content as that of this bit vector. However, the returned bit vector is guaranteed to provide fast random access.