BitSet

java.lang.Object
- com.carrotsearch.hppc.BitSet

All Implemented Interfaces:

java.lang.Cloneable
```
public class BitSet
extends java.lang.Object
implements java.lang.Cloneable
```
An "open" BitSet implementation that allows direct access to the array of words storing the bits.
Unlike java.util.bitset, the fact that bits are packed into an array of longs is part of the interface. This allows efficient implementation of other algorithms by someone other than the author. It also allows one to efficiently implement alternate serialization or interchange formats.

The index range for a bitset can easily exceed positive int range in Java (0x7fffffff), so many methods in this class accept or return a long. There are adapter methods that return views compatible with LongLookupContainer and IntLookupContainer interfaces.

See Also:

asIntLookupContainer(), asLongLookupContainer()

Field Summary

Fields
Modifier and Type	Field and Description
`long[]`	`bits` Internal representation of bits in this bit set.
`private static long`	`DEFAULT_NUM_BITS` The initial default number of bits (64L).
`int`	`wlen` The number of words (longs) used in the `bits` array.

Constructor Summary

Constructors
Constructor and Description
`BitSet()` Constructs a bit set with the default capacity.
`BitSet(long numBits)` Constructs an BitSet large enough to hold numBits.
`BitSet(long[] bits, int numWords)` Constructs an BitSet from an existing long[].

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`and(BitSet other)`
`void`	`andNot(BitSet other)`
`static long`	`andNotCount(BitSet a, BitSet b)`
`IntLookupContainer`	`asIntLookupContainer()` Returns a view over this bitset data compatible with `IntLookupContainer`.
`LongLookupContainer`	`asLongLookupContainer()` Returns a view over this bitset data compatible with `LongLookupContainer`.
`static int`	`bits2words(long numBits)`
`long`	`capacity()`
`long`	`cardinality()`
`void`	`clear()` Clears all bits.
`void`	`clear(int startIndex, int endIndex)` Clears a range of bits.
`void`	`clear(long index)` clears a bit, allowing access beyond the current set size without changing the size.
`void`	`clear(long startIndex, long endIndex)` Clears a range of bits.
`java.lang.Object`	`clone()`
`void`	`ensureCapacity(long numBits)` Ensure that the long[] is big enough to hold numBits, expanding it if necessary.
`void`	`ensureCapacityWords(int numWords)` Expand the long[] with the size given as a number of words (64 bit longs).
`boolean`	`equals(java.lang.Object o)`
`protected int`	`expandingWordNum(long index)`
`void`	`flip(long index)` Flips a bit, expanding the set size if necessary.
`void`	`flip(long startIndex, long endIndex)` Flips a range of bits, expanding the set size if necessary
`boolean`	`flipAndGet(int index)` flips a bit and returns the resulting bit value.
`boolean`	`flipAndGet(long index)` flips a bit and returns the resulting bit value.
`boolean`	`get(int index)`
`boolean`	`get(long index)`
`boolean`	`getAndSet(int index)` Sets a bit and returns the previous value.
`boolean`	`getAndSet(long index)` Sets a bit and returns the previous value.
`static int`	`getNextSize(int targetSize)`
`static long[]`	`grow(long[] array, int minSize)`
`int`	`hashCode()`
`void`	`intersect(BitSet other)` this = this AND other
`static long`	`intersectionCount(BitSet a, BitSet b)`
`boolean`	`intersects(BitSet other)`
`boolean`	`isEmpty()`
`BitSetIterator`	`iterator()`
`long`	`length()`
`static BitSet`	`newInstance()` Static constructor-like method similar to other (generic) collections.
`int`	`nextSetBit(int index)`
`long`	`nextSetBit(long index)`
`void`	`or(BitSet other)`
`void`	`remove(BitSet other)` Remove all elements set in other: this = this AND_NOT other
`void`	`set(long index)` Sets a bit, expanding the set size if necessary.
`void`	`set(long startIndex, long endIndex)` Sets a range of bits, expanding the set size if necessary
`long`	`size()`
`java.lang.String`	`toString()`
`void`	`trimTrailingZeros()` Lowers `wlen`, the number of words in use, by checking for trailing zero words.
`void`	`union(BitSet other)` this = this OR other
`static long`	`unionCount(BitSet a, BitSet b)`
`void`	`xor(BitSet other)` this = this XOR other
`static long`	`xorCount(BitSet a, BitSet b)`

Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait

- Field Detail
  - DEFAULT_NUM_BITS
```
private static final long DEFAULT_NUM_BITS
```
    The initial default number of bits (64L).
    
    See Also:
    
    Constant Field Values
  - bits
```
public long[] bits
```
    Internal representation of bits in this bit set.
  - wlen
```
public int wlen
```
    The number of words (longs) used in the bits array.
- Constructor Detail
  - BitSet
```
public BitSet()
```
    Constructs a bit set with the default capacity.
  - BitSet
