Class BroadWord

Methods and constants inspired by the article "Broadword Implementation of Rank/Select Queries" by Sebastiano Vigna, January 30, 2012:

• algorithm 1: Lucene.Net.Util.BroadWord.BitCount(System.Int64), count of set bits in a
• algorithm 2: Select(Int64, Int32), selection of a set bit in a ,
• bytewise signed smaller <₈ operator: SmallerUpTo7_8(Int64, Int64).
• shortwise signed smaller <₁₆ operator: SmallerUpto15_16(Int64, Int64).
• 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.

This is a Lucene.NET INTERNAL API, use at your own risk

Inheritance

System.Object

BroadWord

Namespace: Lucene.Net.Util

Assembly: Lucene.Net.dll

Syntax

public sealed class BroadWord : object

Fields

H16_L

Declaration

public static readonly long H16_L

Field Value

Type	Description
System.Int64

H8_L

Hk = Lk << (k-1) . These contain the high bit of each group of k bits. The suffix _L indicates the implementation.

Declaration

public static readonly long H8_L

Field Value

Type	Description
System.Int64

L16_L

Declaration

public const long L16_L = null

Field Value

Type	Description
System.Int64

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

Declaration

public const long L8_L = null

Field Value

Type	Description
System.Int64

L9_L

Declaration

public const long L9_L = null

Field Value

Type	Description
System.Int64

Methods

NotEquals0_8(Int64)

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

Declaration

public static long NotEquals0_8(long x)

Parameters

Type	Name	Description
System.Int64	x

Returns

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

Select(Int64, Int32)

Select a 1-bit from a .

Declaration

public static int Select(long x, int r)

Parameters

Type	Name	Description
System.Int64	x
System.Int32	r

Returns

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

SelectNaive(Int64, Int32)

Naive implementation of Select(Int64, Int32), using repetitively. Works relatively fast for low ranks.

Declaration

public static int SelectNaive(long x, int r)

Parameters

Type	Name	Description
System.Int64	x
System.Int32	r

Returns

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

Smalleru_8(Int64, Int64)

An unsigned bytewise smaller <₈ operator. This uses the following numbers of basic 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
System.Int64	x
System.Int64	y

Returns

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

SmallerUpto15_16(Int64, Int64)

A bytewise smaller <₁₆ operator. This uses the following numbers of basic 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
System.Int64	x
System.Int64	y

Returns

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

SmallerUpTo7_8(Int64, Int64)

A signed bytewise smaller <₈ operator, for operands 0L<= x, y <=0x7L. This uses the following numbers of basic 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
System.Int64	x
System.Int64	y

Returns

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