org.apache.lucene.util
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:

• algorithm 1: rank9(long), count of set bits in a long
• algorithm 2: select9(long, int), selection of a set bit in a long,
• bytewise signed smaller <₈ operator: smallerUpTo7_8(long,long).
• shortwise signed smaller <₁₆ operator: smallerUpto15_16(long,long).
• some of the Lk and Hk constants that are used by the above: L8 L8_L, H8 H8_L, L9 L9_L, L16 L16_Land H16 H8_L.

NOTE: This API is for internal purposes only and might change in incompatible ways in the next release.

Field Summary

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

static long	notEquals0_8(long x) An unsigned bytewise not equals 0 operator.
static int	select9(long x, int r) Select a 1-bit from a long.
static int	selectNaive(long x, int r) Naive implementation of select9(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

clone, equals, finalize, 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

L9_L

public static final long L9_L

See Also:

Constant Field Values

L16_L

public static final long L16_L

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

H16_L

public static final long H16_L

See Also:

Constant Field Values

Method Detail

select9

public static int select9(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 <₈ 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 <₈ 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 <₁₆ 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 select9(long,int), using Long.numberOfTrailingZeros(long) repetitively.

Returns:

The index of the r-th 1 bit in x, or if no such bit exists, 72.