Class BroadWord

java.lang.Object
org.apache.lucene.util.BroadWord

public final class BroadWord extends Object
Methods and constants inspired by the article "Broadword Implementation of Rank/Select Queries" by Sebastiano Vigna, January 30, 2012:
  • Field Details

    • L8_L

      public static final long L8_L
      Lk denotes the constant whose ones are in position 0, k, 2k, . . . These contain the low bit of each group of k bits. The suffix _L indicates the long implementation.
      See Also:
    • L9_L

      public static final long L9_L
      See Also:
    • L16_L

      public static final long L16_L
      See Also:
    • H8_L

      public static final long H8_L
      Hk = Lk << (k-1) . These contain the high bit of each group of k bits. The suffix _L indicates the long implementation.
      See Also:
    • H16_L

      public static final long H16_L
      See Also:
  • Method Details

    • select

      public static int select(long x, int r)
      Select a 1-bit from a long.
      Returns:
      The index of the r-th 1 bit in x, or if no such bit exists, 72.
    • smallerUpTo7_8

      public static long smallerUpTo7_8(long x, long y)
      A signed bytewise smaller <8 operator, for operands 0L<= x, y <=0x7L. This uses the following numbers of basic long operations: 1 or, 2 and, 2 xor, 1 minus, 1 not.
      Returns:
      A long with bits set in the H8_L positions corresponding to each input signed byte pair that compares smaller.
    • smalleru_8

      public static long smalleru_8(long x, long y)
      An unsigned bytewise smaller <8 operator. This uses the following numbers of basic long operations: 3 or, 2 and, 2 xor, 1 minus, 1 not.
      Returns:
      A long with bits set in the H8_L positions corresponding to each input unsigned byte pair that compares smaller.
    • notEquals0_8

      public static long notEquals0_8(long x)
      An unsigned bytewise not equals 0 operator. This uses the following numbers of basic long operations: 2 or, 1 and, 1 minus.
      Returns:
      A long with bits set in the H8_L positions corresponding to each unsigned byte that does not equal 0.
    • smallerUpto15_16

      public static long smallerUpto15_16(long x, long y)
      A bytewise smaller <16 operator. This uses the following numbers of basic long operations: 1 or, 2 and, 2 xor, 1 minus, 1 not.
      Returns:
      A long with bits set in the H16_L positions corresponding to each input signed short pair that compares smaller.
    • selectNaive

      public static int selectNaive(long x, int r)
      Naive implementation of select(long,int), using Long.numberOfTrailingZeros(long) repetitively. Works relatively fast for low ranks.
      Returns:
      The index of the r-th 1 bit in x, or if no such bit exists, 72.