```
public BitSet(long numBits)
```
    Constructs an BitSet large enough to hold numBits.
    
    Parameters:
    
    numBits - Number of bits
  - BitSet
```
public BitSet(long[] bits,
              int numWords)
```
    Constructs an BitSet from an existing long[]. The first 64 bits are in long[0], with bit index 0 at the least significant bit, and bit index 63 at the most significant. Given a bit index, the word containing it is long[index/64], and it is at bit number index%64 within that word. numWords are the number of elements in the array that contain set bits (non-zero longs). numWords should be <= bits.length, and any existing words in the array at position >= numWords should be zero.
    
    Parameters:
    
    bits - underlying bits buffer
    
    numWords - the number of elements in the array that contain set bits
- Method Detail
  - newInstance
```
public static BitSet newInstance()
```
    Static constructor-like method similar to other (generic) collections.
    
    Returns:
    
    New instance.
  - iterator
```
public BitSetIterator iterator()
```
    Returns:
    
    Returns an iterator over all set bits of this bitset. The iterator should be faster than using a loop around nextSetBit(int).
  - capacity
```
public long capacity()
```
    Returns:
    
    Returns the current capacity in bits (1 greater than the index of the last bit).
  - size
```
public long size()
```
    Returns:
    
    Returns the current capacity of this set. Included for compatibility. This is not equal to cardinality().
    
    See Also:
    
    cardinality(), BitSet.size()
  - length
```
public long length()
```
    Returns:
    
    Returns the "logical size" of this BitSet: the index of the highest set bit in the BitSet plus one.
    
    See Also:
    
    BitSet.length()
  - isEmpty
```
public boolean isEmpty()
```
    Returns:
    
    Returns true if there are no set bits
  - get
```
public boolean get(int index)
```
    Parameters:
    
    index - The index.
    
    Returns:
    
    Returns true or false for the specified bit index.
  - get
```
public boolean get(long index)
```
    Parameters:
    
    index - The index.
    
    Returns:
    
    Returns true or false for the specified bit index.
  - set
```
public void set(long index)
```
    Sets a bit, expanding the set size if necessary.
    
    Parameters:
    
    index - the index to set
  - set
```
public void set(long startIndex,
                long endIndex)
```
    Sets a range of bits, expanding the set size if necessary
    
    Parameters:
    
    startIndex - lower index
    
    endIndex - one-past the last bit to set
  - expandingWordNum
```
protected int expandingWordNum(long index)
```
  - clear
```
public void clear()
```
    Clears all bits.
  - clear
```
public void clear(long index)
```
    clears a bit, allowing access beyond the current set size without changing the size.
    
    Parameters:
    
    index - the index to clear
  - clear
```
public void clear(int startIndex,
                  int endIndex)
```
    Clears a range of bits. Clearing past the end does not change the size of the set.
    
    Parameters:
    
    startIndex - lower index
    
    endIndex - one-past the last bit to clear
  - clear
```
public void clear(long startIndex,
                  long endIndex)
```
    Clears a range of bits. Clearing past the end does not change the size of the set.
    
    Parameters:
    
    startIndex - lower index
    
    endIndex - one-past the last bit to clear
  - getAndSet
```
public boolean getAndSet(int index)
```
    Sets a bit and returns the previous value. The index should be less than the BitSet size.
    
    Parameters:
    
    index - the index to set
    
    Returns:
    
    previous state of the index
  - getAndSet
```
public boolean getAndSet(long index)
```
    Sets a bit and returns the previous value. The index should be less than the BitSet size.
    
    Parameters:
    
    index - the index to set
    
    Returns:
    
    previous state of the index
  - flip
```
public void flip(long index)
```
    Flips a bit, expanding the set size if necessary.
    
    Parameters:
    
    index - the index to flip
  - flipAndGet
```
public boolean flipAndGet(int index)
```
    flips a bit and returns the resulting bit value. The index should be less than the BitSet size.
    
    Parameters:
    
    index - the index to flip
    
    Returns:
    
    previous state of the index
  - flipAndGet
```
public boolean flipAndGet(long index)
```
    flips a bit and returns the resulting bit value. The index should be less than the BitSet size.
    
    Parameters:
    
    index - the index to flip
    
    Returns:
    
    previous state of the index
  - flip
```
public void flip(long startIndex,
                 long endIndex)
```
    Flips a range of bits, expanding the set size if necessary
    
    Parameters:
    
    startIndex - lower index
    
    endIndex - one-past the last bit to flip
  - cardinality
```
public long cardinality()
```
    Returns:
    
    the number of set bits
  - intersectionCount
```
public static long intersectionCount(BitSet a,
                                     BitSet b)
```
    Parameters:
    
    a - The first set
    
    b - The second set
    
    Returns:
    
    Returns the popcount or cardinality of the intersection of the two sets. Neither set is modified.
  - unionCount
