Class Fast
public final class Fast extends Object
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 ith 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 base2 logarithm of the argument.static int
ceilLog2(int x)
Computes the ceiling of the basetwo logarithm of the argument.static int
ceilLog2(long x)
Computes the ceiling of the basetwo 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 basetwo 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 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. See Also:
 Constant Field Values

BYTELSB
public static final int[] BYTELSBPrecomputed least significant bits for bytes (1 for 0). 
BYTEMSB
public static final int[] BYTEMSBPrecomputed most significant bits for bytes (1 for 0). 
selectInByte
public static final byte[] selectInByteA precomputed table containing in position 256i + j the position of the ith 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 2x1 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^{30}..2^{30}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 2x1 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^{62}..2^{62}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 basetwo logarithm of the argument. Parameters:
x
 a double. Returns:
 the base2 logarithm of
x
.

ceilLog2
public static int ceilLog2(int x)Computes the ceiling of the basetwo logarithm of the argument.This method relies on
mostSignificantBit(int)
, and thus is pretty fast. Parameters:
x
 an integer. Returns:
 the ceiling of the basetwo logarithm of the argument, or 1 if
x
is zero.

ceilLog2
public static int ceilLog2(long x)Computes the ceiling of the basetwo logarithm of the argument.This method relies on
mostSignificantBit(long)
, and thus is pretty fast. Parameters:
x
 an integer. Returns:
 the ceiling of the basetwo logarithm of the argument, or 1 if
x
is zero.

approximateLog2
public static int approximateLog2(double x)Computes an approximate integer base2 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 basetwo 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:
 2^{exponent}.

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 inx
; 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
, ofx
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
, ofx
is nonzero; −1, otherwise.  See Also:
mostSignificantBit(long)

main
