java.util: public class: BitSet

java.util
public class: BitSet [javadoc | source]

java.lang.Object
   java.util.BitSet

All Implemented Interfaces:
Cloneable, Serializable

This class implements a vector of bits that grows as needed. Each component of the bit set has a {@code boolean} value. The bits of a {@code BitSet} are indexed by nonnegative integers. Individual indexed bits can be examined, set, or cleared. One {@code BitSet} may be used to modify the contents of another {@code BitSet} through logical AND, logical inclusive OR, and logical exclusive OR operations.

By default, all bits in the set initially have the value {@code false}.

Every bit set has a current size, which is the number of bits of space currently in use by the bit set. Note that the size is related to the implementation of a bit set, so it may change with implementation. The length of a bit set relates to logical length of a bit set and is defined independently of implementation.

Unless otherwise noted, passing a null parameter to any of the methods in a {@code BitSet} will result in a {@code NullPointerException}.

A {@code BitSet} is not safe for multithreaded use without external synchronization.

author: Arthur - van Hoff

author: Michael - McCloskey

author: Martin - Buchholz

since: JDK1.0 -

Constructor:

Constructor:
public BitSet() { initWords(BITS_PER_WORD); sizeIsSticky = false; } Creates a new bit set. All bits are initially {@code false}.
public BitSet(int nbits) { // nbits can't be negative; size 0 is OK if (nbits < 0) throw new NegativeArraySizeException("nbits < 0: " + nbits); initWords(nbits); sizeIsSticky = true; } Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range {@code 0} through {@code nbits-1}. All bits are initially {@code false}. Parameters: `nbits` - the initial size of the bit set Throws: `NegativeArraySizeException` - if the specified initial size is negative

 public BitSet() {
        initWords(BITS_PER_WORD);
        sizeIsSticky = false;
}

Creates a new bit set. All bits are initially {@code false}.

 public BitSet(int nbits) {
        // nbits can't be negative; size 0 is OK
        if (nbits <  0)
            throw new NegativeArraySizeException("nbits <  0: " + nbits);
        initWords(nbits);
        sizeIsSticky = true;
}

Creates a bit set whose initial size is large enough to explicitly represent bits with indices in the range {@code 0} through {@code nbits-1}. All bits are initially {@code false}.

Parameters:

nbits - the initial size of the bit set

Throws:

NegativeArraySizeException - if the specified initial size is negative

Method from java.util.BitSet Summary:
and, andNot, cardinality, clear, clear, clear, clone, equals, flip, flip, get, get, hashCode, intersects, isEmpty, length, nextClearBit, nextSetBit, or, previousClearBit, previousSetBit, set, set, set, set, size, toByteArray, toLongArray, toString, valueOf, valueOf, valueOf, valueOf, xor

Methods from java.lang.Object:
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method from java.util.BitSet Detail:
public void and(BitSet set) { if (this == set) return; while (wordsInUse > set.wordsInUse) words[--wordsInUse] = 0; // Perform logical AND on words in common for (int i = 0; i < wordsInUse; i++) words[i] &= set.words[i]; recalculateWordsInUse(); checkInvariants(); } Performs a logical AND of this target bit set with the argument bit set. This bit set is modified so that each bit in it has the value {@code true} if and only if it both initially had the value {@code true} and the corresponding bit in the bit set argument also had the value {@code true}.
public void andNot(BitSet set) { // Perform logical (a & !b) on words in common for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--) words[i] &= ~set.words[i]; recalculateWordsInUse(); checkInvariants(); } Clears all of the bits in this {@code BitSet} whose corresponding bit is set in the specified {@code BitSet}.
public int cardinality() { int sum = 0; for (int i = 0; i < wordsInUse; i++) sum += Long.bitCount(words[i]); return sum; } Returns the number of bits set to {@code true} in this {@code BitSet}.
public void clear() { while (wordsInUse > 0) words[--wordsInUse] = 0; } Sets all of the bits in this BitSet to {@code false}.
public void clear(int bitIndex) { if (bitIndex < 0) throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex); int wordIndex = wordIndex(bitIndex); if (wordIndex >= wordsInUse) return; words[wordIndex] &= ~(1L < < bitIndex); recalculateWordsInUse(); checkInvariants(); } Sets the bit specified by the index to {@code false}.
public void clear(int fromIndex, int toIndex) { checkRange(fromIndex, toIndex); if (fromIndex == toIndex) return; int startWordIndex = wordIndex(fromIndex); if (startWordIndex >= wordsInUse) return; int endWordIndex = wordIndex(toIndex - 1); if (endWordIndex >= wordsInUse) { toIndex = length(); endWordIndex = wordsInUse - 1; } long firstWordMask = WORD_MASK < < fromIndex; long lastWordMask = WORD_MASK > > > -toIndex; if (startWordIndex == endWordIndex) { // Case 1: One word words[startWordIndex] &= ~(firstWordMask & lastWordMask); } else { // Case 2: Multiple words // Handle first word words[startWordIndex] &= ~firstWordMask; // Handle intermediate words, if any for (int i = startWordIndex+1; i < endWordIndex; i++) words[i] = 0; // Handle last word words[endWordIndex] &= ~lastWordMask; } recalculateWordsInUse(); checkInvariants(); } Sets the bits from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (exclusive) to {@code false}.
public Object clone() { if (! sizeIsSticky) trimToSize(); try { BitSet result = (BitSet) super.clone(); result.words = words.clone(); result.checkInvariants(); return result; } catch (CloneNotSupportedException e) { throw new InternalError(); } } Cloning this {@code BitSet} produces a new {@code BitSet} that is equal to it. The clone of the bit set is another bit set that has exactly the same bits set to {@code true} as this bit set.
public boolean equals(Object obj) { if (!(obj instanceof BitSet)) return false; if (this == obj) return true; BitSet set = (BitSet) obj; checkInvariants(); set.checkInvariants(); if (wordsInUse != set.wordsInUse) return false; // Check words in use by both BitSets for (int i = 0; i < wordsInUse; i++) if (words[i] != set.words[i]) return false; return true; } Compares this object against the specified object. The result is {@code true} if and only if the argument is not {@code null} and is a {@code Bitset} object that has exactly the same set of bits set to {@code true} as this bit set. That is, for every nonnegative {@code int} index {@code k}, ((BitSet)obj).get(k) == this.get(k) must be true. The current sizes of the two bit sets are not compared.
public void flip(int bitIndex) { if (bitIndex < 0) throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex); int wordIndex = wordIndex(bitIndex); expandTo(wordIndex); words[wordIndex] ^= (1L < < bitIndex); recalculateWordsInUse(); checkInvariants(); } Sets the bit at the specified index to the complement of its current value.
public void flip(int fromIndex, int toIndex) { checkRange(fromIndex, toIndex); if (fromIndex == toIndex) return; int startWordIndex = wordIndex(fromIndex); int endWordIndex = wordIndex(toIndex - 1); expandTo(endWordIndex); long firstWordMask = WORD_MASK < < fromIndex; long lastWordMask = WORD_MASK > > > -toIndex; if (startWordIndex == endWordIndex) { // Case 1: One word words[startWordIndex] ^= (firstWordMask & lastWordMask); } else { // Case 2: Multiple words // Handle first word words[startWordIndex] ^= firstWordMask; // Handle intermediate words, if any for (int i = startWordIndex+1; i < endWordIndex; i++) words[i] ^= WORD_MASK; // Handle last word words[endWordIndex] ^= lastWordMask; } recalculateWordsInUse(); checkInvariants(); } Sets each bit from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (exclusive) to the complement of its current value.
public boolean get(int bitIndex) { if (bitIndex < 0) throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex); checkInvariants(); int wordIndex = wordIndex(bitIndex); return (wordIndex < wordsInUse) && ((words[wordIndex] & (1L < < bitIndex)) != 0); } Returns the value of the bit with the specified index. The value is {@code true} if the bit with the index {@code bitIndex} is currently set in this {@code BitSet}; otherwise, the result is {@code false}.
public BitSet get(int fromIndex, int toIndex) { checkRange(fromIndex, toIndex); checkInvariants(); int len = length(); // If no set bits in range return empty bitset if (len < = fromIndex \|\| fromIndex == toIndex) return new BitSet(0); // An optimization if (toIndex > len) toIndex = len; BitSet result = new BitSet(toIndex - fromIndex); int targetWords = wordIndex(toIndex - fromIndex - 1) + 1; int sourceIndex = wordIndex(fromIndex); boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0); // Process all words but the last word for (int i = 0; i < targetWords - 1; i++, sourceIndex++) result.words[i] = wordAligned ? words[sourceIndex] : (words[sourceIndex] > > > fromIndex) \| (words[sourceIndex+1] < < -fromIndex); // Process the last word long lastWordMask = WORD_MASK > > > -toIndex; result.words[targetWords - 1] = ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK) ? /* straddles source words */ ((words[sourceIndex] > > > fromIndex) \| (words[sourceIndex+1] & lastWordMask) < < -fromIndex) : ((words[sourceIndex] & lastWordMask) > > > fromIndex); // Set wordsInUse correctly result.wordsInUse = targetWords; result.recalculateWordsInUse(); result.checkInvariants(); return result; } Returns a new {@code BitSet} composed of bits from this {@code BitSet} from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).
public int hashCode() { long h = 1234; for (int i = wordsInUse; --i >= 0; ) h ^= words[i] * (i + 1); return (int)((h > > 32) ^ h); } Returns the hash code value for this bit set. The hash code depends only on which bits are set within this {@code BitSet}. The hash code is defined to be the result of the following calculation: {@code public int hashCode() { long h = 1234; long[] words = toLongArray(); for (int i = words.length; --i >= 0; ) h ^= words[i] * (i + 1); return (int)((h >> 32) ^ h); }} Note that the hash code changes if the set of bits is altered.
public boolean intersects(BitSet set) { for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--) if ((words[i] & set.words[i]) != 0) return true; return false; } Returns true if the specified {@code BitSet} has any bits set to {@code true} that are also set to {@code true} in this {@code BitSet}.
public boolean isEmpty() { return wordsInUse == 0; } Returns true if this {@code BitSet} contains no bits that are set to {@code true}.
public int length() { if (wordsInUse == 0) return 0; return BITS_PER_WORD * (wordsInUse - 1) + (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1])); } Returns the "logical size" of this {@code BitSet}: the index of the highest set bit in the {@code BitSet} plus one. Returns zero if the {@code BitSet} contains no set bits.
public int nextClearBit(int fromIndex) { // Neither spec nor implementation handle bitsets of maximal length. // See 4816253. if (fromIndex < 0) throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex); checkInvariants(); int u = wordIndex(fromIndex); if (u >= wordsInUse) return fromIndex; long word = ~words[u] & (WORD_MASK < < fromIndex); while (true) { if (word != 0) return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word); if (++u == wordsInUse) return wordsInUse * BITS_PER_WORD; word = ~words[u]; } } Returns the index of the first bit that is set to {@code false} that occurs on or after the specified starting index.
public int nextSetBit(int fromIndex) { if (fromIndex < 0) throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex); checkInvariants(); int u = wordIndex(fromIndex); if (u >= wordsInUse) return -1; long word = words[u] & (WORD_MASK < < fromIndex); while (true) { if (word != 0) return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word); if (++u == wordsInUse) return -1; word = words[u]; } } Returns the index of the first bit that is set to {@code true} that occurs on or after the specified starting index. If no such bit exists then {@code -1} is returned. To iterate over the {@code true} bits in a {@code BitSet}, use the following loop: {@code for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) { // operate on index i here }}
public void or(BitSet set) { if (this == set) return; int wordsInCommon = Math.min(wordsInUse, set.wordsInUse); if (wordsInUse < set.wordsInUse) { ensureCapacity(set.wordsInUse); wordsInUse = set.wordsInUse; } // Perform logical OR on words in common for (int i = 0; i < wordsInCommon; i++) words[i] \|= set.words[i]; // Copy any remaining words if (wordsInCommon < set.wordsInUse) System.arraycopy(set.words, wordsInCommon, words, wordsInCommon, wordsInUse - wordsInCommon); // recalculateWordsInUse() is unnecessary checkInvariants(); } Performs a logical OR of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value {@code true} if and only if it either already had the value {@code true} or the corresponding bit in the bit set argument has the value {@code true}.
public int previousClearBit(int fromIndex) { if (fromIndex < 0) { if (fromIndex == -1) return -1; throw new IndexOutOfBoundsException( "fromIndex < -1: " + fromIndex); } checkInvariants(); int u = wordIndex(fromIndex); if (u >= wordsInUse) return fromIndex; long word = ~words[u] & (WORD_MASK > > > -(fromIndex+1)); while (true) { if (word != 0) return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word); if (u-- == 0) return -1; word = ~words[u]; } } Returns the index of the nearest bit that is set to {@code false} that occurs on or before the specified starting index. If no such bit exists, or if {@code -1} is given as the starting index, then {@code -1} is returned.
public int previousSetBit(int fromIndex) { if (fromIndex < 0) { if (fromIndex == -1) return -1; throw new IndexOutOfBoundsException( "fromIndex < -1: " + fromIndex); } checkInvariants(); int u = wordIndex(fromIndex); if (u >= wordsInUse) return length() - 1; long word = words[u] & (WORD_MASK > > > -(fromIndex+1)); while (true) { if (word != 0) return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word); if (u-- == 0) return -1; word = words[u]; } } Returns the index of the nearest bit that is set to {@code true} that occurs on or before the specified starting index. If no such bit exists, or if {@code -1} is given as the starting index, then {@code -1} is returned. To iterate over the {@code true} bits in a {@code BitSet}, use the following loop: {@code for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) { // operate on index i here }}
public void set(int bitIndex) { if (bitIndex < 0) throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex); int wordIndex = wordIndex(bitIndex); expandTo(wordIndex); words[wordIndex] \|= (1L < < bitIndex); // Restores invariants checkInvariants(); } Sets the bit at the specified index to {@code true}.
public void set(int bitIndex, boolean value) { if (value) set(bitIndex); else clear(bitIndex); } Sets the bit at the specified index to the specified value.
public void set(int fromIndex, int toIndex) { checkRange(fromIndex, toIndex); if (fromIndex == toIndex) return; // Increase capacity if necessary int startWordIndex = wordIndex(fromIndex); int endWordIndex = wordIndex(toIndex - 1); expandTo(endWordIndex); long firstWordMask = WORD_MASK < < fromIndex; long lastWordMask = WORD_MASK > > > -toIndex; if (startWordIndex == endWordIndex) { // Case 1: One word words[startWordIndex] \|= (firstWordMask & lastWordMask); } else { // Case 2: Multiple words // Handle first word words[startWordIndex] \|= firstWordMask; // Handle intermediate words, if any for (int i = startWordIndex+1; i < endWordIndex; i++) words[i] = WORD_MASK; // Handle last word (restores invariants) words[endWordIndex] \|= lastWordMask; } checkInvariants(); } Sets the bits from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (exclusive) to {@code true}.
public void set(int fromIndex, int toIndex, boolean value) { if (value) set(fromIndex, toIndex); else clear(fromIndex, toIndex); } Sets the bits from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (exclusive) to the specified value.
public int size() { return words.length * BITS_PER_WORD; } Returns the number of bits of space actually in use by this {@code BitSet} to represent bit values. The maximum element in the set is the size - 1st element.
public byte[] toByteArray() { int n = wordsInUse; if (n == 0) return new byte[0]; int len = 8 * (n-1); for (long x = words[n - 1]; x != 0; x > > >= 8) len++; byte[] bytes = new byte[len]; ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN); for (int i = 0; i < n - 1; i++) bb.putLong(words[i]); for (long x = words[n - 1]; x != 0; x > > >= 8) bb.put((byte) (x & 0xff)); return bytes; } Returns a new byte array containing all the bits in this bit set. More precisely, if {@code byte[] bytes = s.toByteArray();} then {@code bytes.length == (s.length()+7)/8} and {@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)} for all {@code n < 8 * bytes.length}.
public long[] toLongArray() { return Arrays.copyOf(words, wordsInUse); } Returns a new long array containing all the bits in this bit set. More precisely, if {@code long[] longs = s.toLongArray();} then {@code longs.length == (s.length()+63)/64} and {@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)} for all {@code n < 64 * longs.length}.
public String toString() { checkInvariants(); int numBits = (wordsInUse > 128) ? cardinality() : wordsInUse * BITS_PER_WORD; StringBuilder b = new StringBuilder(6*numBits + 2); b.append('{"); int i = nextSetBit(0); if (i != -1) { b.append(i); for (i = nextSetBit(i+1); i >= 0; i = nextSetBit(i+1)) { int endOfRun = nextClearBit(i); do { b.append(", ").append(i); } while (++i < endOfRun); } } b.append('}"); return b.toString(); } Returns a string representation of this bit set. For every index for which this {@code BitSet} contains a bit in the set state, the decimal representation of that index is included in the result. Such indices are listed in order from lowest to highest, separated by ", " (a comma and a space) and surrounded by braces, resulting in the usual mathematical notation for a set of integers. Example: BitSet drPepper = new BitSet(); Now {@code drPepper.toString()} returns "{@code {}}". drPepper.set(2); Now {@code drPepper.toString()} returns "{@code {2}}". drPepper.set(4); drPepper.set(10); Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
public static BitSet valueOf(long[] longs) { int n; for (n = longs.length; n > 0 && longs[n - 1] == 0; n--) ; return new BitSet(Arrays.copyOf(longs, n)); } Returns a new bit set containing all the bits in the given long array. More precisely, {@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)} for all {@code n < 64 * longs.length}. This method is equivalent to {@code BitSet.valueOf(LongBuffer.wrap(longs))}.
public static BitSet valueOf(LongBuffer lb) { lb = lb.slice(); int n; for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--) ; long[] words = new long[n]; lb.get(words); return new BitSet(words); } Returns a new bit set containing all the bits in the given long buffer between its position and limit. More precisely, {@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)} for all {@code n < 64 * lb.remaining()}. The long buffer is not modified by this method, and no reference to the buffer is retained by the bit set.
public static BitSet valueOf(byte[] bytes) { return BitSet.valueOf(ByteBuffer.wrap(bytes)); } Returns a new bit set containing all the bits in the given byte array. More precisely, {@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)} for all {@code n < 8 * bytes.length}. This method is equivalent to {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.
public static BitSet valueOf(ByteBuffer bb) { bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN); int n; for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--) ; long[] words = new long[(n + 7) / 8]; bb.limit(n); int i = 0; while (bb.remaining() >= 8) words[i++] = bb.getLong(); for (int remaining = bb.remaining(), j = 0; j < remaining; j++) words[i] \|= (bb.get() & 0xffL) < < (8 * j); return new BitSet(words); } Returns a new bit set containing all the bits in the given byte buffer between its position and limit. More precisely, {@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)} for all {@code n < 8 * bb.remaining()}. The byte buffer is not modified by this method, and no reference to the buffer is retained by the bit set.
public void xor(BitSet set) { int wordsInCommon = Math.min(wordsInUse, set.wordsInUse); if (wordsInUse < set.wordsInUse) { ensureCapacity(set.wordsInUse); wordsInUse = set.wordsInUse; } // Perform logical XOR on words in common for (int i = 0; i < wordsInCommon; i++) words[i] ^= set.words[i]; // Copy any remaining words if (wordsInCommon < set.wordsInUse) System.arraycopy(set.words, wordsInCommon, words, wordsInCommon, set.wordsInUse - wordsInCommon); recalculateWordsInUse(); checkInvariants(); } Performs a logical XOR of this bit set with the bit set argument. This bit set is modified so that a bit in it has the value {@code true} if and only if one of the following statements holds: The bit initially has the value {@code true}, and the corresponding bit in the argument has the value {@code false}. The bit initially has the value {@code false}, and the corresponding bit in the argument has the value {@code true}.

Method from java.util.BitSet Detail:

 public  void and(BitSet set) {
        if (this == set)
            return;
        while (wordsInUse  > set.wordsInUse)
            words[--wordsInUse] = 0;
        // Perform logical AND on words in common
        for (int i = 0; i <  wordsInUse; i++)
            words[i] &= set.words[i];
        recalculateWordsInUse();
        checkInvariants();
}

AND

 public  void andNot(BitSet set) {
        // Perform logical (a & !b) on words in common
        for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i  >= 0; i--)
            words[i] &= ~set.words[i];
        recalculateWordsInUse();
        checkInvariants();
}

