Module org.cicirello.chips_n_salsa
Package org.cicirello.search.representations

Class BitVector

java.lang.Object
org.cicirello.search.representations.BitVector
All Implemented Interfaces:
Copyable<BitVector>
public final class BitVector extends Object implements Copyable<BitVector>
A BitVector is an indexable vector of bits. It supports operations for manipulating the bits in a variety of ways, such as setting and getting, flipping, left and right shifts, computing bitwise operators (and, or, xor) between pairs of equal length BitVectors, etc. It also supports iterating over the bits, either one bit at a time, or groups of bits. Indexes into a BitVector begin at 0, and index 0 refers to the least significant bit ("right-most" bit).

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    final class 
    BitVector.BitIterator
    The BitIterator class enables iterating over the bits of a BitVector.

  • Constructor Summary

    Constructors
    Constructor
    Description
    BitVector(int bitLength)
    Initializes the bit vector to a vector of all 0 bits.
    BitVector(int bitLength, boolean randomize)
    Initializes the bit vector.
    BitVector(int bitLength, double p)
    Initializes a bit vector randomly given probability of 1-bit.
    BitVector(int bitLength, double p, EnhancedRandomGenerator generator)
    Initializes a bit vector randomly given probability of 1-bit.
    BitVector(int bitLength, int[] bits)
    Initializes a bit vector from an array of ints.
    BitVector(int bitLength, EnhancedRandomGenerator generator)
    Initializes the BitVector as a random vector of bits, with 0 and 1 equally likely for each bit.

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    allOnes()
    Check if the BitVector contains all 1-bits.
    boolean
    allZeros()
    Check if the BitVector contains all 0-bits.
    void
    and(BitVector other)
    Computes the bitwise AND of this BitVector and another BitVector.
    boolean
    anyOnes()
    Check if the BitVector contains any bits equal to a 1.
    boolean
    anyZeros()
    Check if the BitVector contains any bits equal to a 0.
    BitVector.BitIterator
    bitIterator()
    Creates a BitIterator to iterate over the bits of this BitVector, one bit at a time.
    BitVector.BitIterator
    bitIterator(int k)
    Creates a BitIterator to iterate over the bits of this BitVector.
    BitVector
    copy()
    Creates an identical copy of this object.
    int
    countOnes()
    Counts the number of bits in the bit vector whose value is a 1.
    int
    countZeros()
    Counts the number of bits in the bit vector whose value is a 0.
    boolean
    equals(Object other)
    Indicates whether some other object is equal to this one.
    static void
    exchangeBits(BitVector b1, BitVector b2, int firstIndex, int lastIndex)
    Exchanges a sequence of bits between two BitVector objects.
    static void
    exchangeBits(BitVector b1, BitVector b2, BitVector mask)
    Exchanges a selection of bits between two BitVectors, where the bits to exchange are indicated by a bit mask, also represented by a BitVector.
    void
    flip(int index)
    Flips the value of the bit at the specified index (e.g., if it is a 0, then change to a 1; if it is a 1, change to a 0).
    int
    get32(int i)
    Gets a block of up to 32 bits.
    int
    getBit(int index)
    Gets the value of the bit at a designated index.
    int
    hashCode()
    Returns a hash code value for the object.
    boolean
    isOne(int index)
    Checks if the bit at a designated index is equal to a 1.
    boolean
    isZero(int index)
    Checks if the bit at a designated index is equal to a 0.
    int
    length()
    Gets the length of the bit vector in number of bits.
    void
    not()
    Computes the bitwise complement of this BitVector.
    void
    or(BitVector other)
    Computes the bitwise OR of this BitVector and another BitVector.
    void
    set32(int i, int block)
    Sets a block of up to 32 bits.
    void
    setBit(int index, int bitValue)
    Sets the value of the bit at a designated index.
    void
    shiftLeft(int numBits)
    Performs a left shift of the bits of the BitVector, with 0s filling in on the right.
    void
    shiftRight(int numBits)
    Performs a right shift of the bits of the BitVector, with 0s filling in on the left.
    String
    toString()
    Returns a String representation of the BitVector.
    void
    xor(BitVector other)
    Computes the bitwise XOR of this BitVector and another BitVector.

    Methods inherited from class java.lang.Object

    clone, finalize, getClass, notify, notifyAll, wait, wait, wait

  • Constructor Details

    • BitVector

      public BitVector(int bitLength)
      Initializes the bit vector to a vector of all 0 bits.
      Parameters:
      bitLength - The length of the bit vector in number of bits.
      Throws:
      IllegalArgumentException - if bitLength < 0.

    • BitVector

      public BitVector(int bitLength, boolean randomize)
      Initializes the bit vector.
      Parameters:
      bitLength - The length of the bit vector in number of bits.
      randomize - if true, then the vector is initialized with random bit values; and otherwise initializes it to a vector of all 0 bits.
      Throws:
      IllegalArgumentException - if bitLength < 0.

    • BitVector

      public BitVector(int bitLength, int[] bits)
      Initializes a bit vector from an array of ints.
      Parameters:
      bitLength - The length of the bit vector in number of bits.
      bits - An array of ints containing the bits for initializing the BitVector.
      Throws:
      IllegalArgumentException - if bitLength < 0 or if bits.length is longer than necessary for a vector of bitLength bits or if bits.length is too short for a vector of bitLength bits.

    • BitVector

      public BitVector(int bitLength, double p)
      Initializes a bit vector randomly given probability of 1-bit.
      Parameters:
      bitLength - The length of the bit vector in number of bits.
      p - The probability, in [0.0, 1.0], that each bit is a 1.
      Throws:
      IllegalArgumentException - if bitLength < 0 .

    • BitVector

      public BitVector(int bitLength, EnhancedRandomGenerator generator)
      Initializes the BitVector as a random vector of bits, with 0 and 1 equally likely for each bit.
      Parameters:
      bitLength - The length of the bit vector in number of bits.
      generator - The source of randomness.
      Throws:
      IllegalArgumentException - if bitLength < 0.
      NullPointerException - if generator is null.

    • BitVector

      public BitVector(int bitLength, double p, EnhancedRandomGenerator generator)
      Initializes a bit vector randomly given probability of 1-bit.
      Parameters:
      bitLength - The length of the bit vector in number of bits.
      p - The probability, in [0.0, 1.0], that each bit is a 1.
      generator - The source of randomness.
      Throws:
      IllegalArgumentException - if bitLength < 0.
      NullPointerException - if generator is null.

  • Method Details

    • exchangeBits

      public static void exchangeBits(BitVector b1, BitVector b2, int firstIndex, int lastIndex)
      Exchanges a sequence of bits between two BitVector objects.
      Parameters:
      b1 - The first BitVector.
      b2 - The second BitVector.
      firstIndex - The first index of the sequence to exchange, inclusive.
      lastIndex - The last index of the sequence to exchange, inclusive.
      Throws:
      IllegalArgumentException - if b1.length() is not equal to b2.length()
      IndexOutOfBoundsException - if either index is negative, or if either index ≥ length()

    • exchangeBits

      public static void exchangeBits(BitVector b1, BitVector b2, BitVector mask)
      Exchanges a selection of bits between two BitVectors, where the bits to exchange are indicated by a bit mask, also represented by a BitVector.
      Parameters:
      b1 - The first BitVector.
      b2 - The second BitVector.
      mask - A bit mask indicating which bit positions to exchange. Specifically, if mask.getBit(i) is a 1, then b1 and b2 will trade the bits in position i between each other, and otherwise they won't.
      Throws:
      IllegalArgumentException - if the lengths of b1, b2, and mask, are not all the same.

    • allZeros

      public boolean allZeros()
      Check if the BitVector contains all 0-bits.
      Returns:
      true If all of the bits are equal to 0, and false otherwise. Note that if the length of the BitVector is 0, this method returns true.

    • allOnes

      public boolean allOnes()
      Check if the BitVector contains all 1-bits.
      Returns:
      true If all of the bits are equal to 1, and false otherwise. Note that if the length of the BitVector is 0, this method returns true.

    • anyOnes

      public boolean anyOnes()
      Check if the BitVector contains any bits equal to a 1.
      Returns:
      true If there is at least one 1-bit, and false otherwise. Note that if the length of the BitVector is 0, this method returns false.

    • anyZeros

      public boolean anyZeros()
      Check if the BitVector contains any bits equal to a 0.
      Returns:
      true If there is at least one 0-bit, and false otherwise. Note that if the length of the BitVector is 0, this method returns false.

    • length

      public int length()
      Gets the length of the bit vector in number of bits.
      Returns:
      The length of the bit vector in number of bits.

    • getBit

      public int getBit(int index)
      Gets the value of the bit at a designated index.
      Parameters:
      index - The index into the bit vector, which must be 0 ≤ index < length().
      Returns:
      The value of the bit at position index, as an int. The least significant bit of the returned int will hold the value of the bit. The other 31 bits will be 0.
      Throws:
      IndexOutOfBoundsException - if index is negative, or if index ≥ length()

    • setBit

      public void setBit(int index, int bitValue)
      Sets the value of the bit at a designated index.
      Parameters:
      index - The index into the bit vector, which must be 0 ≤ index < length().
      bitValue - The value to set for the bit at position index. The least significant bit of this int is used.
      Throws:
      IndexOutOfBoundsException - if index is negative, or if index ≥ length()

    • flip

      public void flip(int index)
      Flips the value of the bit at the specified index (e.g., if it is a 0, then change to a 1; if it is a 1, change to a 0).
      Parameters:
      index - The index into the bit vector, which must be 0 ≤ index < length().
      Throws:
      IndexOutOfBoundsException - if index is negative, or if index ≥ length()

    • isOne

      public boolean isOne(int index)
      Checks if the bit at a designated index is equal to a 1.
      Parameters:
      index - The index into the bit vector, which must be 0 ≤ index < length().
      Returns:
      true if and only if the value of the bit at position index is equal to 1
      Throws:
      IndexOutOfBoundsException - if index is negative, or if index ≥ length()

    • isZero

      public boolean isZero(int index)
      Checks if the bit at a designated index is equal to a 0.
      Parameters:
      index - The index into the bit vector, which must be 0 ≤ index < length().
      Returns:
      true if and only if the value of the bit at position index is equal to 0
      Throws:
      IndexOutOfBoundsException - if index is negative, or if index ≥ length()

    • get32

      public int get32(int i)
      Gets a block of up to 32 bits.
      Parameters:
      i - The block of bits accessed by this method begins at the bit with index 32*i.
      Returns:
      Up to 32 bits beginning at the bit at index 32*i. For example, if i is 0, then this method will return the 32 bits beginning at index 32*0=0, i.e., bits 0 through 31. Bit 0 will be in the least significant position, and bit 31 will be in the most significant position. If i is 1, then this method returns the 32 bits beginning with the bit at index 32 (i.e., bits 32 through 63). If there are less than 32 bits beginning at index 32*i, then the relevant bits will be in the least significant positions of the returned int.
      Throws:
      IndexOutOfBoundsException - if i is negative, or if 32*i ≥ length()

    • set32

      public void set32(int i, int block)
      Sets a block of up to 32 bits.
      Parameters:
      i - The block of bits set by this method begins at the bit with index 32*i. For example, if i is 0, then this method will set the 32 bits beginning at index 32*0=0, i.e., bits 0 through 31. Bit 0 will be in the least significant position, and bit 31 will be in the most significant position. If i is 1, then this method sets the 32 bits beginning with the bit at index 32 (i.e., bits 32 through 63).
      block - The block of bits to set. The least significant bit of block will be stored at index 32*i.
      Throws:
      IndexOutOfBoundsException - if i is negative, or if 32*i ≥ length()

    • countOnes

      public int countOnes()
      Counts the number of bits in the bit vector whose value is a 1.
      Returns:
      the count of the number of bits equal to 1.

    • countZeros

      public int countZeros()
      Counts the number of bits in the bit vector whose value is a 0.
      Returns:
      the count of the number of bits equal to 0.

    • and

      public void and(BitVector other)
      Computes the bitwise AND of this BitVector and another BitVector. This BitVector is updated with the result.
      Parameters:
      other - The other BitVector.
      Throws:
      IllegalArgumentException - if the BitVectors are of different lengths.

    • or

      public void or(BitVector other)
      Computes the bitwise OR of this BitVector and another BitVector. This BitVector is updated with the result.
      Parameters:
      other - The other BitVector.
      Throws:
      IllegalArgumentException - if the BitVectors are of different lengths.

    • xor

      public void xor(BitVector other)
      Computes the bitwise XOR of this BitVector and another BitVector. This BitVector is updated with the result.
      Parameters:
      other - The other BitVector.
      Throws:
      IllegalArgumentException - if the BitVectors are of different lengths.

    • not

      public void not()
      Computes the bitwise complement of this BitVector. This BitVector is updated with the result.

    • shiftLeft

      public void shiftLeft(int numBits)
      Performs a left shift of the bits of the BitVector, with 0s filling in on the right. Specifically, the value of the bit in index i before a call to shiftLeft, will move to index (i + numBits). The method does not change the length of the BitVector, so the numBits bits on the left end of the BitVector before the call are lost.
      Parameters:
      numBits - The number of bits to shift to the left.

    • shiftRight

      public void shiftRight(int numBits)
      Performs a right shift of the bits of the BitVector, with 0s filling in on the left. Specifically, the value of the bit in index i before a call to shiftLeft, will move to index (i - numBits). The numBits bits on the right end of the BitVector before the call are lost.
      Parameters:
      numBits - The number of bits to shift to the right.

    • copy

      public BitVector copy()
      Creates an identical copy of this object.
      Specified by:
      copy in interface Copyable<BitVector>
      Returns:
      an identical copy of this object

    • equals

      public boolean equals(Object other)
      Indicates whether some other object is equal to this one. The objects are equal if they are the same type of operator with the same parameters.
      Overrides:
      equals in class Object
      Parameters:
      other - the object with which to compare
      Returns:
      true if and only if the objects are equal

    • hashCode

      public int hashCode()
      Returns a hash code value for the object. This method is supported for the benefit of hash tables such as those provided by HashMap.
      Overrides:
      hashCode in class Object
      Returns:
      a hash code value for this object

    • toString

      public String toString()
      Returns a String representation of the BitVector.
      Overrides:
      toString in class Object
      Returns:
      a String representation of the BitVector.

    • bitIterator

      public BitVector.BitIterator bitIterator(int k)
      Creates a BitIterator to iterate over the bits of this BitVector.
      Parameters:
      k - The number of bits for the BitIterator to return at a time. For example, if k is 3, then each call to BitVector.BitIterator.nextBitBlock() will return an int containing the next 3 bits from the BitVector in the least significant 3 places. The value of k must be 0 < k ≤ 32.
      Returns:
      A BitIterator object to iterate over the bits of this BitVector.
      Throws:
      IllegalArgumentException - if k ≤ 0 or if k > 32
      See Also:

    • bitIterator

      public BitVector.BitIterator bitIterator()
      Creates a BitIterator to iterate over the bits of this BitVector, one bit at a time.
      Returns:
      A BitIterator object to iterate over the bits of this BitVector.
      See Also: