Fast (Blazegraph Database Platform 2.1.5 API)

java.lang.Object
- it.unimi.dsi.bits.Fast

```
public final class Fast
extends Object
```
All-purpose optimised bit-fiddling static-method container class.
This class contains static optimised utility methods that are used by all classes manipulating bits. They include:
- methods to map bijectively integer to natural numbers and back;
- an implementation of Gerth Brodal's fast algorithm for the most significant bit, and derived methods such as log2(double), ceilLog2(int), etc.;
- an implementation of the classical sideways addition algorithm (a case of broadword programming), which can be used to do ranking, and of a new, dual algorithm for selection; the latter has been presented by Sebastiano Vigna in “Broadword Implementation of Rank/Select Queries”, Proc. of the 7th International Workshop on Experimental Algorithms, WEA 2008, number 5038 in Lecture Notes in Computer Science, pages 154−168. Springer–Verlag, 2008.
Since:

0.1

Author:

Sebastiano Vigna

Field Summary

Fields
Modifier and Type	Field and Description
`static int[]`	`BYTELSB` Precomputed least significant bits for bytes (-1 for 0 ).
`static int[]`	`BYTEMSB` Precomputed most significant bits for bytes (-1 for 0 ).
`static long`	`MSBS_STEP_8`
`static long`	`ONES_STEP_4`
`static long`	`ONES_STEP_8`

Method Summary

Methods
Modifier and Type	Method and Description
`static int`	`ceilLog2(int x)` Computes the ceiling of the base-two logarithm of the argument.
`static int`	`ceilLog2(long x)` Computes the ceiling of the base-two logarithm of the argument.
`static int`	`count(long x)` Returns the number of bits set to one in a long.
`static int`	`int2nat(int x)` Maps integers bijectively into natural numbers.
`static long`	`int2nat(long x)` Maps longs bijectively into long natural numbers.
`static int`	`leastSignificantBit(long x)` Computes the least significant bit of a long integer.
`static int`	`length(int x)` Returns the number of bits that are necessary to encode the argument.
`static int`	`length(long x)` Returns the number of bits that are necessary to encode the argument.
`static double`	`log2(double x)` Returns the base-two logarithm of the argument.
`static void`	`main(String[] a)`
`static int`	`mostSignificantBit(int x)` Returns the most significant bit of an integer.
`static int`	`mostSignificantBit(long x)` Returns the most significant bit of a long.
`static int`	`nat2int(int x)` Maps natural numbers bijectively into integers.
`static long`	`nat2int(long x)` Maps long natural numbers bijectively into longs.
`static int`	`select(long x, int rank)` Returns the position of a bit of given rank.

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - ONES_STEP_4
```
public static final long ONES_STEP_4
```
    See Also:
    Constant Field Values
  - ONES_STEP_8
```
public static final long ONES_STEP_8
```
    See Also:
    Constant Field Values
  - MSBS_STEP_8
```
public static final long MSBS_STEP_8
```
    See Also:
    Constant Field Values
  - BYTELSB
```
public static final int[] BYTELSB
```
    Precomputed least significant bits for bytes (-1 for 0 ).
  - BYTEMSB
```
public static final int[] BYTEMSB
```
    Precomputed most significant bits for bytes (-1 for 0 ).
- Method Detail
  - int2nat
```
public static int int2nat(int x)
```
    Maps integers bijectively into natural numbers.
    This method will map a negative integer x to -2x-1 and a nonnegative integer x to 2x. It can be used to save integers in the range [Integer.MIN_VALUE/2..Integer.MAX_VALUE/2] (i.e., [-2³⁰..2³⁰-1]) using the standard coding methods (which all work on natural numbers). Note that no range checks are performed.
    The inverse of the above map is computed by nat2int(int).
    
    Parameters:
    x - an integer.
    
    Returns:
    the argument mapped into a natural number.
    See Also:
    nat2int(int)
  - nat2int
```
public static int nat2int(int x)
```
    Maps natural numbers bijectively into integers.
    This method computes the inverse of int2nat(int).
    
    Parameters:
    x - a natural number.
    
    Returns:
    the argument mapped into an integer.
    See Also:
    int2nat(int)
  - int2nat
