Class BitsUtil


  • public final class BitsUtil
    extends java.lang.Object
    Utilities for bit operations.

    Implementation note: words are stored in little-endian word order. This can be a bit confusing, because a shift-right means "left" on the word level.

    Naming: methods with a C return a copy, methods with I modify in-place.

    Since:
    0.5.0
    Author:
    Erich Schubert
    • Field Summary

      Fields 
      Modifier and Type Field Description
      static it.unimi.dsi.fastutil.Hash.Strategy<long[]> FASTUTIL_HASH_STRATEGY
      Hashing strategy to use with Fastutils.
      private static long LONG_32_BITS
      Masking 32 bit
      private static long LONG_63_BITS
      Long, with 63 bits set
      private static long LONG_ALL_BITS
      Long with all bits set
      private static int LONG_LOG2_MASK
      Masking for long shifts.
      private static int LONG_LOG2_SIZE
      Shift factor for a long: 2^6 == 64 == Long.SIZE
      private static int[] POW5_INT
      Precomputed powers of 5 for pow5, pow10 on the bit representation.
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private BitsUtil()
      Private constructor.
    • Method Summary

      All Methods Static Methods Concrete Methods 
      Modifier and Type Method Description
      static long[] andCMin​(long[] v, long[] o)
      AND o onto v in a copy, i.e. v & o
      static long[] andI​(long[] v, long[] o)
      AND o onto v in-place, i.e. v &= o
      static long[] andI​(long[] v, long[] o, int off)
      AND o onto v in-place, i.e. v &= (o << off)
      static int capacity​(long[] v)
      Capacity of the vector v.
      static int cardinality​(long v)
      Compute the cardinality (number of set bits)
      static int cardinality​(long[] v)
      Compute the cardinality (number of set bits)
      static long clearC​(long v, int off)
      Clear bit number "off" in v.
      static long[] clearI​(long[] v, int off)
      Clear bit number "off" in v.
      static int compare​(long[] x, long[] y)
      Compare two bitsets.
      static int compare​(long x, long y)
      Compare two bitsets.
      static long[] copy​(long[] v)
      Copy a bitset
      static long[] copy​(long[] v, int mincap)
      Copy a bitset.
      static long[] copy​(long[] v, int mincap, int shift)
      Copy a bitset.
      static long cycleLeftC​(long v, int shift, int len)
      Rotate a long to the left, cyclic with length len
      static long[] cycleLeftI​(long[] v, int shift, int len)
      Cycle a bitstring to the right.
      static long cycleRightC​(long v, int shift, int len)
      Rotate a long to the right, cyclic with length len
      static long[] cycleRightI​(long[] v, int shift, int len)
      Cycle a bitstring to the right.
      static boolean equal​(long[] x, long[] y)
      Test two bitsets for equality
      static boolean equal​(long x, long y)
      Test two bitsets for equality
      static long flipC​(long v, int off)
      Invert bit number "off" in v.
      static long[] flipI​(long[] v, int off)
      Invert bit number "off" in v.
      static boolean get​(long[] v, int off)
      Set bit number "off" in v.
      static boolean get​(long v, int off)
      Set bit number "off" in v.
      static long grayC​(long v)
      Compute corresponding gray code as v XOR (v >>> 1)
      static long[] grayI​(long[] v)
      Compute corresponding gray code as v XOR (v >>> 1)
      static int hammingDistance​(long[] x, long[] y)
      Compute the Hamming distance (Size of symmetric difference), i.e.
      static int hammingDistance​(long b1, long b2)
      Compute the Hamming distance (Size of symmetric difference), i.e.
      static int hashCode​(long x)
      Compute a hash code for the given bitset.
      static int hashCode​(long[] x)
      Compute a hash code for the given bitset.
      static boolean intersect​(long[] x, long[] y)
      Test whether two Bitsets intersect.
      static boolean intersect​(long x, long y)
      Test whether two Bitsets intersect.
      static int intersectionSize​(long[] x, long[] y)
      Compute the intersection size of two Bitsets.
      static int intersectionSize​(long x, long y)
      Compute the intersection size of two Bitsets.
      static long[] invertI​(long[] v)
      Invert v in-place.
      static long invgrayC​(long v)
      Compute the inverted gray code, v XOR (v >>> 1) XOR (v >>> 2) ...
      static long[] invgrayI​(long[] v)
      Compute the inverted gray code, v XOR (v >>> 1) XOR (v >>> 2) ...
      static boolean isZero​(long[] v)
      Test for the bitstring to be all-zero.
      static double lpow10​(long m, int n)
      Compute m * Math.pow(10,e) on the bit representation, for assembling a floating point decimal value.
      static double lpow2​(long m, int n)
      Compute m * pow(2., n) using bit operations.
      static int magnitude​(int v)
      The magnitude is the position of the highest bit set
      static int magnitude​(long v)
      The magnitude is the position of the highest bit set
      static int magnitude​(long[] v)
      The magnitude is the position of the highest bit set
      static long[] make​(int bits, long init)
      Allocate a new long[].
      static long[] nandI​(long[] v, long[] o)
      NOTAND o onto v in-place, i.e. v &= ~o
      static int nextClearBit​(long[] v, int start)
      Find the next clear bit.
      static int nextClearBit​(long v, int start)
      Find the next clear bit.
      static int nextSetBit​(long[] v, int start)
      Find the next set bit.
      static int nextSetBit​(long v, int start)
      Find the next set bit.
      static int numberOfLeadingZeros​(int v)
      Find the number of leading zeros; 32 if all zero
      static int numberOfLeadingZeros​(long v)
      Find the number of leading zeros; 64 if all zero
      static int numberOfLeadingZeros​(long[] v)
      Find the number of leading zeros.
      static int numberOfLeadingZerosSigned​(int v)
      Find the number of leading zeros; -1 if all zero
      static int numberOfLeadingZerosSigned​(long v)
      Find the number of leading zeros; -1 if all zero
      static int numberOfLeadingZerosSigned​(long[] v)
      Find the number of leading zeros.
      static int numberOfTrailingZeros​(int v)
      Find the number of trailing zeros.
      static int numberOfTrailingZeros​(long v)
      Find the number of trailing zeros.
      static int numberOfTrailingZeros​(long[] v)
      Find the number of trailing zeros.
      static int numberOfTrailingZerosSigned​(long v)
      Find the number of trailing zeros.
      static int numberOfTrailingZerosSigned​(long[] v)
      Find the number of trailing zeros.
      static long[] of​(int... positions)
      Generate a bitset with the given list of positions set to 1.
      static long[] ones​(int bits)
      Create a vector initialized with "bits" ones.
      static void onesI​(long[] v, int bits)
      Fill a vector initialized with "bits" ones.
      static long[] orI​(long[] v, long[] o)
      OR o onto v in-place, i.e. v |= o
      static long[] orI​(long[] v, long[] o, int off)
      OR o onto v in-place, i.e. v |= (o << off)
      static int previousClearBit​(long[] v, int start)
      Find the previous clear bit.
      static int previousClearBit​(long v, int start)
      Find the previous clear bit.
      static int previousSetBit​(long[] v, int start)
      Find the previous set bit.
      static int previousSetBit​(long v, int start)
      Find the previous set bit.
      static long[] random​(int card, int capacity, java.util.Random random)
      Creates a new BitSet of fixed cardinality with randomly set bits.
      static long setC​(long v, int off)
      Set bit number "off" in v.
      static long[] setI​(long[] v, int off)
      Set bit number "off" in v.
      static long[] setI​(long[] v, long[] o)
      Put o onto v in-place, i.e. v = o
      static long[] shiftLeftI​(long[] v, int off)
      Shift a long[] bitset in-place.
      static long[] shiftRightI​(long[] v, int off)
      Shift a long[] bitset in-place.
      static java.lang.String toString​(long v)
      Convert bitset to a string consisting of "0" and "1", in high-endian order.
      static java.lang.String toString​(long[] v)
      Convert bitset to a string consisting of "0" and "1", in high-endian order.
      static java.lang.String toString​(long[] v, int minw)
      Convert bitset to a string consisting of "0" and "1", in high-endian order.
      static java.lang.String toString​(long[] v, java.lang.String sep, int offset)
      Convert the bitset into a decimal representation, e.g., 0, 3, 5
      static java.lang.String toStringLow​(long v)
      Convert bitset to a string consisting of "0" and "1", in low-endian order.
      static java.lang.String toStringLow​(long[] v)
      Convert bitset to a string consisting of "0" and "1", in low-endian order.
      static java.lang.String toStringLow​(long[] v, int minw)
      Convert bitset to a string consisting of "0" and "1", in low-endian order.
      static long[] truncateI​(long[] v, int len)
      Truncate a bit string to the given length (setting any higher bit to 0).
      static int unionSize​(long[] x, long[] y)
      Compute the union size of two Bitsets.
      static int unionSize​(long x, long y)
      Compute the union size of two Bitsets.
      static long[] xorI​(long[] v, long[] o)
      XOR o onto v in-place, i.e. v ^= o
      static long[] xorI​(long[] v, long[] o, int off)
      XOR o onto v in-place, i.e. v ^= (o << off)
      static long[] zero​(int bits)
      Allocate a new long[].
      static long[] zeroI​(long[] v)
      Zero the given set Low-endian layout for the array.
      • Methods inherited from class java.lang.Object

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

      • LONG_LOG2_SIZE

        private static final int LONG_LOG2_SIZE
        Shift factor for a long: 2^6 == 64 == Long.SIZE
        See Also:
        Constant Field Values
      • LONG_LOG2_MASK

        private static final int LONG_LOG2_MASK
        Masking for long shifts.
        See Also:
        Constant Field Values
      • LONG_ALL_BITS

        private static final long LONG_ALL_BITS
        Long with all bits set
        See Also:
        Constant Field Values
      • LONG_63_BITS

        private static final long LONG_63_BITS
        Long, with 63 bits set
        See Also:
        Constant Field Values
      • POW5_INT

        private static final int[] POW5_INT
        Precomputed powers of 5 for pow5, pow10 on the bit representation.
      • FASTUTIL_HASH_STRATEGY

        public static final it.unimi.dsi.fastutil.Hash.Strategy<long[]> FASTUTIL_HASH_STRATEGY
        Hashing strategy to use with Fastutils.
    • Constructor Detail

      • BitsUtil

        private BitsUtil()
        Private constructor. Static methods only.
    • Method Detail

      • zero

        public static long[] zero​(int bits)
        Allocate a new long[].
        Parameters:
        bits - Number of bits in storage
        Returns:
        New array
      • make

        public static long[] make​(int bits,
                                  long init)
        Allocate a new long[].
        Parameters:
        bits - Number of bits in storage
        init - Initial value (of at most the size of a long, remaining bits will be 0)
        Returns:
        New array
      • of

        public static long[] of​(int... positions)
        Generate a bitset with the given list of positions set to 1.
        Parameters:
        positions - Positions of ones.
        Returns:
        Bitmask
      • ones

        public static long[] ones​(int bits)
        Create a vector initialized with "bits" ones.
        Parameters:
        bits - Size
        Returns:
        new vector
      • random

        public static long[] random​(int card,
                                    int capacity,
                                    java.util.Random random)
        Creates a new BitSet of fixed cardinality with randomly set bits.
        Parameters:
        card - the cardinality of the BitSet to create
        capacity - the capacity of the BitSet to create - the randomly generated indices of the bits set to true will be uniformly distributed between 0 (inclusive) and capacity (exclusive)
        random - a Random Object to create the sequence of indices set to true - the same number occurring twice or more is ignored but the already selected bit remains true
        Returns:
        a new BitSet with randomly set bits
      • copy

        public static long[] copy​(long[] v)
        Copy a bitset
        Parameters:
        v - Array to copy
        Returns:
        Copy
      • copy

        public static long[] copy​(long[] v,
                                  int mincap)
        Copy a bitset. Note: Bits beyond mincap may be retained!
        Parameters:
        v - Array to copy
        mincap - Target minimum capacity
        Returns:
        Copy with space for at least "capacity" bits
      • copy

        public static long[] copy​(long[] v,
                                  int mincap,
                                  int shift)
        Copy a bitset.

        Note: Bits beyond mincap may be retained!

        Parameters:
        v - Array to copy
        mincap - Target minimum capacity
        shift - Number of bits to shift left
        Returns:
        Copy with space for at least "capacity" bits
      • grayC

        public static long grayC​(long v)
        Compute corresponding gray code as v XOR (v >>> 1)
        Parameters:
        v - Value
        Returns:
        Gray code
      • grayI

        public static long[] grayI​(long[] v)
        Compute corresponding gray code as v XOR (v >>> 1)
        Parameters:
        v - Value
        Returns:
        Gray code
      • invgrayC

        public static long invgrayC​(long v)
        Compute the inverted gray code, v XOR (v >>> 1) XOR (v >>> 2) ...
        Parameters:
        v - Value
        Returns:
        Inverted gray code
      • invgrayI

        public static long[] invgrayI​(long[] v)
        Compute the inverted gray code, v XOR (v >>> 1) XOR (v >>> 2) ...
        Parameters:
        v - Value
        Returns:
        Inverted gray code
      • isZero

        public static boolean isZero​(long[] v)
        Test for the bitstring to be all-zero.
        Parameters:
        v - Bitstring
        Returns:
        true when all zero
      • cardinality

        public static int cardinality​(long v)
        Compute the cardinality (number of set bits)
        Parameters:
        v - Value
        Returns:
        Number of bits set in long
      • cardinality

        public static int cardinality​(long[] v)
        Compute the cardinality (number of set bits)

        Low-endian layout for the array.

        Parameters:
        v - Value
        Returns:
        Number of bits set in long[]
      • flipC

        public static long flipC​(long v,
                                 int off)
        Invert bit number "off" in v.
        Parameters:
        v - Buffer
        off - Offset to flip
      • flipI

        public static long[] flipI​(long[] v,
                                   int off)
        Invert bit number "off" in v.

        Low-endian layout for the array.

        Parameters:
        v - Buffer
        off - Offset to flip
      • setC

        public static long setC​(long v,
                                int off)
        Set bit number "off" in v.
        Parameters:
        v - Buffer
        off - Offset to set
      • setI

        public static long[] setI​(long[] v,
                                  int off)
        Set bit number "off" in v.

        Low-endian layout for the array.

        Parameters:
        v - Buffer
        off - Offset to set
      • setI

        public static long[] setI​(long[] v,
                                  long[] o)
        Put o onto v in-place, i.e. v = o
        Parameters:
        v - Primary object
        o - data to initialize to.
        Returns:
        v
      • clearC

        public static long clearC​(long v,
                                  int off)
        Clear bit number "off" in v.
        Parameters:
        v - Buffer
        off - Offset to clear
      • clearI

        public static long[] clearI​(long[] v,
                                    int off)
        Clear bit number "off" in v.

        Low-endian layout for the array.

        Parameters:
        v - Buffer
        off - Offset to clear
      • get

        public static boolean get​(long v,
                                  int off)
        Set bit number "off" in v.
        Parameters:
        v - Buffer
        off - Offset to set
      • get

        public static boolean get​(long[] v,
                                  int off)
        Set bit number "off" in v.

        Low-endian layout for the array.

        Parameters:
        v - Buffer
        off - Offset to set
      • onesI

        public static void onesI​(long[] v,
                                 int bits)
        Fill a vector initialized with "bits" ones.
        Parameters:
        v - Vector to fill.
        bits - Size
      • zeroI

        public static long[] zeroI​(long[] v)
        Zero the given set Low-endian layout for the array.
        Parameters:
        v - existing set
        Returns:
        array set to zero
      • xorI

        public static long[] xorI​(long[] v,
                                  long[] o)
        XOR o onto v in-place, i.e. v ^= o
        Parameters:
        v - Primary object
        o - data to xor
        Returns:
        v
      • xorI

        public static long[] xorI​(long[] v,
                                  long[] o,
                                  int off)
        XOR o onto v in-place, i.e. v ^= (o << off)
        Parameters:
        v - Primary object
        o - data to or
        off - Offset
        Returns:
        v
      • orI

        public static long[] orI​(long[] v,
                                 long[] o)
        OR o onto v in-place, i.e. v |= o
        Parameters:
        v - Primary object
        o - data to or
        Returns:
        v
      • orI

        public static long[] orI​(long[] v,
                                 long[] o,
                                 int off)
        OR o onto v in-place, i.e. v |= (o << off)

        Note: Bits that are shifted outside of the size of v are discarded.

        Parameters:
        v - Primary object
        o - data to or
        off - Offset
        Returns:
        v
      • andI

        public static long[] andI​(long[] v,
                                  long[] o)
        AND o onto v in-place, i.e. v &= o
        Parameters:
        v - Primary object
        o - data to and
        Returns:
        v
      • andI

        public static long[] andI​(long[] v,
                                  long[] o,
                                  int off)
        AND o onto v in-place, i.e. v &= (o << off)
        Parameters:
        v - Primary object
        o - data to or
        off - Offset
        Returns:
        v
      • andCMin

        public static long[] andCMin​(long[] v,
                                     long[] o)
        AND o onto v in a copy, i.e. v & o

        The resulting array will have the shorter length of the two.

        Parameters:
        v - Primary object
        o - data to and
        Returns:
        Copy of v and o
      • nandI

        public static long[] nandI​(long[] v,
                                   long[] o)
        NOTAND o onto v in-place, i.e. v &= ~o
        Parameters:
        v - Primary object
        o - data to and
        Returns:
        v
      • invertI

        public static long[] invertI​(long[] v)
        Invert v in-place.
        Parameters:
        v - Object to invert
        Returns:
        v
      • shiftRightI

        public static long[] shiftRightI​(long[] v,
                                         int off)
        Shift a long[] bitset in-place.

        Low-endian layout for the array.

        Parameters:
        v - existing bitset
        off - Offset to shift by
        Returns:
        Bitset
      • shiftLeftI

        public static long[] shiftLeftI​(long[] v,
                                        int off)
        Shift a long[] bitset in-place.

        Low-endian layout for the array.

        Parameters:
        v - existing bitset
        off - Offset to shift by
        Returns:
        Bitset
      • cycleRightC

        public static long cycleRightC​(long v,
                                       int shift,
                                       int len)
        Rotate a long to the right, cyclic with length len
        Parameters:
        v - Bits
        shift - Shift value
        len - Length
        Returns:
        cycled bit set
      • cycleRightI

        public static long[] cycleRightI​(long[] v,
                                         int shift,
                                         int len)
        Cycle a bitstring to the right.
        Parameters:
        v - Bit string
        shift - Number of steps to cycle
        len - Length
      • truncateI

        public static long[] truncateI​(long[] v,
                                       int len)
        Truncate a bit string to the given length (setting any higher bit to 0).
        Parameters:
        v - String to process
        len - Length (in bits) to truncate to
      • cycleLeftC

        public static long cycleLeftC​(long v,
                                      int shift,
                                      int len)
        Rotate a long to the left, cyclic with length len
        Parameters:
        v - Bits
        shift - Shift value
        len - Length
        Returns:
        cycled bit set
      • cycleLeftI

        public static long[] cycleLeftI​(long[] v,
                                        int shift,
                                        int len)
        Cycle a bitstring to the right.
        Parameters:
        v - Bit string
        shift - Number of steps to cycle
        len - Length
      • toString

        public static java.lang.String toString​(long[] v)
        Convert bitset to a string consisting of "0" and "1", in high-endian order.
        Parameters:
        v - Value to process
        Returns:
        String representation
      • toString

        public static java.lang.String toString​(long[] v,
                                                int minw)
        Convert bitset to a string consisting of "0" and "1", in high-endian order.
        Parameters:
        v - Value to process
        minw - Minimum width
        Returns:
        String representation
      • toString

        public static java.lang.String toString​(long v)
        Convert bitset to a string consisting of "0" and "1", in high-endian order.
        Parameters:
        v - Value to process
        Returns:
        String representation
      • toStringLow

        public static java.lang.String toStringLow​(long[] v)
        Convert bitset to a string consisting of "0" and "1", in low-endian order.
        Parameters:
        v - Value to process
        Returns:
        String representation
      • toStringLow

        public static java.lang.String toStringLow​(long[] v,
                                                   int minw)
        Convert bitset to a string consisting of "0" and "1", in low-endian order.
        Parameters:
        v - Value to process
        minw - Minimum width
        Returns:
        String representation
      • toStringLow

        public static java.lang.String toStringLow​(long v)
        Convert bitset to a string consisting of "0" and "1", in low-endian order.
        Parameters:
        v - Value to process
        Returns:
        String representation
      • toString

        public static java.lang.String toString​(long[] v,
                                                java.lang.String sep,
                                                int offset)
        Convert the bitset into a decimal representation, e.g., 0, 3, 5
        Parameters:
        v - Value
        sep - Value separator
        offset - Counting offset (usually, 0 or 1)
        Returns:
        String representation
      • numberOfTrailingZerosSigned

        public static int numberOfTrailingZerosSigned​(long[] v)
        Find the number of trailing zeros.
        Parameters:
        v - Bitset
        Returns:
        Position of first set bit, -1 if no set bit was found.
      • numberOfTrailingZeros

        public static int numberOfTrailingZeros​(long[] v)
        Find the number of trailing zeros.
        Parameters:
        v - Bitset
        Returns:
        Position of first set bit, v.length * 64 if no set bit was found.
      • numberOfTrailingZerosSigned

        public static int numberOfTrailingZerosSigned​(long v)
        Find the number of trailing zeros.

        Note: this has different semantics to Long.numberOfLeadingZeros(long) when the number is 0.

        Parameters:
        v - Long
        Returns:
        Position of first set bit, -1 if no set bit was found.
      • numberOfTrailingZeros

        public static int numberOfTrailingZeros​(long v)
        Find the number of trailing zeros.

        Note: this is the same as Long.numberOfTrailingZeros(long)

        Parameters:
        v - Long
        Returns:
        Position of first set bit, 64 if no set bit was found.
      • numberOfTrailingZeros

        public static int numberOfTrailingZeros​(int v)
        Find the number of trailing zeros.

        Note: this is the same as Long.numberOfTrailingZeros(long)

        Parameters:
        v - Long
        Returns:
        Position of first set bit, 64 if no set bit was found.
      • numberOfLeadingZerosSigned

        public static int numberOfLeadingZerosSigned​(long[] v)
        Find the number of leading zeros.
        Parameters:
        v - Bitset
        Returns:
        Position of first set bit, -1 if no set bit was found.
      • numberOfLeadingZeros

        public static int numberOfLeadingZeros​(long[] v)
        Find the number of leading zeros.
        Parameters:
        v - Bitset
        Returns:
        Position of first set bit, v.length * 64 if no set bit was found.
      • numberOfLeadingZerosSigned

        public static int numberOfLeadingZerosSigned​(long v)
        Find the number of leading zeros; -1 if all zero

        Note: this has different semantics to Long.numberOfLeadingZeros(long) when the number is 0.

        Parameters:
        v - Bitset
        Returns:
        Position of first set bit, -1 if no set bit was found.
      • numberOfLeadingZerosSigned

        public static int numberOfLeadingZerosSigned​(int v)
        Find the number of leading zeros; -1 if all zero

        Note: this has different semantics to Long.numberOfLeadingZeros(long) when the number is 0.

        Parameters:
        v - Bitset
        Returns:
        Position of first set bit, -1 if no set bit was found.
      • numberOfLeadingZeros

        public static int numberOfLeadingZeros​(long v)
        Find the number of leading zeros; 64 if all zero

        Note: this the same as Long.numberOfLeadingZeros(long).

        Parameters:
        v - Bitset
        Returns:
        Position of first set bit, 64 if no set bit was found.
      • numberOfLeadingZeros

        public static int numberOfLeadingZeros​(int v)
        Find the number of leading zeros; 32 if all zero

        Note: this the same as Integer.numberOfLeadingZeros(int).

        Parameters:
        v - Bitset
        Returns:
        Position of first set bit, 32 if no set bit was found.
      • previousSetBit

        public static int previousSetBit​(long v,
                                         int start)
        Find the previous set bit.
        Parameters:
        v - Value to process
        start - Start position (inclusive)
        Returns:
        Position of previous set bit, or -1.
      • previousSetBit

        public static int previousSetBit​(long[] v,
                                         int start)
        Find the previous set bit.
        Parameters:
        v - Values to process
        start - Start position (inclusive)
        Returns:
        Position of previous set bit, or -1.
      • previousClearBit

        public static int previousClearBit​(long v,
                                           int start)
        Find the previous clear bit.
        Parameters:
        v - Values to process
        start - Start position (inclusive)
        Returns:
        Position of previous clear bit, or -1.
      • previousClearBit

        public static int previousClearBit​(long[] v,
                                           int start)
        Find the previous clear bit.
        Parameters:
        v - Values to process
        start - Start position (inclusive)
        Returns:
        Position of previous clear bit, or -1.
      • nextSetBit

        public static int nextSetBit​(long v,
                                     int start)
        Find the next set bit.
        Parameters:
        v - Value to process
        start - Start position (inclusive)
        Returns:
        Position of next set bit, or -1.
      • nextSetBit

        public static int nextSetBit​(long[] v,
                                     int start)
        Find the next set bit.
        Parameters:
        v - Value to process
        start - Start position (inclusive)
        Returns:
        Position of next set bit, or -1.
      • nextClearBit

        public static int nextClearBit​(long v,
                                       int start)
        Find the next clear bit.
        Parameters:
        v - Value to process
        start - Start position (inclusive)
        Returns:
        Position of next clear bit, or -1.
      • nextClearBit

        public static int nextClearBit​(long[] v,
                                       int start)
        Find the next clear bit.
        Parameters:
        v - Value to process
        start - Start position (inclusive)
        Returns:
        Position of next clear bit, or -1.
      • magnitude

        public static int magnitude​(long[] v)
        The magnitude is the position of the highest bit set
        Parameters:
        v - Vector v
        Returns:
        position of highest bit set, or 0.
      • magnitude

        public static int magnitude​(long v)
        The magnitude is the position of the highest bit set
        Parameters:
        v - Vector v
        Returns:
        position of highest bit set, or 0.
      • magnitude

        public static int magnitude​(int v)
        The magnitude is the position of the highest bit set
        Parameters:
        v - Vector v
        Returns:
        position of highest bit set, or 0.
      • intersect

        public static boolean intersect​(long x,
                                        long y)
        Test whether two Bitsets intersect.
        Parameters:
        x - First bitset
        y - Second bitset
        Returns:
        true when the bitsets intersect.
      • intersect

        public static boolean intersect​(long[] x,
                                        long[] y)
        Test whether two Bitsets intersect.
        Parameters:
        x - First bitset
        y - Second bitset
        Returns:
        true when the bitsets intersect.
      • intersectionSize

        public static int intersectionSize​(long x,
                                           long y)
        Compute the intersection size of two Bitsets.
        Parameters:
        x - First bitset
        y - Second bitset
        Returns:
        Intersection size
      • intersectionSize

        public static int intersectionSize​(long[] x,
                                           long[] y)
        Compute the intersection size of two Bitsets.
        Parameters:
        x - First bitset
        y - Second bitset
        Returns:
        Intersection size
      • unionSize

        public static int unionSize​(long x,
                                    long y)
        Compute the union size of two Bitsets.
        Parameters:
        x - First bitset
        y - Second bitset
        Returns:
        Union size
      • unionSize

        public static int unionSize​(long[] x,
                                    long[] y)
        Compute the union size of two Bitsets.
        Parameters:
        x - First bitset
        y - Second bitset
        Returns:
        Union size
      • hammingDistance

        public static int hammingDistance​(long b1,
                                          long b2)
        Compute the Hamming distance (Size of symmetric difference), i.e. cardinality(a ^ b).
        Parameters:
        b1 - First vector
        b2 - Second vector
        Returns:
        Cardinality of symmetric difference
      • hammingDistance

        public static int hammingDistance​(long[] x,
                                          long[] y)
        Compute the Hamming distance (Size of symmetric difference), i.e. cardinality(a ^ b).
        Parameters:
        x - First vector
        y - Second vector
        Returns:
        Cardinality of symmetric difference
      • capacity

        public static int capacity​(long[] v)
        Capacity of the vector v.
        Parameters:
        v - Vector v
        Returns:
        Capacity
      • equal

        public static boolean equal​(long x,
                                    long y)
        Test two bitsets for equality
        Parameters:
        x - First bitset
        y - Second bitset
        Returns:
        true when the bitsets are equal
      • equal

        public static boolean equal​(long[] x,
                                    long[] y)
        Test two bitsets for equality
        Parameters:
        x - First bitset
        y - Second bitset
        Returns:
        true when the bitsets are equal
      • compare

        public static int compare​(long x,
                                  long y)
        Compare two bitsets.
        Parameters:
        x - First bitset
        y - Second bitset
        Returns:
        Comparison result
      • compare

        public static int compare​(long[] x,
                                  long[] y)
        Compare two bitsets.
        Parameters:
        x - First bitset
        y - Second bitset
        Returns:
        Comparison result
      • hashCode

        public static int hashCode​(long x)
        Compute a hash code for the given bitset.
        Parameters:
        x - Bitset bitset
        Returns:
        Hash code
      • hashCode

        public static int hashCode​(long[] x)
        Compute a hash code for the given bitset.
        Parameters:
        x - Bitset bitset
        Returns:
        Hash code
      • lpow2

        public static double lpow2​(long m,
                                   int n)
        Compute m * pow(2., n) using bit operations.
        Parameters:
        m - Mantissa
        n - Exponent
        Returns:
        Double value
      • lpow10

        public static double lpow10​(long m,
                                    int n)
        Compute m * Math.pow(10,e) on the bit representation, for assembling a floating point decimal value.
        Parameters:
        m - Mantisse
        n - Exponent to base 10.
        Returns:
        Double value.