Interface BitVector
 All Superinterfaces:
BigList<Boolean>
,BooleanBigList
,BooleanCollection
,BooleanIterable
,Collection<Boolean>
,Comparable<BigList<? extends Boolean>>
,Iterable<Boolean>
,RandomAccess
,Size64
 All Known Implementing Classes:
AbstractBitVector
,AbstractBitVector.SubBitVector
,BooleanListBitVector
,LongArrayBitVector
,LongBigArrayBitVector
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 BooleanBigList
, 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, Collection.clear()
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.
To increase clarity, this interface provides methods length()
and length(long)
which have a semantics similar to Size64.size64()
and BigList.size(long)
.
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 sometimes very inefficient, but implementations such as
LongArrayBitVector
have their own optimised implementations.

Method Summary
Modifier and Type Method Description void
add(int value)
Adds a bit with specified value at the end of this bit vector.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(long value, int k)
Appends the less significant bits of a long integer to this bit vector.BitVector
append(BitVector bitVector)
Appends another bit vector 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).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 at of 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 strictly before the given position.long
previousZero(long index)
Returns the position of the first bit unset before or at the given position.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).void
set(long index, int value)
Sets the value of the specified bit as an integer (optional operation).default int
size()
Deprecated.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.Methods inherited from interface it.unimi.dsi.fastutil.booleans.BooleanBigList
add, add, addAll, addAll, addAll, addAll, addAll, addElements, addElements, get, getBoolean, getElements, indexOf, indexOf, iterator, lastIndexOf, lastIndexOf, listIterator, listIterator, remove, removeBoolean, removeElements, set, set, setElements, setElements, setElements, spliterator, subList
Methods inherited from interface it.unimi.dsi.fastutil.booleans.BooleanCollection
add, add, addAll, contains, contains, containsAll, rem, remove, removeAll, removeIf, removeIf, retainAll, toArray, toBooleanArray, toBooleanArray
Methods inherited from interface it.unimi.dsi.fastutil.booleans.BooleanIterable
forEach, forEach
Methods inherited from interface java.util.Collection
addAll, clear, containsAll, equals, isEmpty, parallelStream, removeAll, retainAll, stream, toArray, toArray, toArray
Methods inherited from interface java.lang.Comparable
compareTo

Method Details

set
void set(long index)Sets a bit in this bit vector (optional operation). Parameters:
index
 the index of a bit.

clear
void clear(long index)Clears a bit in this bit vector (optional operation). Parameters:
index
 the index of a bit.

flip
void flip(long index)Flips a bit in this bit vector (optional operation). Parameters:
index
 the index of a bit.

fill
void fill(long from, long to, boolean value)Fills a range of bits in this bit vector (optional operation). Parameters:
from
 the first index (inclusive).to
 the last index (not inclusive).value
 the value (true or false).

fill
void fill(long from, long to, int value)Clears a range of bits in this bit vector (optional operation). Parameters:
from
 the first index (inclusive).to
 the last index (not inclusive).value
 the value (zero or nonzero).

fill
void fill(boolean value)Sets all bits this bit vector to the given boolean value (optional operation). Parameters:
value
 the value (true or false).

fill
void fill(int value)Sets all bits this bit vector to the given integer value (optional operation). Parameters:
value
 the value (zero or nonzero).

flip
void flip(long from, long to)Flips a range of bits in this bit vector (optional operation). Parameters:
from
 the first index (inclusive).to
 the last index (not inclusive).

flip
void flip()Flips all bits in this bit vector (optional operation). 
replace
Replaces the content of this bit vector with another bit vector. Parameters:
bitVector
 a bit vector. Returns:
 this bit vector.

subVector
Returns a subvector view specified by initial and final index.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.
 Parameters:
from
 the first index (inclusive).to
 the last index (not inclusive).

subVector
Returns a subvector view specified by initial index and running up to the end of this vector. Parameters:
from
 the first index (inclusive). See Also:
subVector(long, long)

asLongSet
LongSortedSet asLongSet()Returns a view of this bit vector as a sorted set of long integers.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
. 
asLongBigList
Returns a view of this bit vector as a list of nonnegative integers of specified width.More formally,
getLong(p)
will return the nonnegative integer defined by the bits starting atp * width
(bit 0, inclusive) and ending at(p + 1) * width
(bitwidth
− 1, exclusive). Parameters:
width
 a bit width.

getInt
int getInt(long index)Returns the value of the specified bit as an integer.This method is a useful synonym for
BooleanBigList.getBoolean(long)
. Parameters:
index
 the index of a bit. Returns:
 the value of the specified bit as an integer (0 or 1).

getLong
long getLong(long from, long to)Returns the specified bit range as a long.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 ofLong.SIZE
andto
isfrom
+Long.SIZE
(or less, in case the vector length is exceeded). This behaviour make it possible to implement highspeed hashing, copies, etc. Parameters:
from
 the starting bit (inclusive).to
 the ending bit (exclusive). Returns:
 the long value contained in the specified bits.

set
void set(long index, int value)Sets the value of the specified bit as an integer (optional operation).This method is a useful synonym for
BooleanBigList.set(long, boolean)
. Parameters:
index
 the index of a bit.value
 the new value (any nonzero integer for setting the bit, zero for clearing the bit).

