Package it.unimi.dsi.bits

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[]	BYTELSB	Precomputed least significant bits for bytes (-1 for 0).
static final int[]	BYTEMSB	Precomputed most significant bits for bytes (-1 for 0).
static final long	INCR_STEP_8	Deprecated.
static final long	MSBS_STEP_8
static final long	ONES_STEP_4
static final long	ONES_STEP_8
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 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., [-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 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:

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 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)