Class BitVector

solr/core/src/java/org/apache/solr/util/hll/BitVector.java:25–284

A vector (array) of bits that is accessed in units ("registers") of width bits which are stored as 64bit "words" ( long s). In this context a register is at most 64bits.

 * are stored as 64bit "words" (<code>long</code>s). In this context a register is at most 64bits.
 */
class BitVector implements Cloneable {
  // NOTE:  in this context, a word is 64bits

  // rather than doing division to determine how a bit index fits into 64bit
  // words (i.e. longs), bit shifting is used
  private static final int LOG2_BITS_PER_WORD = 6 /*=>64bits*/;
  private static final int BITS_PER_WORD = 1 << LOG2_BITS_PER_WORD;
  private static final int BITS_PER_WORD_MASK = BITS_PER_WORD - 1;

  // ditto from above but for bytes (for output)
  private static final int LOG2_BITS_PER_BYTE = 3 /*=>8bits*/;
  public static final int BITS_PER_BYTE = 1 << LOG2_BITS_PER_BYTE;

  // ========================================================================
  public static final int BYTES_PER_WORD = 8 /*8 bytes in a long*/;

  // ************************************************************************
  // 64bit words
  private final long[] words;

  public final long[] words() {
    return words;
  }

  public final int wordCount() {
    return words.length;
  }

  public final int byteCount() {
    return wordCount() * BYTES_PER_WORD;
  }

  // the width of a register in bits (this cannot be more than 64 (the word size))
  private final int registerWidth;

  public final int registerWidth() {
    return registerWidth;
  }

  private final long count;

  // ------------------------------------------------------------------------
  private final long registerMask;

  // ========================================================================
  /**
   * @param width the width of each register. This cannot be negative or zero or greater than 63
   *     (the signed word size).
   * @param count the number of registers. This cannot be negative or zero
   */
  public BitVector(final int width, final long count) {
    // ceil((width * count)/BITS_PER_WORD)
    this.words = new long[(int) (((width * count) + BITS_PER_WORD_MASK) >>> LOG2_BITS_PER_WORD)];
    this.registerWidth = width;
    this.count = count;

    this.registerMask = (1L << width) - 1;
  }