Class QuickBitVector

java.lang.Object
cern.colt.bitvector.QuickBitVector

public class QuickBitVector extends Object
Implements quick non polymorphic non bounds checking low level bitvector operations. Includes some operations that interpret sub-bitstrings as long integers.

WARNING: Methods of this class do not check preconditions. Provided with invalid parameters these method may return (or set) invalid values without throwing any exception. You should only use this class when performance is critical and you are absolutely sure that indexes are within bounds.

A bitvector is modelled as a long array, i.e. long[] bits holds bits of a bitvector. Each long value holds 64 bits. The i-th 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).

Version:
1.0, 09/24/99
See Also:
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected static final int
     
    protected static final int
     
    protected static final int
     
    private static final long[]
     
  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    Makes this class non instantiable, but still inheritable.
  • Method Summary

    Modifier and Type
    Method
    Description
    static final long
    bitMaskWithBitsSetFromTo(int from, int to)
    Returns a bit mask with bits in the specified range set to 1, all the rest set to 0.
    static void
    clear(long[] bits, int bitIndex)
    Changes the bit with index bitIndex in the bitvector bits to the "clear" (false) state.
    static boolean
    get(long[] bits, int bitIndex)
    Returns from the bitvector the value of the bit with the specified index.
    static long
    getLongFromTo(long[] bits, int from, int to)
    Returns a long value representing bits of a bitvector from index from to index to.
    static int
    Returns the index of the least significant bit in state "true".
    static long[]
    makeBitVector(int size, int bitsPerElement)
    Constructs a low level bitvector that holds size elements, with each element taking bitsPerElement bits.
    static int
    mostSignificantBit(int value)
    Returns the index of the most significant bit in state "true".
    protected static int
    offset(int bitIndex)
    Returns the index within the unit that contains the given bitIndex.
    private static long[]
    Initializes a table with numbers having 1,2,3,...,64 bits set.
    static void
    put(long[] bits, int bitIndex, boolean value)
    Sets the bit with index bitIndex in the bitvector bits to the state specified by value.
    static void
    putLongFromTo(long[] bits, long value, int from, int to)
    Sets bits of a bitvector from index from to index to to the bits of value.
    static void
    set(long[] bits, int bitIndex)
    Changes the bit with index bitIndex in the bitvector bits to the "set" (true) state.
    protected static int
    unit(int bitIndex)
    Returns the index of the unit that contains the given bitIndex.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • ADDRESS_BITS_PER_UNIT

      protected static final int ADDRESS_BITS_PER_UNIT
      See Also:
    • BITS_PER_UNIT

      protected static final int BITS_PER_UNIT
      See Also:
    • BIT_INDEX_MASK

      protected static final int BIT_INDEX_MASK
      See Also:
    • pows

      private static final long[] pows
  • Constructor Details

    • QuickBitVector

      protected QuickBitVector()
      Makes this class non instantiable, but still inheritable.
  • Method Details

    • bitMaskWithBitsSetFromTo

      public static final long bitMaskWithBitsSetFromTo(int from, int to)
      Returns a bit mask with bits in the specified range set to 1, all the rest set to 0. In other words, returns a bit mask having 0,1,2,3,...,64 bits set. If to-from+1==0 then returns zero (0L). Precondition (not checked): to-from+1 >= 0 invalid input: '&'invalid input: '&' to-from+1 <= 64.
      Parameters:
      from - index of start bit (inclusive)
      to - index of end bit (inclusive).
      Returns:
      the bit mask having all bits between from and to set to 1.
    • clear

      public static void clear(long[] bits, int bitIndex)
      Changes the bit with index bitIndex in the bitvector bits to the "clear" (false) state.
      Parameters:
      bits - the bitvector.
      bitIndex - the index of the bit to be cleared.
    • get

      public static boolean get(long[] bits, int bitIndex)
      Returns from the bitvector the value of the bit with the specified index. The value is true if the bit with the index bitIndex is currently set; otherwise, returns false.
      Parameters:
      bits - the bitvector.
      bitIndex - the bit index.
      Returns:
      the value of the bit with the specified index.
    • getLongFromTo

      public static long getLongFromTo(long[] bits, int from, int to)
      Returns a long value representing bits of a bitvector from index from to index to. Bits are returned as a long value with the return value having bit 0 set to bit from, ..., bit to-from set to bit to. All other bits of return value are set to 0. If from > to then returns zero (0L). Precondition (not checked): to-from+1 <= 64.
      Parameters:
      bits - the bitvector.
      from - index of start bit (inclusive).
      to - index of end bit (inclusive).
      Returns:
      the specified bits as long value.
    • leastSignificantBit

      public static int leastSignificantBit(int value)
      Returns the index of the least significant bit in state "true". Returns 32 if no bit is in state "true". Examples:
      0x80000000 --> 31
      0x7fffffff --> 0
      0x00000001 --> 0
      0x00000000 --> 32
      
    • makeBitVector

      public static long[] makeBitVector(int size, int bitsPerElement)
      Constructs a low level bitvector that holds size elements, with each element taking bitsPerElement bits.
      Parameters:
      size - the number of elements to be stored in the bitvector (must be >= 0).
      bitsPerElement - the number of bits one single element takes.
      Returns:
      a low level bitvector.
    • mostSignificantBit

      public static int mostSignificantBit(int value)
      Returns the index of the most significant bit in state "true". Returns -1 if no bit is in state "true". Examples:
      0x80000000 --> 31
      0x7fffffff --> 30
      0x00000001 --> 0
      0x00000000 --> -1
      
    • offset

      protected static int offset(int bitIndex)
      Returns the index within the unit that contains the given bitIndex.
    • precomputePows

      private static long[] precomputePows()
      Initializes a table with numbers having 1,2,3,...,64 bits set. pows[i] has bits [0..i-1] set. pows[64] == -1L == ~0L == has all 64 bits set --> correct. to speedup calculations in subsequent methods.
    • put

      public static void put(long[] bits, int bitIndex, boolean value)
      Sets the bit with index bitIndex in the bitvector bits to the state specified by value.
      Parameters:
      bits - the bitvector.
      bitIndex - the index of the bit to be changed.
      value - the value to be stored in the bit.
    • putLongFromTo

      public static void putLongFromTo(long[] bits, long value, int from, int to)
      Sets bits of a bitvector from index from to index to to the bits of value. Bit from is set to bit 0 of value, ..., bit to is set to bit to-from of value. All other bits stay unaffected. If from > to then does nothing. Precondition (not checked): to-from+1 <= 64.
      Parameters:
      bits - the bitvector.
      value - the value to be copied into the bitvector.
      from - index of start bit (inclusive).
      to - index of end bit (inclusive).
    • set

      public static void set(long[] bits, int bitIndex)
      Changes the bit with index bitIndex in the bitvector bits to the "set" (true) state.
      Parameters:
      bits - the bitvector.
      bitIndex - the index of the bit to be set.
    • unit

      protected static int unit(int bitIndex)
      Returns the index of the unit that contains the given bitIndex.