Package org.apache.lucene.util
Class BroadWord
java.lang.Object
org.apache.lucene.util.BroadWord
Methods and constants inspired by the article
"Broadword Implementation of Rank/Select Queries" by Sebastiano Vigna, January 30, 2012:
- algorithm 1:
bitCount(long)
, count of set bits in along
- algorithm 2:
select(long, int)
, selection of a set bit in along
, - bytewise signed smaller <8 operator:
smallerUpTo7_8(long,long)
. - shortwise signed smaller <16 operator:
smallerUpto15_16(long,long)
. - some of the Lk and Hk constants that are used by the above:
L8
L8_L
, H8H8_L
, L9L9_L
, L16L16_L
and H16H8_L
.
-
Field Summary
Fields -
Method Summary
Modifier and TypeMethodDescriptionstatic 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 ofselect(long,int)
, usingLong.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.
-
Field Details
-
L8_L
public static final long L8_LLk 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_LHk = 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 ofselect(long,int)
, usingLong.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.
-