Class 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).
    • Field Detail

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