```
public static long int2nat(long x)
```
    Maps longs bijectively into long natural numbers.
    This method will map a negative long x to -2x-1 and a nonnegative long x to 2x. It can be used to save longs in the range [Long.MIN_VALUE/2..Long.MAX_VALUE/2] (i.e., [-2⁶²..2⁶²-1]) using the standard coding methods (which all work on natural numbers). Note that no range checks are performed.
    The inverse of the above map is computed by nat2int(long).
    
    Parameters:
    x - a long.
    
    Returns:
    the argument mapped into a long natural number.
    See Also:
    int2nat(int)
  - nat2int
```
public static long nat2int(long x)
```
    Maps long natural numbers bijectively into longs.
    This method computes the inverse of int2nat(long).
    
    Parameters:
    x - a long natural number.
    
    Returns:
    the argument mapped into a long.
    See Also:
    nat2int(int)
  - log2
```
public static double log2(double x)
```
    Returns the base-two logarithm of the argument.
    
    Parameters:
    x - a double.
    
    Returns:
    the base-2 logarithm of x.
  - ceilLog2
```
public static int ceilLog2(int x)
```
    Computes the ceiling of the base-two logarithm of the argument.
    This method relies of mostSignificantBit(int), and thus is pretty fast.
    
    Parameters:
    x - an integer.
    
    Returns:
    the ceiling of the base-two logarithm of the argument, or -1 if x is zero.
  - ceilLog2
```
public static int ceilLog2(long x)
```
    Computes the ceiling of the base-two logarithm of the argument.
    This method relies of mostSignificantBit(long), and thus is pretty fast.
    
    Parameters:
    x - an integer.
    
    Returns:
    the ceiling of the base-two logarithm of the argument, or -1 if x is zero.
  - length
```
public static int length(int x)
```
    Returns the number of bits that are necessary to encode the argument.
    
    Parameters:
    x - an integer.
    
    Returns:
    the number of bits that are necessary to encode x.
  - length
```
public static int length(long x)
```
    Returns the number of bits that are necessary to encode the argument.
    
    Parameters:
    x - a long.
    
    Returns:
    the number of bits that are necessary to encode x.
  - count
```
public static int count(long x)
```
    Returns the number of bits set to one in a long.
    This method implements a classical broadword algorithm.
    
    Parameters:
    x - a long.
    
    Returns:
    the number of bits set to one in x.
  - select
```
public static int select(long x,
         int rank)
```
    Returns the position of a bit of given rank.
    This method implements a new broadword algorithm.
    
    Parameters:
    x - a long.
    rank - a rank (smaller than 128).
    
    Returns:
    the position in x of the bit of rank k ones; if no such bit exists, returns 72.
  - mostSignificantBit
```
public static int mostSignificantBit(long x)
```
    Returns the most significant bit of a long.
    This method implements Gerth Brodal's broadword algorithm. On 64-bit architectures it is an order of magnitude faster than standard bit-fiddling techniques.
    
    Parameters:
    x - a long.
    
    Returns:
    the most significant bit of x, of x is nonzero; −1, otherwise.
  - mostSignificantBit
```
public static int mostSignificantBit(int x)
```
    Returns the most significant bit of an integer.
    
    Parameters:
    x - an integer.
    
    Returns:
    the most significant bit of x, of x is nonzero; −1, otherwise.
    See Also:
    mostSignificantBit(long)
  - leastSignificantBit
```
public static int leastSignificantBit(long x)
```
    Computes the least significant bit of a long integer.
    
    Parameters:
    x - a long integer.
    
    Returns:
    the least significant bit of the argument (-1 for 0).
  - main
```
public static void main(String[] a)
```

Class Fast

Field Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

ONES_STEP_4

ONES_STEP_8

MSBS_STEP_8

BYTELSB

BYTEMSB

Method Detail

int2nat

nat2int

int2nat

nat2int

log2

ceilLog2

ceilLog2

length

length

count

select

mostSignificantBit

mostSignificantBit

leastSignificantBit

main