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 System.Int64
algorithm 2: Select(Int64, Int32), selection of a set bit in a System.Int64,
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.

Note

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

Inheritance

System.Object

BroadWord

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: Lucene.Net.Util

Assembly: Lucene.Net.dll

Syntax

public static class BroadWord

Fields

| Improve this Doc View Source

H16_L

Declaration

public static readonly long H16_L

Field Value

Type	Description
System.Int64

| Improve this Doc View Source

H8_L

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

Declaration

public static readonly long H8_L

Field Value

Type	Description
System.Int64

| Improve this Doc View Source

L16_L

Declaration

public const long L16_L = 281479271743489L

Field Value

Type	Description
System.Int64

| Improve this Doc View Source

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

Declaration

public const long L8_L = 72340172838076673L

Field Value

Type	Description
System.Int64

| Improve this Doc View Source

L9_L

Declaration

public const long L9_L = -9205322385119247871L

Field Value

Type	Description
System.Int64

Methods

| Improve this Doc View Source

NotEquals0_8(Int64)

An unsigned bytewise not equals 0 operator. This uses the following numbers of basic System.Int64 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 System.Int64 with bits set in the H8_L positions corresponding to each unsigned byte that does not equal 0.

| Improve this Doc View Source

Select(Int64, Int32)

Select a 1-bit from a System.Int64.

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.

| Improve this Doc View Source

SelectNaive(Int64, Int32)

Naive implementation of Select(Int64, Int32), using J2N.Numerics.BitOperation.TrailingZeroCount(System.Int64) 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.

| Improve this Doc View Source

Smalleru_8(Int64, Int64)

An unsigned bytewise smaller <₈ operator. This uses the following numbers of basic System.Int64 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 System.Int64 with bits set in the H8_L positions corresponding to each input unsigned byte pair that compares smaller.

| Improve this Doc View Source

SmallerUpto15_16(Int64, Int64)

A bytewise smaller <₁₆ operator. This uses the following numbers of basic System.Int64 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 System.Int64 with bits set in the H16_L positions corresponding to each input signed short pair that compares smaller.

| Improve this Doc View Source

SmallerUpTo7_8(Int64, Int64)

A signed bytewise smaller <₈ operator, for operands 0L<= x, y <=0x7L. This uses the following numbers of basic System.Int64 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 System.Int64 with bits set in the H8_L positions corresponding to each input signed byte pair that compares smaller.