Clears all of the bits in this {@code BitSet} whose corresponding bit is set in the specified {@code BitSet}.

 public int cardinality() {
        int sum = 0;
        for (int i = 0; i <  wordsInUse; i++)
            sum += Long.bitCount(words[i]);
        return sum;
}

Returns the number of bits set to {@code true} in this {@code BitSet}.

 public  void clear() {
        while (wordsInUse  > 0)
            words[--wordsInUse] = 0;
}

Sets all of the bits in this BitSet to {@code false}.

 public  void clear(int bitIndex) {
        if (bitIndex <  0)
            throw new IndexOutOfBoundsException("bitIndex <  0: " + bitIndex);
        int wordIndex = wordIndex(bitIndex);
        if (wordIndex  >= wordsInUse)
            return;
        words[wordIndex] &= ~(1L < <  bitIndex);
        recalculateWordsInUse();
        checkInvariants();
}

Sets the bit specified by the index to {@code false}.

 public  void clear(int fromIndex,
    int toIndex) {
        checkRange(fromIndex, toIndex);
        if (fromIndex == toIndex)
            return;
        int startWordIndex = wordIndex(fromIndex);
        if (startWordIndex  >= wordsInUse)
            return;
        int endWordIndex = wordIndex(toIndex - 1);
        if (endWordIndex  >= wordsInUse) {
            toIndex = length();
            endWordIndex = wordsInUse - 1;
        }
        long firstWordMask = WORD_MASK < <  fromIndex;
        long lastWordMask  = WORD_MASK  > > > -toIndex;
        if (startWordIndex == endWordIndex) {
            // Case 1: One word
            words[startWordIndex] &= ~(firstWordMask & lastWordMask);
        } else {
            // Case 2: Multiple words
            // Handle first word
            words[startWordIndex] &= ~firstWordMask;
            // Handle intermediate words, if any
            for (int i = startWordIndex+1; i <  endWordIndex; i++)
                words[i] = 0;
            // Handle last word
            words[endWordIndex] &= ~lastWordMask;
        }
        recalculateWordsInUse();
        checkInvariants();
}

