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
29 import java.nio.ByteBuffer;
30 import java.nio.ByteOrder;
31 import java.nio.LongBuffer;
34 * This class implements a vector of bits that grows as needed. Each
35 * component of the bit set has a {@code boolean} value. The
36 * bits of a {@code BitSet} are indexed by nonnegative integers.
37 * Individual indexed bits can be examined, set, or cleared. One
38 * {@code BitSet} may be used to modify the contents of another
39 * {@code BitSet} through logical AND, logical inclusive OR, and
40 * logical exclusive OR operations.
42 * <p>By default, all bits in the set initially have the value
45 * <p>Every bit set has a current size, which is the number of bits
46 * of space currently in use by the bit set. Note that the size is
47 * related to the implementation of a bit set, so it may change with
48 * implementation. The length of a bit set relates to logical length
49 * of a bit set and is defined independently of implementation.
51 * <p>Unless otherwise noted, passing a null parameter to any of the
52 * methods in a {@code BitSet} will result in a
53 * {@code NullPointerException}.
55 * <p>A {@code BitSet} is not safe for multithreaded use without
56 * external synchronization.
58 * @author Arthur van Hoff
59 * @author Michael McCloskey
60 * @author Martin Buchholz
63 public class BitSet implements Cloneable, java.io.Serializable {
65 * BitSets are packed into arrays of "words." Currently a word is
66 * a long, which consists of 64 bits, requiring 6 address bits.
67 * The choice of word size is determined purely by performance concerns.
69 private final static int ADDRESS_BITS_PER_WORD = 6;
70 private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
71 private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
73 /* Used to shift left or right for a partial word mask */
74 private static final long WORD_MASK = 0xffffffffffffffffL;
77 * @serialField bits long[]
79 * The bits in this BitSet. The ith bit is stored in bits[i/64] at
80 * bit position i % 64 (where bit position 0 refers to the least
81 * significant bit and 63 refers to the most significant bit).
83 private static final ObjectStreamField[] serialPersistentFields = {
84 new ObjectStreamField("bits", long[].class),
88 * The internal field corresponding to the serialField "bits".
93 * The number of words in the logical size of this BitSet.
95 private transient int wordsInUse = 0;
98 * Whether the size of "words" is user-specified. If so, we assume
99 * the user knows what he's doing and try harder to preserve it.
101 private transient boolean sizeIsSticky = false;
103 /* use serialVersionUID from JDK 1.0.2 for interoperability */
104 private static final long serialVersionUID = 7997698588986878753L;
107 * Given a bit index, return word index containing it.
109 private static int wordIndex(int bitIndex) {
110 return bitIndex >> ADDRESS_BITS_PER_WORD;
114 * Every public method must preserve these invariants.
116 private void checkInvariants() {
117 assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
118 assert(wordsInUse >= 0 && wordsInUse <= words.length);
119 assert(wordsInUse == words.length || words[wordsInUse] == 0);
123 * Sets the field wordsInUse to the logical size in words of the bit set.
124 * WARNING:This method assumes that the number of words actually in use is
125 * less than or equal to the current value of wordsInUse!
127 private void recalculateWordsInUse() {
128 // Traverse the bitset until a used word is found
130 for (i = wordsInUse-1; i >= 0; i--)
134 wordsInUse = i+1; // The new logical size
138 * Creates a new bit set. All bits are initially {@code false}.
141 initWords(BITS_PER_WORD);
142 sizeIsSticky = false;
146 * Creates a bit set whose initial size is large enough to explicitly
147 * represent bits with indices in the range {@code 0} through
148 * {@code nbits-1}. All bits are initially {@code false}.
150 * @param nbits the initial size of the bit set
151 * @throws NegativeArraySizeException if the specified initial size
154 public BitSet(int nbits) {
155 // nbits can't be negative; size 0 is OK
157 throw new NegativeArraySizeException("nbits < 0: " + nbits);
163 private void initWords(int nbits) {
164 words = new long[wordIndex(nbits-1) + 1];
168 * Creates a bit set using words as the internal representation.
169 * The last word (if there is one) must be non-zero.
171 private BitSet(long[] words) {
173 this.wordsInUse = words.length;
178 * Returns a new bit set containing all the bits in the given long array.
181 * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
182 * <br>for all {@code n < 64 * longs.length}.
184 * <p>This method is equivalent to
185 * {@code BitSet.valueOf(LongBuffer.wrap(longs))}.
187 * @param longs a long array containing a little-endian representation
188 * of a sequence of bits to be used as the initial bits of the
192 public static BitSet valueOf(long[] longs) {
194 for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)
196 return new BitSet(Arrays.copyOf(longs, n));
200 * Returns a new bit set containing all the bits in the given long
201 * buffer between its position and limit.
204 * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}
205 * <br>for all {@code n < 64 * lb.remaining()}.
207 * <p>The long buffer is not modified by this method, and no
208 * reference to the buffer is retained by the bit set.
210 * @param lb a long buffer containing a little-endian representation
211 * of a sequence of bits between its position and limit, to be
212 * used as the initial bits of the new bit set
215 public static BitSet valueOf(LongBuffer lb) {
218 for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)
220 long[] words = new long[n];
222 return new BitSet(words);
226 * Returns a new bit set containing all the bits in the given byte array.
229 * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
230 * <br>for all {@code n < 8 * bytes.length}.
232 * <p>This method is equivalent to
233 * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.
235 * @param bytes a byte array containing a little-endian
236 * representation of a sequence of bits to be used as the
237 * initial bits of the new bit set
240 public static BitSet valueOf(byte[] bytes) {
241 return BitSet.valueOf(ByteBuffer.wrap(bytes));
245 * Returns a new bit set containing all the bits in the given byte
246 * buffer between its position and limit.
249 * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}
250 * <br>for all {@code n < 8 * bb.remaining()}.
252 * <p>The byte buffer is not modified by this method, and no
253 * reference to the buffer is retained by the bit set.
255 * @param bb a byte buffer containing a little-endian representation
256 * of a sequence of bits between its position and limit, to be
257 * used as the initial bits of the new bit set
260 public static BitSet valueOf(ByteBuffer bb) {
261 bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);
263 for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)
265 long[] words = new long[(n + 7) / 8];
268 while (bb.remaining() >= 8)
269 words[i++] = bb.getLong();
270 for (int remaining = bb.remaining(), j = 0; j < remaining; j++)
271 words[i] |= (bb.get() & 0xffL) << (8 * j);
272 return new BitSet(words);
276 * Returns a new byte array containing all the bits in this bit set.
278 * <p>More precisely, if
279 * <br>{@code byte[] bytes = s.toByteArray();}
280 * <br>then {@code bytes.length == (s.length()+7)/8} and
281 * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
282 * <br>for all {@code n < 8 * bytes.length}.
284 * @return a byte array containing a little-endian representation
285 * of all the bits in this bit set
288 public byte[] toByteArray() {
293 for (long x = words[n - 1]; x != 0; x >>>= 8)
295 byte[] bytes = new byte[len];
296 ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);
297 for (int i = 0; i < n - 1; i++)
298 bb.putLong(words[i]);
299 for (long x = words[n - 1]; x != 0; x >>>= 8)
300 bb.put((byte) (x & 0xff));
305 * Returns a new long array containing all the bits in this bit set.
307 * <p>More precisely, if
308 * <br>{@code long[] longs = s.toLongArray();}
309 * <br>then {@code longs.length == (s.length()+63)/64} and
310 * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
311 * <br>for all {@code n < 64 * longs.length}.
313 * @return a long array containing a little-endian representation
314 * of all the bits in this bit set
317 public long[] toLongArray() {
318 return Arrays.copyOf(words, wordsInUse);
322 * Ensures that the BitSet can hold enough words.
323 * @param wordsRequired the minimum acceptable number of words.
325 private void ensureCapacity(int wordsRequired) {
326 if (words.length < wordsRequired) {
327 // Allocate larger of doubled size or required size
328 int request = Math.max(2 * words.length, wordsRequired);
329 words = Arrays.copyOf(words, request);
330 sizeIsSticky = false;
335 * Ensures that the BitSet can accommodate a given wordIndex,
336 * temporarily violating the invariants. The caller must
337 * restore the invariants before returning to the user,
338 * possibly using recalculateWordsInUse().
339 * @param wordIndex the index to be accommodated.
341 private void expandTo(int wordIndex) {
342 int wordsRequired = wordIndex+1;
343 if (wordsInUse < wordsRequired) {
344 ensureCapacity(wordsRequired);
345 wordsInUse = wordsRequired;
350 * Checks that fromIndex ... toIndex is a valid range of bit indices.
352 private static void checkRange(int fromIndex, int toIndex) {
354 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
356 throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
357 if (fromIndex > toIndex)
358 throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
359 " > toIndex: " + toIndex);
363 * Sets the bit at the specified index to the complement of its
366 * @param bitIndex the index of the bit to flip
367 * @throws IndexOutOfBoundsException if the specified index is negative
370 public void flip(int bitIndex) {
372 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
374 int wordIndex = wordIndex(bitIndex);
377 words[wordIndex] ^= (1L << bitIndex);
379 recalculateWordsInUse();
384 * Sets each bit from the specified {@code fromIndex} (inclusive) to the
385 * specified {@code toIndex} (exclusive) to the complement of its current
388 * @param fromIndex index of the first bit to flip
389 * @param toIndex index after the last bit to flip
390 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
391 * or {@code toIndex} is negative, or {@code fromIndex} is
392 * larger than {@code toIndex}
395 public void flip(int fromIndex, int toIndex) {
396 checkRange(fromIndex, toIndex);
398 if (fromIndex == toIndex)
401 int startWordIndex = wordIndex(fromIndex);
402 int endWordIndex = wordIndex(toIndex - 1);
403 expandTo(endWordIndex);
405 long firstWordMask = WORD_MASK << fromIndex;
406 long lastWordMask = WORD_MASK >>> -toIndex;
407 if (startWordIndex == endWordIndex) {
409 words[startWordIndex] ^= (firstWordMask & lastWordMask);
411 // Case 2: Multiple words
413 words[startWordIndex] ^= firstWordMask;
415 // Handle intermediate words, if any
416 for (int i = startWordIndex+1; i < endWordIndex; i++)
417 words[i] ^= WORD_MASK;
420 words[endWordIndex] ^= lastWordMask;
423 recalculateWordsInUse();
428 * Sets the bit at the specified index to {@code true}.
430 * @param bitIndex a bit index
431 * @throws IndexOutOfBoundsException if the specified index is negative
434 public void set(int bitIndex) {
436 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
438 int wordIndex = wordIndex(bitIndex);
441 words[wordIndex] |= (1L << bitIndex); // Restores invariants
447 * Sets the bit at the specified index to the specified value.
449 * @param bitIndex a bit index
450 * @param value a boolean value to set
451 * @throws IndexOutOfBoundsException if the specified index is negative
454 public void set(int bitIndex, boolean value) {
462 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
463 * specified {@code toIndex} (exclusive) to {@code true}.
465 * @param fromIndex index of the first bit to be set
466 * @param toIndex index after the last bit to be set
467 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
468 * or {@code toIndex} is negative, or {@code fromIndex} is
469 * larger than {@code toIndex}
472 public void set(int fromIndex, int toIndex) {
473 checkRange(fromIndex, toIndex);
475 if (fromIndex == toIndex)
478 // Increase capacity if necessary
479 int startWordIndex = wordIndex(fromIndex);
480 int endWordIndex = wordIndex(toIndex - 1);
481 expandTo(endWordIndex);
483 long firstWordMask = WORD_MASK << fromIndex;
484 long lastWordMask = WORD_MASK >>> -toIndex;
485 if (startWordIndex == endWordIndex) {
487 words[startWordIndex] |= (firstWordMask & lastWordMask);
489 // Case 2: Multiple words
491 words[startWordIndex] |= firstWordMask;
493 // Handle intermediate words, if any
494 for (int i = startWordIndex+1; i < endWordIndex; i++)
495 words[i] = WORD_MASK;
497 // Handle last word (restores invariants)
498 words[endWordIndex] |= lastWordMask;
505 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
506 * specified {@code toIndex} (exclusive) to the specified value.
508 * @param fromIndex index of the first bit to be set
509 * @param toIndex index after the last bit to be set
510 * @param value value to set the selected bits to
511 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
512 * or {@code toIndex} is negative, or {@code fromIndex} is
513 * larger than {@code toIndex}
516 public void set(int fromIndex, int toIndex, boolean value) {
518 set(fromIndex, toIndex);
520 clear(fromIndex, toIndex);
524 * Sets the bit specified by the index to {@code false}.
526 * @param bitIndex the index of the bit to be cleared
527 * @throws IndexOutOfBoundsException if the specified index is negative
530 public void clear(int bitIndex) {
532 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
534 int wordIndex = wordIndex(bitIndex);
535 if (wordIndex >= wordsInUse)
538 words[wordIndex] &= ~(1L << bitIndex);
540 recalculateWordsInUse();
545 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
546 * specified {@code toIndex} (exclusive) to {@code false}.
548 * @param fromIndex index of the first bit to be cleared
549 * @param toIndex index after the last bit to be cleared
550 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
551 * or {@code toIndex} is negative, or {@code fromIndex} is
552 * larger than {@code toIndex}
555 public void clear(int fromIndex, int toIndex) {
556 checkRange(fromIndex, toIndex);
558 if (fromIndex == toIndex)
561 int startWordIndex = wordIndex(fromIndex);
562 if (startWordIndex >= wordsInUse)
565 int endWordIndex = wordIndex(toIndex - 1);
566 if (endWordIndex >= wordsInUse) {
568 endWordIndex = wordsInUse - 1;
571 long firstWordMask = WORD_MASK << fromIndex;
572 long lastWordMask = WORD_MASK >>> -toIndex;
573 if (startWordIndex == endWordIndex) {
575 words[startWordIndex] &= ~(firstWordMask & lastWordMask);
577 // Case 2: Multiple words
579 words[startWordIndex] &= ~firstWordMask;
581 // Handle intermediate words, if any
582 for (int i = startWordIndex+1; i < endWordIndex; i++)
586 words[endWordIndex] &= ~lastWordMask;
589 recalculateWordsInUse();
594 * Sets all of the bits in this BitSet to {@code false}.
598 public void clear() {
599 while (wordsInUse > 0)
600 words[--wordsInUse] = 0;
604 * Returns the value of the bit with the specified index. The value
605 * is {@code true} if the bit with the index {@code bitIndex}
606 * is currently set in this {@code BitSet}; otherwise, the result
609 * @param bitIndex the bit index
610 * @return the value of the bit with the specified index
611 * @throws IndexOutOfBoundsException if the specified index is negative
613 public boolean get(int bitIndex) {
615 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
619 int wordIndex = wordIndex(bitIndex);
620 return (wordIndex < wordsInUse)
621 && ((words[wordIndex] & (1L << bitIndex)) != 0);
625 * Returns a new {@code BitSet} composed of bits from this {@code BitSet}
626 * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).
628 * @param fromIndex index of the first bit to include
629 * @param toIndex index after the last bit to include
630 * @return a new {@code BitSet} from a range of this {@code BitSet}
631 * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
632 * or {@code toIndex} is negative, or {@code fromIndex} is
633 * larger than {@code toIndex}
636 public BitSet get(int fromIndex, int toIndex) {
637 checkRange(fromIndex, toIndex);
643 // If no set bits in range return empty bitset
644 if (len <= fromIndex || fromIndex == toIndex)
645 return new BitSet(0);
651 BitSet result = new BitSet(toIndex - fromIndex);
652 int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
653 int sourceIndex = wordIndex(fromIndex);
654 boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);
656 // Process all words but the last word
657 for (int i = 0; i < targetWords - 1; i++, sourceIndex++)
658 result.words[i] = wordAligned ? words[sourceIndex] :
659 (words[sourceIndex] >>> fromIndex) |
660 (words[sourceIndex+1] << -fromIndex);
662 // Process the last word
663 long lastWordMask = WORD_MASK >>> -toIndex;
664 result.words[targetWords - 1] =
665 ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)
666 ? /* straddles source words */
667 ((words[sourceIndex] >>> fromIndex) |
668 (words[sourceIndex+1] & lastWordMask) << -fromIndex)
670 ((words[sourceIndex] & lastWordMask) >>> fromIndex);
672 // Set wordsInUse correctly
673 result.wordsInUse = targetWords;
674 result.recalculateWordsInUse();
675 result.checkInvariants();
681 * Returns the index of the first bit that is set to {@code true}
682 * that occurs on or after the specified starting index. If no such
683 * bit exists then {@code -1} is returned.
685 * <p>To iterate over the {@code true} bits in a {@code BitSet},
686 * use the following loop:
689 * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
690 * // operate on index i here
693 * @param fromIndex the index to start checking from (inclusive)
694 * @return the index of the next set bit, or {@code -1} if there
696 * @throws IndexOutOfBoundsException if the specified index is negative
699 public int nextSetBit(int fromIndex) {
701 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
705 int u = wordIndex(fromIndex);
709 long word = words[u] & (WORD_MASK << fromIndex);
713 return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
714 if (++u == wordsInUse)
721 * Returns the index of the first bit that is set to {@code false}
722 * that occurs on or after the specified starting index.
724 * @param fromIndex the index to start checking from (inclusive)
725 * @return the index of the next clear bit
726 * @throws IndexOutOfBoundsException if the specified index is negative
729 public int nextClearBit(int fromIndex) {
730 // Neither spec nor implementation handle bitsets of maximal length.
733 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
737 int u = wordIndex(fromIndex);
741 long word = ~words[u] & (WORD_MASK << fromIndex);
745 return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
746 if (++u == wordsInUse)
747 return wordsInUse * BITS_PER_WORD;
753 * Returns the index of the nearest bit that is set to {@code true}
754 * that occurs on or before the specified starting index.
755 * If no such bit exists, or if {@code -1} is given as the
756 * starting index, then {@code -1} is returned.
758 * <p>To iterate over the {@code true} bits in a {@code BitSet},
759 * use the following loop:
762 * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
763 * // operate on index i here
766 * @param fromIndex the index to start checking from (inclusive)
767 * @return the index of the previous set bit, or {@code -1} if there
769 * @throws IndexOutOfBoundsException if the specified index is less
773 public int previousSetBit(int fromIndex) {
777 throw new IndexOutOfBoundsException(
778 "fromIndex < -1: " + fromIndex);
783 int u = wordIndex(fromIndex);
787 long word = words[u] & (WORD_MASK >>> -(fromIndex+1));
791 return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
799 * Returns the index of the nearest bit that is set to {@code false}
800 * that occurs on or before the specified starting index.
801 * If no such bit exists, or if {@code -1} is given as the
802 * starting index, then {@code -1} is returned.
804 * @param fromIndex the index to start checking from (inclusive)
805 * @return the index of the previous clear bit, or {@code -1} if there
807 * @throws IndexOutOfBoundsException if the specified index is less
811 public int previousClearBit(int fromIndex) {
815 throw new IndexOutOfBoundsException(
816 "fromIndex < -1: " + fromIndex);
821 int u = wordIndex(fromIndex);
825 long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));
829 return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);
837 * Returns the "logical size" of this {@code BitSet}: the index of
838 * the highest set bit in the {@code BitSet} plus one. Returns zero
839 * if the {@code BitSet} contains no set bits.
841 * @return the logical size of this {@code BitSet}
844 public int length() {
848 return BITS_PER_WORD * (wordsInUse - 1) +
849 (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
853 * Returns true if this {@code BitSet} contains no bits that are set
856 * @return boolean indicating whether this {@code BitSet} is empty
859 public boolean isEmpty() {
860 return wordsInUse == 0;
864 * Returns true if the specified {@code BitSet} has any bits set to
865 * {@code true} that are also set to {@code true} in this {@code BitSet}.
867 * @param set {@code BitSet} to intersect with
868 * @return boolean indicating whether this {@code BitSet} intersects
869 * the specified {@code BitSet}
872 public boolean intersects(BitSet set) {
873 for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
874 if ((words[i] & set.words[i]) != 0)
880 * Returns the number of bits set to {@code true} in this {@code BitSet}.
882 * @return the number of bits set to {@code true} in this {@code BitSet}
885 public int cardinality() {
887 for (int i = 0; i < wordsInUse; i++)
888 sum += Long.bitCount(words[i]);
893 * Performs a logical <b>AND</b> of this target bit set with the
894 * argument bit set. This bit set is modified so that each bit in it
895 * has the value {@code true} if and only if it both initially
896 * had the value {@code true} and the corresponding bit in the
897 * bit set argument also had the value {@code true}.
899 * @param set a bit set
901 public void and(BitSet set) {
905 while (wordsInUse > set.wordsInUse)
906 words[--wordsInUse] = 0;
908 // Perform logical AND on words in common
909 for (int i = 0; i < wordsInUse; i++)
910 words[i] &= set.words[i];
912 recalculateWordsInUse();
917 * Performs a logical <b>OR</b> of this bit set with the bit set
918 * argument. This bit set is modified so that a bit in it has the
919 * value {@code true} if and only if it either already had the
920 * value {@code true} or the corresponding bit in the bit set
921 * argument has the value {@code true}.
923 * @param set a bit set
925 public void or(BitSet set) {
929 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
931 if (wordsInUse < set.wordsInUse) {
932 ensureCapacity(set.wordsInUse);
933 wordsInUse = set.wordsInUse;
936 // Perform logical OR on words in common
937 for (int i = 0; i < wordsInCommon; i++)
938 words[i] |= set.words[i];
940 // Copy any remaining words
941 if (wordsInCommon < set.wordsInUse)
942 System.arraycopy(set.words, wordsInCommon,
943 words, wordsInCommon,
944 wordsInUse - wordsInCommon);
946 // recalculateWordsInUse() is unnecessary
951 * Performs a logical <b>XOR</b> of this bit set with the bit set
952 * argument. This bit set is modified so that a bit in it has the
953 * value {@code true} if and only if one of the following
956 * <li>The bit initially has the value {@code true}, and the
957 * corresponding bit in the argument has the value {@code false}.
958 * <li>The bit initially has the value {@code false}, and the
959 * corresponding bit in the argument has the value {@code true}.
962 * @param set a bit set
964 public void xor(BitSet set) {
965 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
967 if (wordsInUse < set.wordsInUse) {
968 ensureCapacity(set.wordsInUse);
969 wordsInUse = set.wordsInUse;
972 // Perform logical XOR on words in common
973 for (int i = 0; i < wordsInCommon; i++)
974 words[i] ^= set.words[i];
976 // Copy any remaining words
977 if (wordsInCommon < set.wordsInUse)
978 System.arraycopy(set.words, wordsInCommon,
979 words, wordsInCommon,
980 set.wordsInUse - wordsInCommon);
982 recalculateWordsInUse();
987 * Clears all of the bits in this {@code BitSet} whose corresponding
988 * bit is set in the specified {@code BitSet}.
990 * @param set the {@code BitSet} with which to mask this
994 public void andNot(BitSet set) {
995 // Perform logical (a & !b) on words in common
996 for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
997 words[i] &= ~set.words[i];
999 recalculateWordsInUse();
1004 * Returns the hash code value for this bit set. The hash code depends
1005 * only on which bits are set within this {@code BitSet}.
1007 * <p>The hash code is defined to be the result of the following
1010 * public int hashCode() {
1012 * long[] words = toLongArray();
1013 * for (int i = words.length; --i >= 0; )
1014 * h ^= words[i] * (i + 1);
1015 * return (int)((h >> 32) ^ h);
1017 * Note that the hash code changes if the set of bits is altered.
1019 * @return the hash code value for this bit set
1021 public int hashCode() {
1023 for (int i = wordsInUse; --i >= 0; )
1024 h ^= words[i] * (i + 1);
1026 return (int)((h >> 32) ^ h);
1030 * Returns the number of bits of space actually in use by this
1031 * {@code BitSet} to represent bit values.
1032 * The maximum element in the set is the size - 1st element.
1034 * @return the number of bits currently in this bit set
1037 return words.length * BITS_PER_WORD;
1041 * Compares this object against the specified object.
1042 * The result is {@code true} if and only if the argument is
1043 * not {@code null} and is a {@code Bitset} object that has
1044 * exactly the same set of bits set to {@code true} as this bit
1045 * set. That is, for every nonnegative {@code int} index {@code k},
1046 * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
1047 * must be true. The current sizes of the two bit sets are not compared.
1049 * @param obj the object to compare with
1050 * @return {@code true} if the objects are the same;
1051 * {@code false} otherwise
1054 public boolean equals(Object obj) {
1055 if (!(obj instanceof BitSet))
1060 BitSet set = (BitSet) obj;
1063 set.checkInvariants();
1065 if (wordsInUse != set.wordsInUse)
1068 // Check words in use by both BitSets
1069 for (int i = 0; i < wordsInUse; i++)
1070 if (words[i] != set.words[i])
1077 * Cloning this {@code BitSet} produces a new {@code BitSet}
1078 * that is equal to it.
1079 * The clone of the bit set is another bit set that has exactly the
1080 * same bits set to {@code true} as this bit set.
1082 * @return a clone of this bit set
1085 public Object clone() {
1090 BitSet result = (BitSet) super.clone();
1091 result.words = words.clone();
1092 result.checkInvariants();
1094 } catch (CloneNotSupportedException e) {
1095 throw new InternalError();
1100 * Attempts to reduce internal storage used for the bits in this bit set.
1101 * Calling this method may, but is not required to, affect the value
1102 * returned by a subsequent call to the {@link #size()} method.
1104 private void trimToSize() {
1105 if (wordsInUse != words.length) {
1106 words = Arrays.copyOf(words, wordsInUse);
1112 * Save the state of the {@code BitSet} instance to a stream (i.e.,
1115 private void writeObject(ObjectOutputStream s)
1116 throws IOException {
1123 ObjectOutputStream.PutField fields = s.putFields();
1124 fields.put("bits", words);
1129 * Reconstitute the {@code BitSet} instance from a stream (i.e.,
1132 private void readObject(ObjectInputStream s)
1133 throws IOException, ClassNotFoundException {
1135 ObjectInputStream.GetField fields = s.readFields();
1136 words = (long[]) fields.get("bits", null);
1138 // Assume maximum length then find real length
1139 // because recalculateWordsInUse assumes maintenance
1140 // or reduction in logical size
1141 wordsInUse = words.length;
1142 recalculateWordsInUse();
1143 sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic
1148 * Returns a string representation of this bit set. For every index
1149 * for which this {@code BitSet} contains a bit in the set
1150 * state, the decimal representation of that index is included in
1151 * the result. Such indices are listed in order from lowest to
1152 * highest, separated by ", " (a comma and a space) and
1153 * surrounded by braces, resulting in the usual mathematical
1154 * notation for a set of integers.
1158 * BitSet drPepper = new BitSet();</pre>
1159 * Now {@code drPepper.toString()} returns "{@code {}}".<p>
1161 * drPepper.set(2);</pre>
1162 * Now {@code drPepper.toString()} returns "{@code {2}}".<p>
1165 * drPepper.set(10);</pre>
1166 * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
1168 * @return a string representation of this bit set
1170 public String toString() {
1173 int numBits = (wordsInUse > 128) ?
1174 cardinality() : wordsInUse * BITS_PER_WORD;
1175 StringBuilder b = new StringBuilder(6*numBits + 2);
1178 int i = nextSetBit(0);
1181 for (i = nextSetBit(i+1); i >= 0; i = nextSetBit(i+1)) {
1182 int endOfRun = nextClearBit(i);
1183 do { b.append(", ").append(i); }
1184 while (++i < endOfRun);
1189 return b.toString();