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 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 INCR_STEP_8
    Deprecated.
    static long MSBS_STEP_8  
    static long ONES_STEP_4  
    static long ONES_STEP_8  
    static 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 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 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 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:
      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
    • INCR_STEP_8

      @Deprecated public static final long INCR_STEP_8
      Deprecated.
      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).
    • 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(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., [-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:
      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 on 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 on 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.
    • 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:
      mostSignificantBit(long)
    • main

      public static void main​(String[] a)