Sets the bits from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (exclusive) to {@code false}.

 public Object clone() {
        if (! sizeIsSticky)
            trimToSize();
        try {
            BitSet result = (BitSet) super.clone();
            result.words = words.clone();
            result.checkInvariants();
            return result;
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
}

Cloning this {@code BitSet} produces a new {@code BitSet} that is equal to it. The clone of the bit set is another bit set that has exactly the same bits set to {@code true} as this bit set.

 public boolean equals(Object obj) {
        if (!(obj instanceof BitSet))
            return false;
        if (this == obj)
            return true;
        BitSet set = (BitSet) obj;
        checkInvariants();
        set.checkInvariants();
        if (wordsInUse != set.wordsInUse)
            return false;
        // Check words in use by both BitSets
        for (int i = 0; i <  wordsInUse; i++)
            if (words[i] != set.words[i])
                return false;
        return true;
}

((BitSet)obj).get(k) == this.get(k)

 public  void flip(int bitIndex) {
        if (bitIndex <  0)
            throw new IndexOutOfBoundsException("bitIndex <  0: " + bitIndex);
        int wordIndex = wordIndex(bitIndex);
        expandTo(wordIndex);
        words[wordIndex] ^= (1L < <  bitIndex);
        recalculateWordsInUse();
        checkInvariants();
}

Sets the bit at the specified index to the complement of its current value.

 public  void flip(int fromIndex,
    int toIndex) {
        checkRange(fromIndex, toIndex);
        if (fromIndex == toIndex)
            return;
        int startWordIndex = wordIndex(fromIndex);
        int endWordIndex   = wordIndex(toIndex - 1);
        expandTo(endWordIndex);
        long firstWordMask = WORD_MASK < <  fromIndex;
        long lastWordMask  = WORD_MASK  > > > -toIndex;
        if (startWordIndex == endWordIndex) {
            // Case 1: One word
            words[startWordIndex] ^= (firstWordMask & lastWordMask);
        } else {
            // Case 2: Multiple words
            // Handle first word
            words[startWordIndex] ^= firstWordMask;
            // Handle intermediate words, if any
            for (int i = startWordIndex+1; i <  endWordIndex; i++)
                words[i] ^= WORD_MASK;
            // Handle last word
            words[endWordIndex] ^= lastWordMask;
        }
        recalculateWordsInUse();
        checkInvariants();
}

Sets each bit from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (exclusive) to the complement of its current value.

 public boolean get(int bitIndex) {
        if (bitIndex <  0)
            throw new IndexOutOfBoundsException("bitIndex <  0: " + bitIndex);
        checkInvariants();
        int wordIndex = wordIndex(bitIndex);
        return (wordIndex <  wordsInUse)
            && ((words[wordIndex] & (1L < <  bitIndex)) != 0);
}

Returns the value of the bit with the specified index. The value is {@code true} if the bit with the index {@code bitIndex} is currently set in this {@code BitSet}; otherwise, the result is {@code false}.

 public BitSet get(int fromIndex,
    int toIndex) {
        checkRange(fromIndex, toIndex);
        checkInvariants();
        int len = length();
        // If no set bits in range return empty bitset
        if (len < = fromIndex || fromIndex == toIndex)
            return new BitSet(0);
        // An optimization
        if (toIndex  > len)
            toIndex = len;
        BitSet result = new BitSet(toIndex - fromIndex);
        int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
        int sourceIndex = wordIndex(fromIndex);
        boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);
        // Process all words but the last word
        for (int i = 0; i <  targetWords - 1; i++, sourceIndex++)
            result.words[i] = wordAligned ? words[sourceIndex] :
                (words[sourceIndex]  > > > fromIndex) |
                (words[sourceIndex+1] < <  -fromIndex);
        // Process the last word
        long lastWordMask = WORD_MASK  > > > -toIndex;
        result.words[targetWords - 1] =
            ((toIndex-1) & BIT_INDEX_MASK) <  (fromIndex & BIT_INDEX_MASK)
            ? /* straddles source words */
            ((words[sourceIndex]  > > > fromIndex) |
             (words[sourceIndex+1] & lastWordMask) < <  -fromIndex)
            :
            ((words[sourceIndex] & lastWordMask)  > > > fromIndex);
        // Set wordsInUse correctly
        result.wordsInUse = targetWords;
        result.recalculateWordsInUse();
        result.checkInvariants();
        return result;
}

