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.

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

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.