Don't obfuscate names of fields in objects - otherwise fields provided by two modules may clash
2 * Copyright (c) 1995, 2007, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
31 * This class implements a vector of bits that grows as needed. Each
32 * component of the bit set has a {@code boolean} value. The
33 * bits of a {@code BitSet} are indexed by nonnegative integers.
34 * Individual indexed bits can be examined, set, or cleared. One
35 * {@code BitSet} may be used to modify the contents of another
36 * {@code BitSet} through logical AND, logical inclusive OR, and
37 * logical exclusive OR operations.
39 * <p>By default, all bits in the set initially have the value
42 * <p>Every bit set has a current size, which is the number of bits
43 * of space currently in use by the bit set. Note that the size is
44 * related to the implementation of a bit set, so it may change with
45 * implementation. The length of a bit set relates to logical length
46 * of a bit set and is defined independently of implementation.
48 * <p>Unless otherwise noted, passing a null parameter to any of the
49 * methods in a {@code BitSet} will result in a
50 * {@code NullPointerException}.
52 * <p>A {@code BitSet} is not safe for multithreaded use without
53 * external synchronization.
55 * @author Arthur van Hoff
56 * @author Michael McCloskey
57 * @author Martin Buchholz
60 public class BitSet implements Cloneable, java.io.Serializable {
62 * BitSets are packed into arrays of "words." Currently a word is
63 * a long, which consists of 64 bits, requiring 6 address bits.
64 * The choice of word size is determined purely by performance concerns.
66 private final static int ADDRESS_BITS_PER_WORD = 6;
67 private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
68 private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
70 /* Used to shift left or right for a partial word mask */
71 private static final long WORD_MASK = 0xffffffffffffffffL;
74 * @serialField bits long[]
76 * The bits in this BitSet. The ith bit is stored in bits[i/64] at
77 * bit position i % 64 (where bit position 0 refers to the least
78 * significant bit and 63 refers to the most significant bit).
80 private static final ObjectStreamField[] serialPersistentFields = {
81 new ObjectStreamField("bits", long[].class),
85 * The internal field corresponding to the serialField "bits".
90 * The number of words in the logical size of this BitSet.
92 private transient int wordsInUse = 0;
95 * Whether the size of "words" is user-specified. If so, we assume
96 * the user knows what he's doing and try harder to preserve it.
98 private transient boolean sizeIsSticky = false;
100 /* use serialVersionUID from JDK 1.0.2 for interoperability */
101 private static final long serialVersionUID = 7997698588986878753L;
104 * Given a bit index, return word index containing it.
106 private static int wordIndex(int bitIndex) {
107 return bitIndex >> ADDRESS_BITS_PER_WORD;
111 * Every public method must preserve these invariants.
113 private void checkInvariants() {
114 assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
115 assert(wordsInUse >= 0 && wordsInUse <= words.length);
116 assert(wordsInUse == words.length || words[wordsInUse] == 0);
120 * Sets the field wordsInUse to the logical size in words of the bit set.
121 * WARNING:This method assumes that the number of words actually in use is
122 * less than or equal to the current value of wordsInUse!
124 private void recalculateWordsInUse() {
125 // Traverse the bitset until a used word is found
127 for (i = wordsInUse-1; i >= 0; i--)
131 wordsInUse = i+1; // The new logical size
135 * Creates a new bit set. All bits are initially {@code false}.
138 initWords(BITS_PER_WORD);
139 sizeIsSticky = false;
143 * Creates a bit set whose initial size is large enough to explicitly
144 * represent bits with indices in the range {@code 0} through
145 * {@code nbits-1}. All bits are initially {@code false}.
147 * @param nbits the initial size of the bit set
148 * @throws NegativeArraySizeException if the specified initial size
151 public BitSet(int nbits) {
152 // nbits can't be negative; size 0 is OK
154 throw new NegativeArraySizeException("nbits < 0: " + nbits);
160 private void initWords(int nbits) {
161 words = new long[wordIndex(nbits-1) + 1];
165 * Creates a bit set using words as the internal representation.
166 * The last word (if there is one) must be non-zero.
168 private BitSet(long[] words) {
170 this.wordsInUse = words.length;
175 * Returns a new bit set containing all the bits in the given long array.
178 * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
179 * <br>for all {@code n < 64 * longs.length}.
181 * <p>This method is equivalent to
182 * {@code BitSet.valueOf(LongBuffer.wrap(longs))}.
184 * @param longs a long array containing a little-endian representation
185 * of a sequence of bits to be used as the initial bits of the
189 public static BitSet valueOf(long[] longs) {
191 for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)
193 return new BitSet(Arrays.copyOf(longs, n));
197 * Returns a new bit set containing all the bits in the given long
198 * buffer between its position and limit.
201 * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}
202 * <br>for all {@code n < 64 * lb.remaining()}.
204 * <p>The long buffer is not modified by this method, and no
205 * reference to the buffer is retained by the bit set.
207 * @param lb a long buffer containing a little-endian representation
208 * of a sequence of bits between its position and limit, to be
209 * used as the initial bits of the new bit set
212 // public static BitSet valueOf(LongBuffer lb) {
215 // for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)
217 // long[] words = new long[n];
219 // return new BitSet(words);
223 * Returns a new bit set containing all the bits in the given byte array.
226 * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
227 * <br>for all {@code n < 8 * bytes.length}.
229 * <p>This method is equivalent to
230 * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.
232 * @param bytes a byte array containing a little-endian
233 * representation of a sequence of bits to be used as the
234 * initial bits of the new bit set
237 // public static BitSet valueOf(byte[] bytes) {
238 // return BitSet.valueOf(ByteBuffer.wrap(bytes));
242 * Returns a new bit set containing all the bits in the given byte
243 * buffer between its position and limit.
246 * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}
247 * <br>for all {@code n < 8 * bb.remaining()}.
249 * <p>The byte buffer is not modified by this method, and no
250 * reference to the buffer is retained by the bit set.
252 * @param bb a byte buffer containing a little-endian representation
253 * of a sequence of bits between its position and limit, to be
254 * used as the initial bits of the new bit set
257 // public static BitSet valueOf(ByteBuffer bb) {
258 // bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);
260 // for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)
262 // long[] words = new long[(n + 7) / 8];
265 // while (bb.remaining() >= 8)
266 // words[i++] = bb.getLong();
267 // for (int remaining = bb.remaining(), j = 0; j < remaining; j++)
268 // words[i] |= (bb.get() & 0xffL) << (8 * j);
269 // return new BitSet(words);
273 * Returns a new byte array containing all the bits in this bit set.
275 * <p>More precisely, if
276 * <br>{@code byte[] bytes = s.toByteArray();}
277 * <br>then {@code bytes.length == (s.length()+7)/8} and
278 * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
279 * <br>for all {@code n < 8 * bytes.length}.
281 * @return a byte array containing a little-endian representation
282 * of all the bits in this bit set
285 // public byte[] toByteArray() {
286 // int n = wordsInUse;
288 // return new byte[0];
289 // int len = 8 * (n-1);
290 // for (long x = words[n - 1]; x != 0; x >>>= 8)
292 // byte[] bytes = new byte[len];
293 // ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);
294 // for (int i = 0; i < n - 1; i++)
295 // bb.putLong(words[i]);
296 // for (long x = words[n - 1]; x != 0; x >>>= 8)
297 // bb.put((byte) (x & 0xff));
302 * Returns a new long array containing all the bits in this bit set.
304 * <p>More precisely, if
305 * <br>{@code long[] longs = s.toLongArray();}
306 * <br>then {@code longs.length == (s.length()+63)/64} and
307 * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
308 * <br>for all {@code n < 64 * longs.length}.
310 * @return a long array containing a little-endian representation
311 * of all the bits in this bit set
314 public long[] toLongArray() {
315 return Arrays.copyOf(words, wordsInUse);
319 * Ensures that the BitSet can hold enough words.
320 * @param wordsRequired the minimum acceptable number of words.
322 private void ensureCapacity(int wordsRequired) {
323 if (words.length < wordsRequired) {
324 // Allocate larger of doubled size or required size
325 int request = Math.max(2 * words.length, wordsRequired);
326 words = Arrays.copyOf(words, request);
327 sizeIsSticky = false;
332 * Ensures that the BitSet can accommodate a given wordIndex,
333 * temporarily violating the invariants. The caller must
334 * restore the invariants before returning to the user,
335 * possibly using recalculateWordsInUse().
336 * @param wordIndex the index to be accommodated.
338 private void expandTo(int wordIndex) {
339 int wordsRequired = wordIndex+1;
340 if (wordsInUse < wordsRequired) {
341 ensureCapacity(wordsRequired);
342 wordsInUse = wordsRequired;
347 * Checks that fromIndex ... toIndex is a valid range of bit indices.
349 private static void checkRange(int fromIndex, int toIndex) {
351 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
353 throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
354 if (fromIndex > toIndex)
355 throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
356 " > toIndex: " + toIndex);
360 * Sets the bit at the specified index to the complement of its
363 * @param bitIndex the index of the bit to flip
364 * @throws IndexOutOfBoundsException if the specified index is negative
367 public void flip(int bitIndex) {
369 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
371 int wordIndex = wordIndex(bitIndex);
374 words[wordIndex] ^= (1L << bitIndex);
376 recalculateWordsInUse();
381 * Sets each bit from the specified {@code fromIndex} (inclusive) to the
382 * specified {@code toIndex} (exclusive) to the complement of its current
385 * @param fromIndex index of the first bit to flip
386 * @param toIndex index after the last bit to flip
387 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
388 * or {@code toIndex} is negative, or {@code fromIndex} is
389 * larger than {@code toIndex}
392 public void flip(int fromIndex, int toIndex) {
393 checkRange(fromIndex, toIndex);
395 if (fromIndex == toIndex)
398 int startWordIndex = wordIndex(fromIndex);
399 int endWordIndex = wordIndex(toIndex - 1);
400 expandTo(endWordIndex);
402 long firstWordMask = WORD_MASK << fromIndex;
403 long lastWordMask = WORD_MASK >>> -toIndex;
404 if (startWordIndex == endWordIndex) {
406 words[startWordIndex] ^= (firstWordMask & lastWordMask);
408 // Case 2: Multiple words
410 words[startWordIndex] ^= firstWordMask;
412 // Handle intermediate words, if any
413 for (int i = startWordIndex+1; i < endWordIndex; i++)
414 words[i] ^= WORD_MASK;
417 words[endWordIndex] ^= lastWordMask;
420 recalculateWordsInUse();
425 * Sets the bit at the specified index to {@code true}.
427 * @param bitIndex a bit index
428 * @throws IndexOutOfBoundsException if the specified index is negative
431 public void set(int bitIndex) {
433 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
435 int wordIndex = wordIndex(bitIndex);
438 words[wordIndex] |= (1L << bitIndex); // Restores invariants
444 * Sets the bit at the specified index to the specified value.
446 * @param bitIndex a bit index
447 * @param value a boolean value to set
448 * @throws IndexOutOfBoundsException if the specified index is negative
451 public void set(int bitIndex, boolean value) {
459 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
460 * specified {@code toIndex} (exclusive) to {@code true}.
462 * @param fromIndex index of the first bit to be set
463 * @param toIndex index after the last bit to be set
464 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
465 * or {@code toIndex} is negative, or {@code fromIndex} is
466 * larger than {@code toIndex}
469 public void set(int fromIndex, int toIndex) {
470 checkRange(fromIndex, toIndex);
472 if (fromIndex == toIndex)
475 // Increase capacity if necessary
476 int startWordIndex = wordIndex(fromIndex);
477 int endWordIndex = wordIndex(toIndex - 1);
478 expandTo(endWordIndex);
480 long firstWordMask = WORD_MASK << fromIndex;
481 long lastWordMask = WORD_MASK >>> -toIndex;
482 if (startWordIndex == endWordIndex) {
484 words[startWordIndex] |= (firstWordMask & lastWordMask);
486 // Case 2: Multiple words
488 words[startWordIndex] |= firstWordMask;
490 // Handle intermediate words, if any
491 for (int i = startWordIndex+1; i < endWordIndex; i++)
492 words[i] = WORD_MASK;
494 // Handle last word (restores invariants)
495 words[endWordIndex] |= lastWordMask;
502 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
503 * specified {@code toIndex} (exclusive) to the specified value.
505 * @param fromIndex index of the first bit to be set
506 * @param toIndex index after the last bit to be set
507 * @param value value to set the selected bits to
508 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
509 * or {@code toIndex} is negative, or {@code fromIndex} is
510 * larger than {@code toIndex}
513 public void set(int fromIndex, int toIndex, boolean value) {
515 set(fromIndex, toIndex);
517 clear(fromIndex, toIndex);
521 * Sets the bit specified by the index to {@code false}.
523 * @param bitIndex the index of the bit to be cleared
524 * @throws IndexOutOfBoundsException if the specified index is negative
527 public void clear(int bitIndex) {
529 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
531 int wordIndex = wordIndex(bitIndex);
532 if (wordIndex >= wordsInUse)
535 words[wordIndex] &= ~(1L << bitIndex);
537 recalculateWordsInUse();
542 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
543 * specified {@code toIndex} (exclusive) to {@code false}.
545 * @param fromIndex index of the first bit to be cleared
546 * @param toIndex index after the last bit to be cleared
547 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
548 * or {@code toIndex} is negative, or {@code fromIndex} is
549 * larger than {@code toIndex}
552 public void clear(int fromIndex, int toIndex) {
553 checkRange(fromIndex, toIndex);
555 if (fromIndex == toIndex)
558 int startWordIndex = wordIndex(fromIndex);
559 if (startWordIndex >= wordsInUse)
562 int endWordIndex = wordIndex(toIndex - 1);
563 if (endWordIndex >= wordsInUse) {
565 endWordIndex = wordsInUse - 1;
568 long firstWordMask = WORD_MASK << fromIndex;
569 long lastWordMask = WORD_MASK >>> -toIndex;
570 if (startWordIndex == endWordIndex) {
572 words[startWordIndex] &= ~(firstWordMask & lastWordMask);
574 // Case 2: Multiple words
576 words[startWordIndex] &= ~firstWordMask;
578 // Handle intermediate words, if any
579 for (int i = startWordIndex+1; i < endWordIndex; i++)
583 words[endWordIndex] &= ~lastWordMask;
586 recalculateWordsInUse();
591 * Sets all of the bits in this BitSet to {@code false}.
595 public void clear() {
596 while (wordsInUse > 0)
597 words[--wordsInUse] = 0;
601 * Returns the value of the bit with the specified index. The value
602 * is {@code true} if the bit with the index {@code bitIndex}
603 * is currently set in this {@code BitSet}; otherwise, the result
606 * @param bitIndex the bit index
607 * @return the value of the bit with the specified index
608 * @throws IndexOutOfBoundsException if the specified index is negative
610 public boolean get(int bitIndex) {
612 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
616 int wordIndex = wordIndex(bitIndex);
617 return (wordIndex < wordsInUse)
618 && ((words[wordIndex] & (1L << bitIndex)) != 0);
622 * Returns a new {@code BitSet} composed of bits from this {@code BitSet}
623 * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).
625 * @param fromIndex index of the first bit to include
626 * @param toIndex index after the last bit to include
627 * @return a new {@code BitSet} from a range of this {@code BitSet}
628 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
629 * or {@code toIndex} is negative, or {@code fromIndex} is
630 * larger than {@code toIndex}
633 public BitSet get(int fromIndex, int toIndex) {
634 checkRange(fromIndex, toIndex);
640 // If no set bits in range return empty bitset
641 if (len <= fromIndex || fromIndex == toIndex)
642 return new BitSet(0);
648 BitSet result = new BitSet(toIndex - fromIndex);
649 int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
650 int sourceIndex = wordIndex(fromIndex);
651 boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);
653 // Process all words but the last word
654 for (int i = 0; i < targetWords - 1; i++, sourceIndex++)
655 result.words[i] = wordAligned ? words[sourceIndex] :
656 (words[sourceIndex] >>> fromIndex) |
657 (words[sourceIndex+1] << -fromIndex);
659 // Process the last word
660 long lastWordMask = WORD_MASK >>> -toIndex;
661 result.words[targetWords - 1] =
662 ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)
663 ? /* straddles source words */
664 ((words[sourceIndex] >>> fromIndex) |
665 (words[sourceIndex+1] & lastWordMask) << -fromIndex)
667 ((words[sourceIndex] & lastWordMask) >>> fromIndex);
669 // Set wordsInUse correctly
670 result.wordsInUse = targetWords;
671 result.recalculateWordsInUse();
672 result.checkInvariants();
678 * Returns the index of the first bit that is set to {@code true}
679 * that occurs on or after the specified starting index. If no such
680 * bit exists then {@code -1} is returned.
682 * <p>To iterate over the {@code true} bits in a {@code BitSet},
683 * use the following loop:
686 * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
687 * // operate on index i here
690 * @param fromIndex the index to start checking from (inclusive)
691 * @return the index of the next set bit, or {@code -1} if there
693 * @throws IndexOutOfBoundsException if the specified index is negative
696 public int nextSetBit(int fromIndex) {
698 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
702 int u = wordIndex(fromIndex);
706 long word = words[u] & (WORD_MASK << fromIndex);
710 return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
711 if (++u == wordsInUse)
718 * Returns the index of the first bit that is set to {@code false}
719 * that occurs on or after the specified starting index.
721 * @param fromIndex the index to start checking from (inclusive)
722 * @return the index of the next clear bit
723 * @throws IndexOutOfBoundsException if the specified index is negative
726 public int nextClearBit(int fromIndex) {
727 // Neither spec nor implementation handle bitsets of maximal length.
730 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
734 int u = wordIndex(fromIndex);
738 long word = ~words[u] & (WORD_MASK << fromIndex);
742 return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
743 if (++u == wordsInUse)
744 return wordsInUse * BITS_PER_WORD;
750 * Returns the index of the nearest bit that is set to {@code true}
751 * that occurs on or before the specified starting index.
752 * If no such bit exists, or if {@code -1} is given as the
753 * starting index, then {@code -1} is returned.
755 * <p>To iterate over the {@code true} bits in a {@code BitSet},
756 * use the following loop:
759 * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
760 * // operate on index i here
763 * @param fromIndex the index to start checking from (inclusive)
764 * @return the index of the previous set bit, or {@code -1} if there
766 * @throws IndexOutOfBoundsException if the specified index is less
770 public int previousSetBit(int fromIndex) {
774 throw new IndexOutOfBoundsException(
775 "fromIndex < -1: " + fromIndex);
780 int u = wordIndex(fromIndex);
784 long word = words[u] & (WORD_MASK >>> -(fromIndex+1));
788 return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
796 * Returns the index of the nearest bit that is set to {@code false}
797 * that occurs on or before the specified starting index.
798 * If no such bit exists, or if {@code -1} is given as the
799 * starting index, then {@code -1} is returned.
801 * @param fromIndex the index to start checking from (inclusive)
802 * @return the index of the previous clear bit, or {@code -1} if there
804 * @throws IndexOutOfBoundsException if the specified index is less
808 public int previousClearBit(int fromIndex) {
812 throw new IndexOutOfBoundsException(
813 "fromIndex < -1: " + fromIndex);
818 int u = wordIndex(fromIndex);
822 long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));
826 return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);
834 * Returns the "logical size" of this {@code BitSet}: the index of
835 * the highest set bit in the {@code BitSet} plus one. Returns zero
836 * if the {@code BitSet} contains no set bits.
838 * @return the logical size of this {@code BitSet}
841 public int length() {
845 return BITS_PER_WORD * (wordsInUse - 1) +
846 (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
850 * Returns true if this {@code BitSet} contains no bits that are set
853 * @return boolean indicating whether this {@code BitSet} is empty
856 public boolean isEmpty() {
857 return wordsInUse == 0;
861 * Returns true if the specified {@code BitSet} has any bits set to
862 * {@code true} that are also set to {@code true} in this {@code BitSet}.
864 * @param set {@code BitSet} to intersect with
865 * @return boolean indicating whether this {@code BitSet} intersects
866 * the specified {@code BitSet}
869 public boolean intersects(BitSet set) {
870 for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
871 if ((words[i] & set.words[i]) != 0)
877 * Returns the number of bits set to {@code true} in this {@code BitSet}.
879 * @return the number of bits set to {@code true} in this {@code BitSet}
882 public int cardinality() {
884 for (int i = 0; i < wordsInUse; i++)
885 sum += Long.bitCount(words[i]);
890 * Performs a logical <b>AND</b> of this target bit set with the
891 * argument bit set. This bit set is modified so that each bit in it
892 * has the value {@code true} if and only if it both initially
893 * had the value {@code true} and the corresponding bit in the
894 * bit set argument also had the value {@code true}.
896 * @param set a bit set
898 public void and(BitSet set) {
902 while (wordsInUse > set.wordsInUse)
903 words[--wordsInUse] = 0;
905 // Perform logical AND on words in common
906 for (int i = 0; i < wordsInUse; i++)
907 words[i] &= set.words[i];
909 recalculateWordsInUse();
914 * Performs a logical <b>OR</b> of this bit set with the bit set
915 * argument. This bit set is modified so that a bit in it has the
916 * value {@code true} if and only if it either already had the
917 * value {@code true} or the corresponding bit in the bit set
918 * argument has the value {@code true}.
920 * @param set a bit set
922 public void or(BitSet set) {
926 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
928 if (wordsInUse < set.wordsInUse) {
929 ensureCapacity(set.wordsInUse);
930 wordsInUse = set.wordsInUse;
933 // Perform logical OR on words in common
934 for (int i = 0; i < wordsInCommon; i++)
935 words[i] |= set.words[i];
937 // Copy any remaining words
938 if (wordsInCommon < set.wordsInUse)
939 System.arraycopy(set.words, wordsInCommon,
940 words, wordsInCommon,
941 wordsInUse - wordsInCommon);
943 // recalculateWordsInUse() is unnecessary
948 * Performs a logical <b>XOR</b> of this bit set with the bit set
949 * argument. This bit set is modified so that a bit in it has the
950 * value {@code true} if and only if one of the following
953 * <li>The bit initially has the value {@code true}, and the
954 * corresponding bit in the argument has the value {@code false}.
955 * <li>The bit initially has the value {@code false}, and the
956 * corresponding bit in the argument has the value {@code true}.
959 * @param set a bit set
961 public void xor(BitSet set) {
962 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
964 if (wordsInUse < set.wordsInUse) {
965 ensureCapacity(set.wordsInUse);
966 wordsInUse = set.wordsInUse;
969 // Perform logical XOR on words in common
970 for (int i = 0; i < wordsInCommon; i++)
971 words[i] ^= set.words[i];
973 // Copy any remaining words
974 if (wordsInCommon < set.wordsInUse)
975 System.arraycopy(set.words, wordsInCommon,
976 words, wordsInCommon,
977 set.wordsInUse - wordsInCommon);
979 recalculateWordsInUse();
984 * Clears all of the bits in this {@code BitSet} whose corresponding
985 * bit is set in the specified {@code BitSet}.
987 * @param set the {@code BitSet} with which to mask this
991 public void andNot(BitSet set) {
992 // Perform logical (a & !b) on words in common
993 for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
994 words[i] &= ~set.words[i];
996 recalculateWordsInUse();
1001 * Returns the hash code value for this bit set. The hash code depends
1002 * only on which bits are set within this {@code BitSet}.
1004 * <p>The hash code is defined to be the result of the following
1007 * public int hashCode() {
1009 * long[] words = toLongArray();
1010 * for (int i = words.length; --i >= 0; )
1011 * h ^= words[i] * (i + 1);
1012 * return (int)((h >> 32) ^ h);
1014 * Note that the hash code changes if the set of bits is altered.
1016 * @return the hash code value for this bit set
1018 public int hashCode() {
1020 for (int i = wordsInUse; --i >= 0; )
1021 h ^= words[i] * (i + 1);
1023 return (int)((h >> 32) ^ h);
1027 * Returns the number of bits of space actually in use by this
1028 * {@code BitSet} to represent bit values.
1029 * The maximum element in the set is the size - 1st element.
1031 * @return the number of bits currently in this bit set
1034 return words.length * BITS_PER_WORD;
1038 * Compares this object against the specified object.
1039 * The result is {@code true} if and only if the argument is
1040 * not {@code null} and is a {@code Bitset} object that has
1041 * exactly the same set of bits set to {@code true} as this bit
1042 * set. That is, for every nonnegative {@code int} index {@code k},
1043 * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
1044 * must be true. The current sizes of the two bit sets are not compared.
1046 * @param obj the object to compare with
1047 * @return {@code true} if the objects are the same;
1048 * {@code false} otherwise
1051 public boolean equals(Object obj) {
1052 if (!(obj instanceof BitSet))
1057 BitSet set = (BitSet) obj;
1060 set.checkInvariants();
1062 if (wordsInUse != set.wordsInUse)
1065 // Check words in use by both BitSets
1066 for (int i = 0; i < wordsInUse; i++)
1067 if (words[i] != set.words[i])
1074 * Cloning this {@code BitSet} produces a new {@code BitSet}
1075 * that is equal to it.
1076 * The clone of the bit set is another bit set that has exactly the
1077 * same bits set to {@code true} as this bit set.
1079 * @return a clone of this bit set
1082 public Object clone() {
1087 BitSet result = (BitSet) super.clone();
1088 result.words = words.clone();
1089 result.checkInvariants();
1091 } catch (CloneNotSupportedException e) {
1092 throw new InternalError();
1097 * Attempts to reduce internal storage used for the bits in this bit set.
1098 * Calling this method may, but is not required to, affect the value
1099 * returned by a subsequent call to the {@link #size()} method.
1101 private void trimToSize() {
1102 if (wordsInUse != words.length) {
1103 words = Arrays.copyOf(words, wordsInUse);
1109 * Save the state of the {@code BitSet} instance to a stream (i.e.,
1112 private void writeObject(ObjectOutputStream s)
1113 throws IOException {
1120 ObjectOutputStream.PutField fields = s.putFields();
1121 fields.put("bits", words);
1126 * Reconstitute the {@code BitSet} instance from a stream (i.e.,
1129 private void readObject(ObjectInputStream s)
1130 throws IOException, ClassNotFoundException {
1132 ObjectInputStream.GetField fields = s.readFields();
1133 words = (long[]) fields.get("bits", null);
1135 // Assume maximum length then find real length
1136 // because recalculateWordsInUse assumes maintenance
1137 // or reduction in logical size
1138 wordsInUse = words.length;
1139 recalculateWordsInUse();
1140 sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic
1145 * Returns a string representation of this bit set. For every index
1146 * for which this {@code BitSet} contains a bit in the set
1147 * state, the decimal representation of that index is included in
1148 * the result. Such indices are listed in order from lowest to
1149 * highest, separated by ", " (a comma and a space) and
1150 * surrounded by braces, resulting in the usual mathematical
1151 * notation for a set of integers.
1155 * BitSet drPepper = new BitSet();</pre>
1156 * Now {@code drPepper.toString()} returns "{@code {}}".<p>
1158 * drPepper.set(2);</pre>
1159 * Now {@code drPepper.toString()} returns "{@code {2}}".<p>
1162 * drPepper.set(10);</pre>
1163 * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
1165 * @return a string representation of this bit set
1167 public String toString() {
1170 int numBits = (wordsInUse > 128) ?
1171 cardinality() : wordsInUse * BITS_PER_WORD;
1172 StringBuilder b = new StringBuilder(6*numBits + 2);
1175 int i = nextSetBit(0);
1178 for (i = nextSetBit(i+1); i >= 0; i = nextSetBit(i+1)) {
1179 int endOfRun = nextClearBit(i);
1180 do { b.append(", ").append(i); }
1181 while (++i < endOfRun);
1186 return b.toString();