Returns a new {@code BitSet} composed of bits from this {@code BitSet} from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).

 public int hashCode() {
        long h = 1234;
        for (int i = wordsInUse; --i  >= 0; )
            h ^= words[i] * (i + 1);
        return (int)((h  > > 32) ^ h);
}

The hash code is defined to be the result of the following calculation:

 {@code
public int hashCode() {
long h = 1234;
long[] words = toLongArray();
for (int i = words.length; --i >= 0; )
h ^= words[i] * (i + 1);
return (int)((h >> 32) ^ h);
}}

 public boolean intersects(BitSet set) {
        for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i  >= 0; i--)
            if ((words[i] & set.words[i]) != 0)
                return true;
        return false;
}

Returns true if the specified {@code BitSet} has any bits set to {@code true} that are also set to {@code true} in this {@code BitSet}.

 public boolean isEmpty() {
        return wordsInUse == 0;
}

Returns true if this {@code BitSet} contains no bits that are set to {@code true}.

 public int length() {
        if (wordsInUse == 0)
            return 0;
        return BITS_PER_WORD * (wordsInUse - 1) +
            (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
}

Returns the "logical size" of this {@code BitSet}: the index of the highest set bit in the {@code BitSet} plus one. Returns zero if the {@code BitSet} contains no set bits.

 public int nextClearBit(int fromIndex) {
        // Neither spec nor implementation handle bitsets of maximal length.
        // See 4816253.
        if (fromIndex <  0)
            throw new IndexOutOfBoundsException("fromIndex <  0: " + fromIndex);
        checkInvariants();
        int u = wordIndex(fromIndex);
        if (u  >= wordsInUse)
            return fromIndex;
        long word = ~words[u] & (WORD_MASK < <  fromIndex);
        while (true) {
            if (word != 0)
                return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
            if (++u == wordsInUse)
                return wordsInUse * BITS_PER_WORD;
            word = ~words[u];
        }
}

Returns the index of the first bit that is set to {@code false} that occurs on or after the specified starting index.

 public int nextSetBit(int fromIndex) {
        if (fromIndex <  0)
            throw new IndexOutOfBoundsException("fromIndex <  0: " + fromIndex);
        checkInvariants();
        int u = wordIndex(fromIndex);
        if (u  >= wordsInUse)
            return -1;
        long word = words[u] & (WORD_MASK < <  fromIndex);
        while (true) {
            if (word != 0)
                return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
            if (++u == wordsInUse)
                return -1;
            word = words[u];
        }
}

To iterate over the {@code true} bits in a {@code BitSet}, use the following loop:

 {@code
for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
// operate on index i here
}}

 public  void or(BitSet set) {
        if (this == set)
            return;
        int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
        if (wordsInUse <  set.wordsInUse) {
            ensureCapacity(set.wordsInUse);
            wordsInUse = set.wordsInUse;
        }
        // Perform logical OR on words in common
        for (int i = 0; i <  wordsInCommon; i++)
            words[i] |= set.words[i];
        // Copy any remaining words
        if (wordsInCommon <  set.wordsInUse)
            System.arraycopy(set.words, wordsInCommon,
                             words, wordsInCommon,
                             wordsInUse - wordsInCommon);
        // recalculateWordsInUse() is unnecessary
        checkInvariants();
}

 public int previousClearBit(int fromIndex) {
        if (fromIndex <  0) {
            if (fromIndex == -1)
                return -1;
            throw new IndexOutOfBoundsException(
                "fromIndex <  -1: " + fromIndex);
        }
        checkInvariants();
        int u = wordIndex(fromIndex);
        if (u  >= wordsInUse)
            return fromIndex;
        long word = ~words[u] & (WORD_MASK  > > > -(fromIndex+1));
        while (true) {
            if (word != 0)
                return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);
            if (u-- == 0)
                return -1;
            word = ~words[u];
        }
}