```
public static long unionCount(BitSet a,
                              BitSet b)
```
    Parameters:
    
    a - The first set
    
    b - The second set
    
    Returns:
    
    Returns the popcount or cardinality of the union of the two sets. Neither set is modified.
  - andNotCount
```
public static long andNotCount(BitSet a,
                               BitSet b)
```
    Parameters:
    
    a - The first set
    
    b - The second set
    
    Returns:
    
    Returns the popcount or cardinality of "a and not b" or "intersection(a, not(b))". Neither set is modified.
  - xorCount
```
public static long xorCount(BitSet a,
                            BitSet b)
```
    Parameters:
    
    a - The first set
    
    b - The second set
    
    Returns:
    
    Returns the popcount or cardinality of the exclusive-or of the two sets. Neither set is modified.
  - nextSetBit
```
public int nextSetBit(int index)
```
    Parameters:
    
    index - The index to start scanning from, inclusive.
    
    Returns:
    
    Returns the index of the first set bit starting at the index specified. -1 is returned if there are no more set bits.
  - nextSetBit
```
public long nextSetBit(long index)
```
    Parameters:
    
    index - The index to start scanning from, inclusive.
    
    Returns:
    
    Returns the index of the first set bit starting at the index specified. -1 is returned if there are no more set bits.
  - clone
```
public java.lang.Object clone()
```
    Overrides:
    
    clone in class java.lang.Object
  - intersect
```
public void intersect(BitSet other)
```
    this = this AND other
    
    Parameters:
    
    other - The bitset to intersect with.
  - union
```
public void union(BitSet other)
```
    this = this OR other
    
    Parameters:
    
    other - The bitset to union with.
  - remove
```
public void remove(BitSet other)
```
    Remove all elements set in other: this = this AND_NOT other
    
    Parameters:
    
    other - The other bitset.
  - xor
```
public void xor(BitSet other)
```
    this = this XOR other
    
    Parameters:
    
    other - The other bitset.
  - and
```
public void and(BitSet other)
```
  - or
```
public void or(BitSet other)
```
  - andNot
```
public void andNot(BitSet other)
```
  - intersects
```
public boolean intersects(BitSet other)
```
    Parameters:
    
    other - The other bitset.
    
    Returns:
    
    true if the sets have any elements in common
  - ensureCapacityWords
```
public void ensureCapacityWords(int numWords)
```
    Expand the long[] with the size given as a number of words (64 bit longs). getNumWords() is unchanged by this call.
    
    Parameters:
    
    numWords - The size to expand to (64-bit long words)
  - grow
```
public static long[] grow(long[] array,
                          int minSize)
```
  - getNextSize
```
public static int getNextSize(int targetSize)
```
  - ensureCapacity
```
public void ensureCapacity(long numBits)
```
    Ensure that the long[] is big enough to hold numBits, expanding it if necessary. getNumWords() is unchanged by this call.
    
    Parameters:
    
    numBits - The number of bits to expand to
  - trimTrailingZeros
```
public void trimTrailingZeros()
```
    Lowers wlen, the number of words in use, by checking for trailing zero words.
  - bits2words
```
public static int bits2words(long numBits)
```
  - equals
```
public boolean equals(java.lang.Object o)
```
    Overrides:
    
    equals in class java.lang.Object
  - hashCode
```
public int hashCode()
```
    Overrides:
    
    hashCode in class java.lang.Object
  - toString
```
public java.lang.String toString()
```
    Overrides:
    
    toString in class java.lang.Object
  - asIntLookupContainer
```
public IntLookupContainer asIntLookupContainer()
```
    Returns a view over this bitset data compatible with IntLookupContainer. A new object is always returned, but its methods reflect the current state of the bitset (the view is not a snapshot).
    Methods of the returned IntLookupContainer may throw a RuntimeException if the cardinality of this bitset exceeds the int range.
    
    Returns:
    
    The view of this bitset as IntLookupContainer.
  - asLongLookupContainer
```
public LongLookupContainer asLongLookupContainer()
```
    Returns a view over this bitset data compatible with LongLookupContainer. A new object is always returned, but its methods reflect the current state of the bitset (the view is not a snapshot).
    
    Returns:
    
    The view of this bitset as LongLookupContainer.

Class BitSet

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

DEFAULT_NUM_BITS

bits

wlen

Constructor Detail

BitSet

BitSet

BitSet

Method Detail

newInstance

iterator

capacity

size

length

isEmpty

get

get

set

set

expandingWordNum

clear

clear

clear

clear

getAndSet

getAndSet

flip

flipAndGet

flipAndGet

flip

cardinality

intersectionCount

unionCount

andNotCount

xorCount

nextSetBit

nextSetBit

clone

intersect

union

remove

xor

and

or

andNot

intersects

ensureCapacityWords

grow

getNextSize

ensureCapacity

trimTrailingZeros

bits2words

equals

hashCode

toString

asIntLookupContainer

asLongLookupContainer