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

Field Summary

Fields
Modifier and Type	Field	Description
`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

All Methods Static Methods Concrete Methods
Modifier and Type	Method	Description
`static long`	`notEquals0_8(long x)`	An unsigned bytewise not equals 0 operator.
`static int`	`select(long x, int r)`	Select a 1-bit from a long.
`static int`	`selectNaive(long x, int r)`	Naive implementation of `select(long,int)`, using `Long.numberOfTrailingZeros(long)` repetitively.
`static long`	`smalleru_8(long x, long y)`	An unsigned bytewise smaller <₈ operator.
`static long`	`smallerUpto15_16(long x, long y)`	A bytewise smaller <₁₆ operator.
`static long`	`smallerUpTo7_8(long x, long y)`	A signed bytewise smaller <₈ 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
  - select
```
public static int select(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 select(long,int), using Long.numberOfTrailingZeros(long) repetitively. Works relatively fast for low ranks.
    
    Returns:
    
    The index of the r-th 1 bit in x, or if no such bit exists, 72.

Class BroadWord

Field Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

L8_L

L9_L

L16_L

H8_L

H16_L

Method Detail

select

smallerUpTo7_8

smalleru_8

notEquals0_8

smallerUpto15_16

selectNaive