Returns the index of the nearest bit that is set to {@code false} that occurs on or before the specified starting index. If no such bit exists, or if {@code -1} is given as the starting index, then {@code -1} is returned.

 public int previousSetBit(int fromIndex) {
        if (fromIndex <  0) {
            if (fromIndex == -1)
                return -1;
            throw new IndexOutOfBoundsException(
                "fromIndex <  -1: " + fromIndex);
        }
        checkInvariants();
        int u = wordIndex(fromIndex);
        if (u  >= wordsInUse)
            return length() - 1;
        long word = words[u] & (WORD_MASK  > > > -(fromIndex+1));
        while (true) {
            if (word != 0)
                return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
            if (u-- == 0)
                return -1;
            word = words[u];
        }
}

To iterate over the {@code true} bits in a {@code BitSet}, use the following loop:

 {@code
for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
// operate on index i here
}}

 public  void set(int bitIndex) {
        if (bitIndex <  0)
            throw new IndexOutOfBoundsException("bitIndex <  0: " + bitIndex);
        int wordIndex = wordIndex(bitIndex);
        expandTo(wordIndex);
        words[wordIndex] |= (1L < <  bitIndex); // Restores invariants
        checkInvariants();
}

Sets the bit at the specified index to {@code true}.

 public  void set(int bitIndex,
    boolean value) {
        if (value)
            set(bitIndex);
        else
            clear(bitIndex);
}

