Package org.apache.lucene.util

Class BroadWord

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

    • Field Summary

      Fields 
      Modifier and Type Field Description
      static long H16_L  
      static long H8_L
      Hk = Lk << (k-1) .
      static long L16_L  
      static long L8_L
      Lk denotes the constant whose ones are in position 0, k, 2k, .
      static long L9_L  

    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static long notEquals0_8​(long x)
      An unsigned bytewise not equals 0 operator.
      static int select​(long x, int r)
      Select a 1-bit from a long.
      static int selectNaive​(long x, int r)
      Naive implementation of select(long,int), using Long.numberOfTrailingZeros(long) repetitively.
      static long smalleru_8​(long x, long y)
      An unsigned bytewise smaller <8 operator.
      static long smallerUpto15_16​(long x, long y)
      A bytewise smaller <16 operator.
      static long smallerUpTo7_8​(long x, long y)
      A signed bytewise smaller <8 operator, for operands 0L<= x, y <=0x7L.

      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • 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:
        Constant Field Values

      • 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:
        Constant Field Values

    • Method Detail

      • 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.