Class 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
      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, int[] bits)
      Initializes a bit vector from an array of ints.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      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.
      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()  
      void xor​(BitVector other)
      Computes the bitwise XOR of this BitVector and another BitVector.
    • Constructor Detail

      • 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.
    • Method Detail

      • 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
      • 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:
        BitVector.BitIterator
      • 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:
        BitVector.BitIterator