Sets the bit at the specified index to the specified value.

 public  void set(int fromIndex,
    int toIndex) {
        checkRange(fromIndex, toIndex);
        if (fromIndex == toIndex)
            return;
        // Increase capacity if necessary
        int startWordIndex = wordIndex(fromIndex);
        int endWordIndex   = wordIndex(toIndex - 1);
        expandTo(endWordIndex);
        long firstWordMask = WORD_MASK < <  fromIndex;
        long lastWordMask  = WORD_MASK  > > > -toIndex;
        if (startWordIndex == endWordIndex) {
            // Case 1: One word
            words[startWordIndex] |= (firstWordMask & lastWordMask);
        } else {
            // Case 2: Multiple words
            // Handle first word
            words[startWordIndex] |= firstWordMask;
            // Handle intermediate words, if any
            for (int i = startWordIndex+1; i <  endWordIndex; i++)
                words[i] = WORD_MASK;
            // Handle last word (restores invariants)
            words[endWordIndex] |= lastWordMask;
        }
        checkInvariants();
}

Sets the bits from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (exclusive) to {@code true}.

 public  void set(int fromIndex,
    int toIndex,
    boolean value) {
        if (value)
            set(fromIndex, toIndex);
        else
            clear(fromIndex, toIndex);
}

Sets the bits from the specified {@code fromIndex} (inclusive) to the specified {@code toIndex} (exclusive) to the specified value.

 public int size() {
        return words.length * BITS_PER_WORD;
}