add
void add(long index, int value)Adds a bit with specified integer value at the specified index (optional operation).This method is a useful synonym for
BooleanBigList.add(long, boolean)
. Parameters:
index
 the index of a bit.value
 the value that will be inserted at positionindex
(any nonzero integer for a true bit, zero for a false bit).

add
void add(int value)Adds a bit with specified value at the end of this bit vector.This method is a useful synonym for
BooleanList.add(boolean)
. Parameters:
value
 the new value (any nonzero integer for a true bit, zero for a false bit).

append
Appends the less significant bits of a long integer to this bit vector. Parameters:
value
 a value to be appendedk
 the number of less significant bits to be added to this bit vector. Returns:
 this bit vector.

append
Appends another bit vector to this bit vector. Parameters:
bitVector
 a bit vector to be appended. Returns:
 this bit vector.

length
long length()Returns the number of bits in this bit vector.If the number of bits in this vector is smaller than or equal to
Integer.MAX_VALUE
, this method is semantically equivalent toList.size()
. In any case, this method is semantically equivalent toSize64.size64()
, but it is prefererred. Returns:
 the number of bits in this bit vector.

length
Sets the number of bits in this bit vector.It is expected that this method will try to allocate exactly the necessary space.
If the argument fits an integer, this method has the same side effects of
BooleanList.size(int)
. In any case, this method has the same side effects ofBigList.size(long)
, but it is preferred, as it has the advantage of returning this bit vector, thus making it possible to chain methods. Parameters:
newLength
 the new length in bits for this bit vector. Returns:
 this bit vector.

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

and
Performs a logical and between this bit vector and another one, leaving the result in this vector. Parameters:
v
 a bit vector. Returns:
 this bit vector.

or
Performs a logical or between this bit vector and another one, leaving the result in this vector. Parameters:
v
 a bit vector. Returns:
 this bit vector.

xor
Performs a logical xor between this bit vector and another one, leaving the result in this vector. Parameters:
v
 a bit vector. Returns:
 this bit vector.

firstOne
long firstOne()Returns the position of the first bit set in this vector. Returns:
 the first bit set, or 1 for a vector of zeroes.

lastOne
long lastOne()Returns the position of the last bit set in this vector. Returns:
 the last bit set, or 1 for a vector of zeroes.

nextOne
long nextOne(long index)Returns the position of the first bit set at of after the given position. Parameters:
index
 a bit position. Returns:
 the position of the first bit set at or after position
index
, or 1 if no such bit exists.

previousOne
long previousOne(long index)Returns the position of the first bit set strictly before the given position. Parameters:
index
 a bit position. Returns:
 the position of the first bit set strictly before position
index
, or 1 if no such bit exists.

firstZero
long firstZero()Returns the position of the first bit unset in this vector. Returns:
 the first bit unset, or 1 for a vector of ones.

lastZero
long lastZero()Returns the position of the last bit unset in this vector. Returns:
 the last bit unset, or 1 for a vector of ones.

nextZero
long nextZero(long index)Returns the position of the first bit unset after the given position. Parameters:
index
 a bit position. Returns:
 the first bit unset after position
index
(inclusive), or 1 if no such bit exists.

previousZero
long previousZero(long index)Returns the position of the first bit unset before or at the given position. Parameters:
index
 a bit position. Returns:
 the first bit unset before or at the given position, or 1 if no such bit exists.

longestCommonPrefixLength
Returns the length of the greatest common prefix between this and the specified vector. Parameters:
v
 a bit vector. Returns:
 the length of the greatest common prefix.

isPrefix
Returns true if this vector is a prefix of the specified vector. Parameters:
v
 a bit vector. Returns:
 true if this vector is a prefix of
v
.

isProperPrefix
Returns true if this vector is a proper prefix of the specified vector. Parameters:
v
 a bit vector. Returns:
 true if this vector is a proper prefix of
v
(i.e., it is a prefix but not equal).

equals
Checks for equality with a segment of another vector. Parameters:
v
 a bit vector.from
 the starting bit, inclusive.to
 the ending bit, not inclusive. Returns:
 true if this vector and v are equal in the range of positions
[
from
..to
).

copy
Returns a copy of a part of this bit vector. Parameters:
from
 the starting bit, inclusive.to
 the ending bit, not inclusive. Returns:
 a copy of the part of this bit vector going from bit
from
(inclusive) to bitto
(not inclusive)

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

bits
long[] bits()Returns the bits in this bit vector as an array of longs, not to be modified. Returns:
 an array of longs whose first
length()
bits contain the bits of this bit vector. The array cannot be modified.

hashCode
int hashCode()Returns a hash code for this bit vector.Hash codes for bit vectors are defined as follows:
final long length = length(); long fullLength = 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
. Specified by:
hashCode
in interfaceCollection<Boolean>
 Overrides:
hashCode
in classObject
 Returns:
 a hash code for this bit vector.

fast
BitVector fast()Returns a fast version of this bit vector.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 ofLong.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.
 Returns:
 a fast version of this bit vector.

size
Deprecated.Please useSize64.size64()
instead.

Size64.size64()
instead.