Class Fast

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 used to contain a large number of bits hacks. Intrinsification of methods such as Long.bitCount(long), Long.numberOfTrailingZeros(long), etc. using SSE instructions has made such hacks obsolete.

The main highlight is now a new algorithm for selection that is twice as fast as the one previously implemented, but that will behave impredictably if there is no bit with the requested rank; the algorithm is based on the one 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, but it has been improved with ideas from Simon Gog's SDSL library.

Since:
0.1
Author:
Sebastiano Vigna
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final int[]
    Precomputed least significant bits for bytes (-1 for 0).
    static final int[]
    Precomputed most significant bits for bytes (-1 for 0).
    static final long
    Deprecated.
    static final long
     
    static final long
     
    static final long
     
    static final byte[]
    A precomputed table containing in position 256i + j the position of the i-th one (0 ≤ j < 8) in the binary representation of i (0 ≤ i < 256), or -1 if no such bit exists.
  • Method Summary

    Modifier and Type
    Method
    Description
    static int
    approximateLog2(double x)
    Computes an approximate integer base-2 logarithm of the argument.
    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
    int2nat(int x)
    Maps integers bijectively into natural numbers.
    static long
    int2nat(long x)
    Maps longs bijectively into long natural numbers.
    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
    Returns the most significant bit of an integer.
    static int
    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 double
    pow2(int exponent)
    Quickly raises 2 to the argument.
    static int
    select(long x, int rank)
    Returns the position of a bit of given rank (starting from zero).

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

    • ONES_STEP_4

      public static final long ONES_STEP_4
      See Also:
    • ONES_STEP_8

      public static final long ONES_STEP_8
      See Also:
    • MSBS_STEP_8

      public static final long MSBS_STEP_8
      See Also:
    • INCR_STEP_8

      @Deprecated public static final long INCR_STEP_8
      Deprecated.
      See Also:
    • 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).
    • selectInByte

      public static final byte[] selectInByte
      A precomputed table containing in position 256i + j the position of the i-th one (0 ≤ j < 8) in the binary representation of i (0 ≤ i < 256), or -1 if no such bit exists.
  • Method Details

    • 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., [-230..230-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

      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

      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., [-262..262-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:
    • 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:
    • 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 on Integer.numberOfLeadingZeros(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 on Long.numberOfLeadingZeros(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.
    • approximateLog2

      public static int approximateLog2(double x)
      Computes an approximate integer base-2 logarithm of the argument.

      This method relies on Double.doubleToRawLongBits(double), and thus is very fast if the former is intrinsified by the JVM.

      Parameters:
      x - a double.
      Returns:
      an integer approximation of the base-two logarithm of the argument.
    • pow2

      public static double pow2(int exponent)
      Quickly raises 2 to the argument.
      Parameters:
      exponent - an integer exponent between -62 ad 62.
      Returns:
      2exponent.
    • 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.
    • select

      public static int select(long x, int rank)
      Returns the position of a bit of given rank (starting from zero).
      Parameters:
      x - a long.
      rank - an integer smaller than the number of ones in x; impredictable results (including exceptions) might happen if this constraint is violated.
      Returns:
      the position in x of the bit of given rank.
    • mostSignificantBit

      public static int mostSignificantBit(long x)
      Returns the most significant bit of a long.

      This method returns 63 − Long.numberOfLeadingZeroes(x).

      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:
    • main

      public static void main(String[] a)