Returns the number of bits of space actually in use by this {@code BitSet} to represent bit values. The maximum element in the set is the size - 1st element.

 public byte[] toByteArray() {
        int n = wordsInUse;
        if (n == 0)
            return new byte[0];
        int len = 8 * (n-1);
        for (long x = words[n - 1]; x != 0; x  > > >= 8)
            len++;
        byte[] bytes = new byte[len];
        ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);
        for (int i = 0; i <  n - 1; i++)
            bb.putLong(words[i]);
        for (long x = words[n - 1]; x != 0; x  > > >= 8)
            bb.put((byte) (x & 0xff));
        return bytes;
}

More precisely, if
{@code byte[] bytes = s.toByteArray();}
then {@code bytes.length == (s.length()+7)/8} and
{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
for all {@code n < 8 * bytes.length}.

 public long[] toLongArray() {
        return Arrays.copyOf(words, wordsInUse);
}

More precisely, if
{@code long[] longs = s.toLongArray();}
then {@code longs.length == (s.length()+63)/64} and
{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
for all {@code n < 64 * longs.length}.

 public String toString() {
        checkInvariants();
        int numBits = (wordsInUse  > 128) ?
            cardinality() : wordsInUse * BITS_PER_WORD;
        StringBuilder b = new StringBuilder(6*numBits + 2);
        b.append('{");
        int i = nextSetBit(0);
        if (i != -1) {
            b.append(i);
            for (i = nextSetBit(i+1); i  >= 0; i = nextSetBit(i+1)) {
                int endOfRun = nextClearBit(i);
                do { b.append(", ").append(i); }
                while (++i <  endOfRun);
            }
        }
        b.append('}");
        return b.toString();
}

Example:

BitSet drPepper = new BitSet();

drPepper.set(2);

drPepper.set(4);
drPepper.set(10);

 public static BitSet valueOf(long[] longs) {
        int n;
        for (n = longs.length; n  > 0 && longs[n - 1] == 0; n--)
            ;
        return new BitSet(Arrays.copyOf(longs, n));
}

More precisely,
{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
for all {@code n < 64 * longs.length}.

This method is equivalent to {@code BitSet.valueOf(LongBuffer.wrap(longs))}.

 public static BitSet valueOf(LongBuffer lb) {
        lb = lb.slice();
        int n;
        for (n = lb.remaining(); n  > 0 && lb.get(n - 1) == 0; n--)
            ;
        long[] words = new long[n];
        lb.get(words);
        return new BitSet(words);
}

More precisely,
{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}
for all {@code n < 64 * lb.remaining()}.

The long buffer is not modified by this method, and no reference to the buffer is retained by the bit set.

 public static BitSet valueOf(byte[] bytes) {
        return BitSet.valueOf(ByteBuffer.wrap(bytes));
}

More precisely,
{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
for all {@code n < 8 * bytes.length}.

This method is equivalent to {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.

 public static BitSet valueOf(ByteBuffer bb) {
        bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);
        int n;
        for (n = bb.remaining(); n  > 0 && bb.get(n - 1) == 0; n--)
            ;
        long[] words = new long[(n + 7) / 8];
        bb.limit(n);
        int i = 0;
        while (bb.remaining()  >= 8)
            words[i++] = bb.getLong();
        for (int remaining = bb.remaining(), j = 0; j <  remaining; j++)
            words[i] |= (bb.get() & 0xffL) < <  (8 * j);
        return new BitSet(words);
}

More precisely,
{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}
for all {@code n < 8 * bb.remaining()}.

The byte buffer is not modified by this method, and no reference to the buffer is retained by the bit set.

 public  void xor(BitSet set) {
        int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
        if (wordsInUse <  set.wordsInUse) {
            ensureCapacity(set.wordsInUse);
            wordsInUse = set.wordsInUse;
        }
        // Perform logical XOR on words in common
        for (int i = 0; i <  wordsInCommon; i++)
            words[i] ^= set.words[i];
        // Copy any remaining words
        if (wordsInCommon <  set.wordsInUse)
            System.arraycopy(set.words, wordsInCommon,
                             words, wordsInCommon,
                             set.wordsInUse - wordsInCommon);
        recalculateWordsInUse();
        checkInvariants();
}

XOR

The bit initially has the value {@code true}, and the corresponding bit in the argument has the value {@code false}.
The bit initially has the value {@code false}, and the corresponding bit in the argument has the value {@code true}.