Class 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 a long
algorithm 2: Select(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.

Inheritance

object

BroadWord

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Namespace: Lucene.Net.Util

Assembly: Lucene.Net.dll

Syntax

public static class BroadWord

Fields

H16_L

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 a long
algorithm 2: Select(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.

Declaration

public static readonly long H16_L

Field Value

Type	Description
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.

Declaration

public static readonly long H8_L

Field Value

Type	Description
long

L16_L

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 a long
algorithm 2: Select(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.

Declaration

public const long L16_L = 281479271743489

Field Value

Type	Description
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.

Declaration

public const long L8_L = 72340172838076673

Field Value

Type	Description
long

L9_L

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 a long
algorithm 2: Select(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.

Declaration

public const long L9_L = -9205322385119247871

Field Value

Type	Description
long

Methods

NotEquals0_8(long)

An unsigned bytewise not equals 0 operator. This uses the following numbers of basic long operations: 2 or, 1 and, 1 minus.

Declaration

public static long NotEquals0_8(long x)

Parameters

Type	Name	Description
long	x

Returns

Type	Description
long	A long with bits set in the H8_L positions corresponding to each unsigned byte that does not equal 0.

Select(long, int)

Select a 1-bit from a long.

Declaration

public static int Select(long x, int r)

Parameters

Type	Name	Description
long	x
int	r

Returns

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

SelectNaive(long, int)

Naive implementation of Select(long, int), using TrailingZeroCount(long) repetitively. Works relatively fast for low ranks.

Declaration

public static int SelectNaive(long x, int r)

Parameters

Type	Name	Description
long	x
int	r

Returns

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

SmallerUpTo7_8(long, long)

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.

Declaration

public static long SmallerUpTo7_8(long x, long y)

Parameters

Type	Name	Description
long	x
long	y

Returns

Type	Description
long	A long with bits set in the H8_L positions corresponding to each input signed byte pair that compares smaller.

SmallerUpto15_16(long, long)

A bytewise smaller <₁₆ operator. This uses the following numbers of basic long operations: 1 or, 2 and, 2 xor, 1 minus, 1 not.

Declaration

public static long SmallerUpto15_16(long x, long y)

Parameters

Type	Name	Description
long	x
long	y

Returns

Type	Description
long	A long with bits set in the H16_L positions corresponding to each input signed short pair that compares smaller.

Smalleru_8(long, long)

An unsigned bytewise smaller <₈ operator. This uses the following numbers of basic long operations: 3 or, 2 and, 2 xor, 1 minus, 1 not.

Declaration

public static long Smalleru_8(long x, long y)

Parameters

Type	Name	Description
long	x
long	y

Returns

Type	Description
long	A long with bits set in the H8_L positions corresponding to each input unsigned byte pair that compares smaller.