BitsUtil (ELKI: Environment for DeveLoping KDD-Applications Supported by Index-Structures)

java.lang.Object
- de.lmu.ifi.dbs.elki.utilities.BitsUtil

```
public final class BitsUtil
extends 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.

Field Summary

Fields
Modifier and Type	Field and Description
`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

Constructor Summary

Constructors
Constructor and Description

BitsUtil()

Constructors
Constructor and Description
`BitsUtil()`

Method Summary

Methods
Modifier and Type	Method and Description
`static long[]`	`andI(long[] v, long[] o)` AND o onto v inplace, i.e. v &= o
`static long[]`	`andI(long[] v, long[] o, int off)` AND o onto v inplace, 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 long`	`cardinality(long[] v)` Compute the cardinality (number of set bits) Low-endian layout for the array.
`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 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 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 long[]`	`invertI(long[] v)` Invert v inplace.
`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 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 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`	`numberOfLeadingZeros(int v)` Find the number of leading zeros; 32 if all zero Note: this the same as `Integer.numberOfLeadingZeros(int)`.
`static int`	`numberOfLeadingZeros(long v)` Find the number of leading zeros; 64 if all zero Note: this the same as `Long.numberOfLeadingZeros(long)`.
`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 Note: this has different semantics to `Long.numberOfLeadingZeros(long)` when the number is 0.
`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.
`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[]`	`ones(int bits)` Create a vector initialized with "bits" ones.
`static long[]`	`orI(long[] v, long[] o)` OR o onto v inplace, i.e. v \|= o
`static long[]`	`orI(long[] v, long[] o, int off)` OR o onto v inplace, i.e. v \|= (o << off) Note: Bits that are shifted outside of the size of v are discarded.
`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 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[]`	`shiftLeftI(long[] v, int off)` Shift a long[] bitset inplace.
`static long[]`	`shiftRightI(long[] v, int off)` Shift a long[] bitset inplace.
`static String`	`toString(long v)` Convert bitset to a string consisting of "0" and "1", in high-endian order.
`static String`	`toString(long[] v)` Convert bitset to a string consisting of "0" and "1", in high-endian order.
`static String`	`toString(long[] v, int minw)` Convert bitset to a string consisting of "0" and "1", in high-endian order.
`static long[]`	`truncateI(long[] v, int len)` Truncate a bit string to the given length (setting any higher bit to 0).
`static long[]`	`xorI(long[] v, long[] o)` XOR o onto v inplace, i.e. v ^= o
`static long[]`	`xorI(long[] v, long[] o, int off)` XOR o onto v inplace, 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
- Constructor Detail
  - BitsUtil
```
public BitsUtil()
```
- 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
  - ones
```
public static long[] ones(int bits)
```
    Create a vector initialized with "bits" ones.
    
    Parameters:
    bits - Size
    
    Returns:
    new vector
  - 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 long 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
  - 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
  - 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 inplace, 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 inplace, 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 inplace, 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 inplace, 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 inplace, 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 inplace, i.e. v &= (o << off)
    
    Parameters:
    v - Primary object
    o - data to or
    off - Offset
    
    Returns:
    v
  - invertI
```
public static long[] invertI(long[] v)
```
    Invert v inplace.
    
    Parameters:
    v - Object to invert
    
    Returns:
    v
  - shiftRightI
```
public static long[] shiftRightI(long[] v,
                 int off)
```
    Shift a long[] bitset inplace. 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 inplace. 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 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 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 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
  - 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 - 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.
  - 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.
  - 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.
  - capacity
```
public static int capacity(long[] v)
```
    Capacity of the vector v.
    
    Parameters:
    v - Vector v
    
    Returns:
    Capacity
  - compare
```
public static int compare(long[] x,
          long[] y)
```
    Compare two bitsets.
    
    Parameters:
    x - First bitset
    y - Second bitset
    
    Returns:
    Comparison result

Class BitsUtil

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

LONG_LOG2_SIZE

LONG_LOG2_MASK

LONG_ALL_BITS

Constructor Detail

BitsUtil

Method Detail

zero

make

ones

copy

copy

copy

grayC

grayI

invgrayC

invgrayI

isZero

cardinality

cardinality

flipC

flipI

setC

setI

clearC

clearI

get

get

zeroI

xorI

xorI

orI

orI

andI

andI

invertI

shiftRightI

shiftLeftI

cycleRightC

cycleRightI

truncateI

cycleLeftC

cycleLeftI

toString

toString

toString

numberOfTrailingZerosSigned

numberOfTrailingZeros

numberOfTrailingZerosSigned

numberOfTrailingZeros

numberOfTrailingZeros

numberOfLeadingZerosSigned

numberOfLeadingZeros

numberOfLeadingZerosSigned

numberOfLeadingZerosSigned

numberOfLeadingZeros

numberOfLeadingZeros

previousSetBit

previousClearBit

nextSetBit

nextClearBit

magnitude

magnitude

magnitude

capacity

compare