View Javadoc
1   /*
2    * Copyright (c) 1995, 2013, Oracle and/or its affiliates. All rights reserved.
3    * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4    *
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.
10   *
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).
16   *
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.
20   *
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
23   * questions.
24   */
25  
26  package java.util;
27  
28  import java.io.*;
29  import java.nio.ByteBuffer;
30  import java.nio.ByteOrder;
31  import java.nio.LongBuffer;
32  import java.util.stream.IntStream;
33  import java.util.stream.StreamSupport;
34  
35  /**
36   * This class implements a vector of bits that grows as needed. Each
37   * component of the bit set has a {@code boolean} value. The
38   * bits of a {@code BitSet} are indexed by nonnegative integers.
39   * Individual indexed bits can be examined, set, or cleared. One
40   * {@code BitSet} may be used to modify the contents of another
41   * {@code BitSet} through logical AND, logical inclusive OR, and
42   * logical exclusive OR operations.
43   *
44   * <p>By default, all bits in the set initially have the value
45   * {@code false}.
46   *
47   * <p>Every bit set has a current size, which is the number of bits
48   * of space currently in use by the bit set. Note that the size is
49   * related to the implementation of a bit set, so it may change with
50   * implementation. The length of a bit set relates to logical length
51   * of a bit set and is defined independently of implementation.
52   *
53   * <p>Unless otherwise noted, passing a null parameter to any of the
54   * methods in a {@code BitSet} will result in a
55   * {@code NullPointerException}.
56   *
57   * <p>A {@code BitSet} is not safe for multithreaded use without
58   * external synchronization.
59   *
60   * @author  Arthur van Hoff
61   * @author  Michael McCloskey
62   * @author  Martin Buchholz
63   * @since   JDK1.0
64   */
65  public class BitSet implements Cloneable, java.io.Serializable {
66      /*
67       * BitSets are packed into arrays of "words."  Currently a word is
68       * a long, which consists of 64 bits, requiring 6 address bits.
69       * The choice of word size is determined purely by performance concerns.
70       */
71      private final static int ADDRESS_BITS_PER_WORD = 6;
72      private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
73      private final static int BIT_INDEX_MASK = BITS_PER_WORD - 1;
74  
75      /* Used to shift left or right for a partial word mask */
76      private static final long WORD_MASK = 0xffffffffffffffffL;
77  
78      /**
79       * @serialField bits long[]
80       *
81       * The bits in this BitSet.  The ith bit is stored in bits[i/64] at
82       * bit position i % 64 (where bit position 0 refers to the least
83       * significant bit and 63 refers to the most significant bit).
84       */
85      private static final ObjectStreamField[] serialPersistentFields = {
86          new ObjectStreamField("bits", long[].class),
87      };
88  
89      /**
90       * The internal field corresponding to the serialField "bits".
91       */
92      private long[] words;
93  
94      /**
95       * The number of words in the logical size of this BitSet.
96       */
97      private transient int wordsInUse = 0;
98  
99      /**
100      * Whether the size of "words" is user-specified.  If so, we assume
101      * the user knows what he's doing and try harder to preserve it.
102      */
103     private transient boolean sizeIsSticky = false;
104 
105     /* use serialVersionUID from JDK 1.0.2 for interoperability */
106     private static final long serialVersionUID = 7997698588986878753L;
107 
108     /**
109      * Given a bit index, return word index containing it.
110      */
111     private static int wordIndex(int bitIndex) {
112         return bitIndex >> ADDRESS_BITS_PER_WORD;
113     }
114 
115     /**
116      * Every public method must preserve these invariants.
117      */
118     private void checkInvariants() {
119         assert(wordsInUse == 0 || words[wordsInUse - 1] != 0);
120         assert(wordsInUse >= 0 && wordsInUse <= words.length);
121         assert(wordsInUse == words.length || words[wordsInUse] == 0);
122     }
123 
124     /**
125      * Sets the field wordsInUse to the logical size in words of the bit set.
126      * WARNING:This method assumes that the number of words actually in use is
127      * less than or equal to the current value of wordsInUse!
128      */
129     private void recalculateWordsInUse() {
130         // Traverse the bitset until a used word is found
131         int i;
132         for (i = wordsInUse-1; i >= 0; i--)
133             if (words[i] != 0)
134                 break;
135 
136         wordsInUse = i+1; // The new logical size
137     }
138 
139     /**
140      * Creates a new bit set. All bits are initially {@code false}.
141      */
142     public BitSet() {
143         initWords(BITS_PER_WORD);
144         sizeIsSticky = false;
145     }
146 
147     /**
148      * Creates a bit set whose initial size is large enough to explicitly
149      * represent bits with indices in the range {@code 0} through
150      * {@code nbits-1}. All bits are initially {@code false}.
151      *
152      * @param  nbits the initial size of the bit set
153      * @throws NegativeArraySizeException if the specified initial size
154      *         is negative
155      */
156     public BitSet(int nbits) {
157         // nbits can't be negative; size 0 is OK
158         if (nbits < 0)
159             throw new NegativeArraySizeException("nbits < 0: " + nbits);
160 
161         initWords(nbits);
162         sizeIsSticky = true;
163     }
164 
165     private void initWords(int nbits) {
166         words = new long[wordIndex(nbits-1) + 1];
167     }
168 
169     /**
170      * Creates a bit set using words as the internal representation.
171      * The last word (if there is one) must be non-zero.
172      */
173     private BitSet(long[] words) {
174         this.words = words;
175         this.wordsInUse = words.length;
176         checkInvariants();
177     }
178 
179     /**
180      * Returns a new bit set containing all the bits in the given long array.
181      *
182      * <p>More precisely,
183      * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
184      * <br>for all {@code n < 64 * longs.length}.
185      *
186      * <p>This method is equivalent to
187      * {@code BitSet.valueOf(LongBuffer.wrap(longs))}.
188      *
189      * @param longs a long array containing a little-endian representation
190      *        of a sequence of bits to be used as the initial bits of the
191      *        new bit set
192      * @return a {@code BitSet} containing all the bits in the long array
193      * @since 1.7
194      */
195     public static BitSet valueOf(long[] longs) {
196         int n;
197         for (n = longs.length; n > 0 && longs[n - 1] == 0; n--)
198             ;
199         return new BitSet(Arrays.copyOf(longs, n));
200     }
201 
202     /**
203      * Returns a new bit set containing all the bits in the given long
204      * buffer between its position and limit.
205      *
206      * <p>More precisely,
207      * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)}
208      * <br>for all {@code n < 64 * lb.remaining()}.
209      *
210      * <p>The long buffer is not modified by this method, and no
211      * reference to the buffer is retained by the bit set.
212      *
213      * @param lb a long buffer containing a little-endian representation
214      *        of a sequence of bits between its position and limit, to be
215      *        used as the initial bits of the new bit set
216      * @return a {@code BitSet} containing all the bits in the buffer in the
217      *         specified range
218      * @since 1.7
219      */
220     public static BitSet valueOf(LongBuffer lb) {
221         lb = lb.slice();
222         int n;
223         for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--)
224             ;
225         long[] words = new long[n];
226         lb.get(words);
227         return new BitSet(words);
228     }
229 
230     /**
231      * Returns a new bit set containing all the bits in the given byte array.
232      *
233      * <p>More precisely,
234      * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
235      * <br>for all {@code n <  8 * bytes.length}.
236      *
237      * <p>This method is equivalent to
238      * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}.
239      *
240      * @param bytes a byte array containing a little-endian
241      *        representation of a sequence of bits to be used as the
242      *        initial bits of the new bit set
243      * @return a {@code BitSet} containing all the bits in the byte array
244      * @since 1.7
245      */
246     public static BitSet valueOf(byte[] bytes) {
247         return BitSet.valueOf(ByteBuffer.wrap(bytes));
248     }
249 
250     /**
251      * Returns a new bit set containing all the bits in the given byte
252      * buffer between its position and limit.
253      *
254      * <p>More precisely,
255      * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)}
256      * <br>for all {@code n < 8 * bb.remaining()}.
257      *
258      * <p>The byte buffer is not modified by this method, and no
259      * reference to the buffer is retained by the bit set.
260      *
261      * @param bb a byte buffer containing a little-endian representation
262      *        of a sequence of bits between its position and limit, to be
263      *        used as the initial bits of the new bit set
264      * @return a {@code BitSet} containing all the bits in the buffer in the
265      *         specified range
266      * @since 1.7
267      */
268     public static BitSet valueOf(ByteBuffer bb) {
269         bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN);
270         int n;
271         for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--)
272             ;
273         long[] words = new long[(n + 7) / 8];
274         bb.limit(n);
275         int i = 0;
276         while (bb.remaining() >= 8)
277             words[i++] = bb.getLong();
278         for (int remaining = bb.remaining(), j = 0; j < remaining; j++)
279             words[i] |= (bb.get() & 0xffL) << (8 * j);
280         return new BitSet(words);
281     }
282 
283     /**
284      * Returns a new byte array containing all the bits in this bit set.
285      *
286      * <p>More precisely, if
287      * <br>{@code byte[] bytes = s.toByteArray();}
288      * <br>then {@code bytes.length == (s.length()+7)/8} and
289      * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)}
290      * <br>for all {@code n < 8 * bytes.length}.
291      *
292      * @return a byte array containing a little-endian representation
293      *         of all the bits in this bit set
294      * @since 1.7
295     */
296     public byte[] toByteArray() {
297         int n = wordsInUse;
298         if (n == 0)
299             return new byte[0];
300         int len = 8 * (n-1);
301         for (long x = words[n - 1]; x != 0; x >>>= 8)
302             len++;
303         byte[] bytes = new byte[len];
304         ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN);
305         for (int i = 0; i < n - 1; i++)
306             bb.putLong(words[i]);
307         for (long x = words[n - 1]; x != 0; x >>>= 8)
308             bb.put((byte) (x & 0xff));
309         return bytes;
310     }
311 
312     /**
313      * Returns a new long array containing all the bits in this bit set.
314      *
315      * <p>More precisely, if
316      * <br>{@code long[] longs = s.toLongArray();}
317      * <br>then {@code longs.length == (s.length()+63)/64} and
318      * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)}
319      * <br>for all {@code n < 64 * longs.length}.
320      *
321      * @return a long array containing a little-endian representation
322      *         of all the bits in this bit set
323      * @since 1.7
324     */
325     public long[] toLongArray() {
326         return Arrays.copyOf(words, wordsInUse);
327     }
328 
329     /**
330      * Ensures that the BitSet can hold enough words.
331      * @param wordsRequired the minimum acceptable number of words.
332      */
333     private void ensureCapacity(int wordsRequired) {
334         if (words.length < wordsRequired) {
335             // Allocate larger of doubled size or required size
336             int request = Math.max(2 * words.length, wordsRequired);
337             words = Arrays.copyOf(words, request);
338             sizeIsSticky = false;
339         }
340     }
341 
342     /**
343      * Ensures that the BitSet can accommodate a given wordIndex,
344      * temporarily violating the invariants.  The caller must
345      * restore the invariants before returning to the user,
346      * possibly using recalculateWordsInUse().
347      * @param wordIndex the index to be accommodated.
348      */
349     private void expandTo(int wordIndex) {
350         int wordsRequired = wordIndex+1;
351         if (wordsInUse < wordsRequired) {
352             ensureCapacity(wordsRequired);
353             wordsInUse = wordsRequired;
354         }
355     }
356 
357     /**
358      * Checks that fromIndex ... toIndex is a valid range of bit indices.
359      */
360     private static void checkRange(int fromIndex, int toIndex) {
361         if (fromIndex < 0)
362             throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
363         if (toIndex < 0)
364             throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
365         if (fromIndex > toIndex)
366             throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
367                                                 " > toIndex: " + toIndex);
368     }
369 
370     /**
371      * Sets the bit at the specified index to the complement of its
372      * current value.
373      *
374      * @param  bitIndex the index of the bit to flip
375      * @throws IndexOutOfBoundsException if the specified index is negative
376      * @since  1.4
377      */
378     public void flip(int bitIndex) {
379         if (bitIndex < 0)
380             throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
381 
382         int wordIndex = wordIndex(bitIndex);
383         expandTo(wordIndex);
384 
385         words[wordIndex] ^= (1L << bitIndex);
386 
387         recalculateWordsInUse();
388         checkInvariants();
389     }
390 
391     /**
392      * Sets each bit from the specified {@code fromIndex} (inclusive) to the
393      * specified {@code toIndex} (exclusive) to the complement of its current
394      * value.
395      *
396      * @param  fromIndex index of the first bit to flip
397      * @param  toIndex index after the last bit to flip
398      * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
399      *         or {@code toIndex} is negative, or {@code fromIndex} is
400      *         larger than {@code toIndex}
401      * @since  1.4
402      */
403     public void flip(int fromIndex, int toIndex) {
404         checkRange(fromIndex, toIndex);
405 
406         if (fromIndex == toIndex)
407             return;
408 
409         int startWordIndex = wordIndex(fromIndex);
410         int endWordIndex   = wordIndex(toIndex - 1);
411         expandTo(endWordIndex);
412 
413         long firstWordMask = WORD_MASK << fromIndex;
414         long lastWordMask  = WORD_MASK >>> -toIndex;
415         if (startWordIndex == endWordIndex) {
416             // Case 1: One word
417             words[startWordIndex] ^= (firstWordMask & lastWordMask);
418         } else {
419             // Case 2: Multiple words
420             // Handle first word
421             words[startWordIndex] ^= firstWordMask;
422 
423             // Handle intermediate words, if any
424             for (int i = startWordIndex+1; i < endWordIndex; i++)
425                 words[i] ^= WORD_MASK;
426 
427             // Handle last word
428             words[endWordIndex] ^= lastWordMask;
429         }
430 
431         recalculateWordsInUse();
432         checkInvariants();
433     }
434 
435     /**
436      * Sets the bit at the specified index to {@code true}.
437      *
438      * @param  bitIndex a bit index
439      * @throws IndexOutOfBoundsException if the specified index is negative
440      * @since  JDK1.0
441      */
442     public void set(int bitIndex) {
443         if (bitIndex < 0)
444             throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
445 
446         int wordIndex = wordIndex(bitIndex);
447         expandTo(wordIndex);
448 
449         words[wordIndex] |= (1L << bitIndex); // Restores invariants
450 
451         checkInvariants();
452     }
453 
454     /**
455      * Sets the bit at the specified index to the specified value.
456      *
457      * @param  bitIndex a bit index
458      * @param  value a boolean value to set
459      * @throws IndexOutOfBoundsException if the specified index is negative
460      * @since  1.4
461      */
462     public void set(int bitIndex, boolean value) {
463         if (value)
464             set(bitIndex);
465         else
466             clear(bitIndex);
467     }
468 
469     /**
470      * Sets the bits from the specified {@code fromIndex} (inclusive) to the
471      * specified {@code toIndex} (exclusive) to {@code true}.
472      *
473      * @param  fromIndex index of the first bit to be set
474      * @param  toIndex index after the last bit to be set
475      * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
476      *         or {@code toIndex} is negative, or {@code fromIndex} is
477      *         larger than {@code toIndex}
478      * @since  1.4
479      */
480     public void set(int fromIndex, int toIndex) {
481         checkRange(fromIndex, toIndex);
482 
483         if (fromIndex == toIndex)
484             return;
485 
486         // Increase capacity if necessary
487         int startWordIndex = wordIndex(fromIndex);
488         int endWordIndex   = wordIndex(toIndex - 1);
489         expandTo(endWordIndex);
490 
491         long firstWordMask = WORD_MASK << fromIndex;
492         long lastWordMask  = WORD_MASK >>> -toIndex;
493         if (startWordIndex == endWordIndex) {
494             // Case 1: One word
495             words[startWordIndex] |= (firstWordMask & lastWordMask);
496         } else {
497             // Case 2: Multiple words
498             // Handle first word
499             words[startWordIndex] |= firstWordMask;
500 
501             // Handle intermediate words, if any
502             for (int i = startWordIndex+1; i < endWordIndex; i++)
503                 words[i] = WORD_MASK;
504 
505             // Handle last word (restores invariants)
506             words[endWordIndex] |= lastWordMask;
507         }
508 
509         checkInvariants();
510     }
511 
512     /**
513      * Sets the bits from the specified {@code fromIndex} (inclusive) to the
514      * specified {@code toIndex} (exclusive) to the specified value.
515      *
516      * @param  fromIndex index of the first bit to be set
517      * @param  toIndex index after the last bit to be set
518      * @param  value value to set the selected bits to
519      * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
520      *         or {@code toIndex} is negative, or {@code fromIndex} is
521      *         larger than {@code toIndex}
522      * @since  1.4
523      */
524     public void set(int fromIndex, int toIndex, boolean value) {
525         if (value)
526             set(fromIndex, toIndex);
527         else
528             clear(fromIndex, toIndex);
529     }
530 
531     /**
532      * Sets the bit specified by the index to {@code false}.
533      *
534      * @param  bitIndex the index of the bit to be cleared
535      * @throws IndexOutOfBoundsException if the specified index is negative
536      * @since  JDK1.0
537      */
538     public void clear(int bitIndex) {
539         if (bitIndex < 0)
540             throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
541 
542         int wordIndex = wordIndex(bitIndex);
543         if (wordIndex >= wordsInUse)
544             return;
545 
546         words[wordIndex] &= ~(1L << bitIndex);
547 
548         recalculateWordsInUse();
549         checkInvariants();
550     }
551 
552     /**
553      * Sets the bits from the specified {@code fromIndex} (inclusive) to the
554      * specified {@code toIndex} (exclusive) to {@code false}.
555      *
556      * @param  fromIndex index of the first bit to be cleared
557      * @param  toIndex index after the last bit to be cleared
558      * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
559      *         or {@code toIndex} is negative, or {@code fromIndex} is
560      *         larger than {@code toIndex}
561      * @since  1.4
562      */
563     public void clear(int fromIndex, int toIndex) {
564         checkRange(fromIndex, toIndex);
565 
566         if (fromIndex == toIndex)
567             return;
568 
569         int startWordIndex = wordIndex(fromIndex);
570         if (startWordIndex >= wordsInUse)
571             return;
572 
573         int endWordIndex = wordIndex(toIndex - 1);
574         if (endWordIndex >= wordsInUse) {
575             toIndex = length();
576             endWordIndex = wordsInUse - 1;
577         }
578 
579         long firstWordMask = WORD_MASK << fromIndex;
580         long lastWordMask  = WORD_MASK >>> -toIndex;
581         if (startWordIndex == endWordIndex) {
582             // Case 1: One word
583             words[startWordIndex] &= ~(firstWordMask & lastWordMask);
584         } else {
585             // Case 2: Multiple words
586             // Handle first word
587             words[startWordIndex] &= ~firstWordMask;
588 
589             // Handle intermediate words, if any
590             for (int i = startWordIndex+1; i < endWordIndex; i++)
591                 words[i] = 0;
592 
593             // Handle last word
594             words[endWordIndex] &= ~lastWordMask;
595         }
596 
597         recalculateWordsInUse();
598         checkInvariants();
599     }
600 
601     /**
602      * Sets all of the bits in this BitSet to {@code false}.
603      *
604      * @since 1.4
605      */
606     public void clear() {
607         while (wordsInUse > 0)
608             words[--wordsInUse] = 0;
609     }
610 
611     /**
612      * Returns the value of the bit with the specified index. The value
613      * is {@code true} if the bit with the index {@code bitIndex}
614      * is currently set in this {@code BitSet}; otherwise, the result
615      * is {@code false}.
616      *
617      * @param  bitIndex   the bit index
618      * @return the value of the bit with the specified index
619      * @throws IndexOutOfBoundsException if the specified index is negative
620      */
621     public boolean get(int bitIndex) {
622         if (bitIndex < 0)
623             throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
624 
625         checkInvariants();
626 
627         int wordIndex = wordIndex(bitIndex);
628         return (wordIndex < wordsInUse)
629             && ((words[wordIndex] & (1L << bitIndex)) != 0);
630     }
631 
632     /**
633      * Returns a new {@code BitSet} composed of bits from this {@code BitSet}
634      * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive).
635      *
636      * @param  fromIndex index of the first bit to include
637      * @param  toIndex index after the last bit to include
638      * @return a new {@code BitSet} from a range of this {@code BitSet}
639      * @throws IndexOutOfBoundsException if {@code fromIndex} is negative,
640      *         or {@code toIndex} is negative, or {@code fromIndex} is
641      *         larger than {@code toIndex}
642      * @since  1.4
643      */
644     public BitSet get(int fromIndex, int toIndex) {
645         checkRange(fromIndex, toIndex);
646 
647         checkInvariants();
648 
649         int len = length();
650 
651         // If no set bits in range return empty bitset
652         if (len <= fromIndex || fromIndex == toIndex)
653             return new BitSet(0);
654 
655         // An optimization
656         if (toIndex > len)
657             toIndex = len;
658 
659         BitSet result = new BitSet(toIndex - fromIndex);
660         int targetWords = wordIndex(toIndex - fromIndex - 1) + 1;
661         int sourceIndex = wordIndex(fromIndex);
662         boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0);
663 
664         // Process all words but the last word
665         for (int i = 0; i < targetWords - 1; i++, sourceIndex++)
666             result.words[i] = wordAligned ? words[sourceIndex] :
667                 (words[sourceIndex] >>> fromIndex) |
668                 (words[sourceIndex+1] << -fromIndex);
669 
670         // Process the last word
671         long lastWordMask = WORD_MASK >>> -toIndex;
672         result.words[targetWords - 1] =
673             ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK)
674             ? /* straddles source words */
675             ((words[sourceIndex] >>> fromIndex) |
676              (words[sourceIndex+1] & lastWordMask) << -fromIndex)
677             :
678             ((words[sourceIndex] & lastWordMask) >>> fromIndex);
679 
680         // Set wordsInUse correctly
681         result.wordsInUse = targetWords;
682         result.recalculateWordsInUse();
683         result.checkInvariants();
684 
685         return result;
686     }
687 
688     /**
689      * Returns the index of the first bit that is set to {@code true}
690      * that occurs on or after the specified starting index. If no such
691      * bit exists then {@code -1} is returned.
692      *
693      * <p>To iterate over the {@code true} bits in a {@code BitSet},
694      * use the following loop:
695      *
696      *  <pre> {@code
697      * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
698      *     // operate on index i here
699      * }}</pre>
700      *
701      * @param  fromIndex the index to start checking from (inclusive)
702      * @return the index of the next set bit, or {@code -1} if there
703      *         is no such bit
704      * @throws IndexOutOfBoundsException if the specified index is negative
705      * @since  1.4
706      */
707     public int nextSetBit(int fromIndex) {
708         if (fromIndex < 0)
709             throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
710 
711         checkInvariants();
712 
713         int u = wordIndex(fromIndex);
714         if (u >= wordsInUse)
715             return -1;
716 
717         long word = words[u] & (WORD_MASK << fromIndex);
718 
719         while (true) {
720             if (word != 0)
721                 return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
722             if (++u == wordsInUse)
723                 return -1;
724             word = words[u];
725         }
726     }
727 
728     /**
729      * Returns the index of the first bit that is set to {@code false}
730      * that occurs on or after the specified starting index.
731      *
732      * @param  fromIndex the index to start checking from (inclusive)
733      * @return the index of the next clear bit
734      * @throws IndexOutOfBoundsException if the specified index is negative
735      * @since  1.4
736      */
737     public int nextClearBit(int fromIndex) {
738         // Neither spec nor implementation handle bitsets of maximal length.
739         // See 4816253.
740         if (fromIndex < 0)
741             throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
742 
743         checkInvariants();
744 
745         int u = wordIndex(fromIndex);
746         if (u >= wordsInUse)
747             return fromIndex;
748 
749         long word = ~words[u] & (WORD_MASK << fromIndex);
750 
751         while (true) {
752             if (word != 0)
753                 return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word);
754             if (++u == wordsInUse)
755                 return wordsInUse * BITS_PER_WORD;
756             word = ~words[u];
757         }
758     }
759 
760     /**
761      * Returns the index of the nearest bit that is set to {@code true}
762      * that occurs on or before the specified starting index.
763      * If no such bit exists, or if {@code -1} is given as the
764      * starting index, then {@code -1} is returned.
765      *
766      * <p>To iterate over the {@code true} bits in a {@code BitSet},
767      * use the following loop:
768      *
769      *  <pre> {@code
770      * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) {
771      *     // operate on index i here
772      * }}</pre>
773      *
774      * @param  fromIndex the index to start checking from (inclusive)
775      * @return the index of the previous set bit, or {@code -1} if there
776      *         is no such bit
777      * @throws IndexOutOfBoundsException if the specified index is less
778      *         than {@code -1}
779      * @since  1.7
780      */
781     public int previousSetBit(int fromIndex) {
782         if (fromIndex < 0) {
783             if (fromIndex == -1)
784                 return -1;
785             throw new IndexOutOfBoundsException(
786                 "fromIndex < -1: " + fromIndex);
787         }
788 
789         checkInvariants();
790 
791         int u = wordIndex(fromIndex);
792         if (u >= wordsInUse)
793             return length() - 1;
794 
795         long word = words[u] & (WORD_MASK >>> -(fromIndex+1));
796 
797         while (true) {
798             if (word != 0)
799                 return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word);
800             if (u-- == 0)
801                 return -1;
802             word = words[u];
803         }
804     }
805 
806     /**
807      * Returns the index of the nearest bit that is set to {@code false}
808      * that occurs on or before the specified starting index.
809      * If no such bit exists, or if {@code -1} is given as the
810      * starting index, then {@code -1} is returned.
811      *
812      * @param  fromIndex the index to start checking from (inclusive)
813      * @return the index of the previous clear bit, or {@code -1} if there
814      *         is no such bit
815      * @throws IndexOutOfBoundsException if the specified index is less
816      *         than {@code -1}
817      * @since  1.7
818      */
819     public int previousClearBit(int fromIndex) {
820         if (fromIndex < 0) {
821             if (fromIndex == -1)
822                 return -1;
823             throw new IndexOutOfBoundsException(
824                 "fromIndex < -1: " + fromIndex);
825         }
826 
827         checkInvariants();
828 
829         int u = wordIndex(fromIndex);
830         if (u >= wordsInUse)
831             return fromIndex;
832 
833         long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1));
834 
835         while (true) {
836             if (word != 0)
837                 return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word);
838             if (u-- == 0)
839                 return -1;
840             word = ~words[u];
841         }
842     }
843 
844     /**
845      * Returns the "logical size" of this {@code BitSet}: the index of
846      * the highest set bit in the {@code BitSet} plus one. Returns zero
847      * if the {@code BitSet} contains no set bits.
848      *
849      * @return the logical size of this {@code BitSet}
850      * @since  1.2
851      */
852     public int length() {
853         if (wordsInUse == 0)
854             return 0;
855 
856         return BITS_PER_WORD * (wordsInUse - 1) +
857             (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1]));
858     }
859 
860     /**
861      * Returns true if this {@code BitSet} contains no bits that are set
862      * to {@code true}.
863      *
864      * @return boolean indicating whether this {@code BitSet} is empty
865      * @since  1.4
866      */
867     public boolean isEmpty() {
868         return wordsInUse == 0;
869     }
870 
871     /**
872      * Returns true if the specified {@code BitSet} has any bits set to
873      * {@code true} that are also set to {@code true} in this {@code BitSet}.
874      *
875      * @param  set {@code BitSet} to intersect with
876      * @return boolean indicating whether this {@code BitSet} intersects
877      *         the specified {@code BitSet}
878      * @since  1.4
879      */
880     public boolean intersects(BitSet set) {
881         for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
882             if ((words[i] & set.words[i]) != 0)
883                 return true;
884         return false;
885     }
886 
887     /**
888      * Returns the number of bits set to {@code true} in this {@code BitSet}.
889      *
890      * @return the number of bits set to {@code true} in this {@code BitSet}
891      * @since  1.4
892      */
893     public int cardinality() {
894         int sum = 0;
895         for (int i = 0; i < wordsInUse; i++)
896             sum += Long.bitCount(words[i]);
897         return sum;
898     }
899 
900     /**
901      * Performs a logical <b>AND</b> of this target bit set with the
902      * argument bit set. This bit set is modified so that each bit in it
903      * has the value {@code true} if and only if it both initially
904      * had the value {@code true} and the corresponding bit in the
905      * bit set argument also had the value {@code true}.
906      *
907      * @param set a bit set
908      */
909     public void and(BitSet set) {
910         if (this == set)
911             return;
912 
913         while (wordsInUse > set.wordsInUse)
914             words[--wordsInUse] = 0;
915 
916         // Perform logical AND on words in common
917         for (int i = 0; i < wordsInUse; i++)
918             words[i] &= set.words[i];
919 
920         recalculateWordsInUse();
921         checkInvariants();
922     }
923 
924     /**
925      * Performs a logical <b>OR</b> of this bit set with the bit set
926      * argument. This bit set is modified so that a bit in it has the
927      * value {@code true} if and only if it either already had the
928      * value {@code true} or the corresponding bit in the bit set
929      * argument has the value {@code true}.
930      *
931      * @param set a bit set
932      */
933     public void or(BitSet set) {
934         if (this == set)
935             return;
936 
937         int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
938 
939         if (wordsInUse < set.wordsInUse) {
940             ensureCapacity(set.wordsInUse);
941             wordsInUse = set.wordsInUse;
942         }
943 
944         // Perform logical OR on words in common
945         for (int i = 0; i < wordsInCommon; i++)
946             words[i] |= set.words[i];
947 
948         // Copy any remaining words
949         if (wordsInCommon < set.wordsInUse)
950             System.arraycopy(set.words, wordsInCommon,
951                              words, wordsInCommon,
952                              wordsInUse - wordsInCommon);
953 
954         // recalculateWordsInUse() is unnecessary
955         checkInvariants();
956     }
957 
958     /**
959      * Performs a logical <b>XOR</b> of this bit set with the bit set
960      * argument. This bit set is modified so that a bit in it has the
961      * value {@code true} if and only if one of the following
962      * statements holds:
963      * <ul>
964      * <li>The bit initially has the value {@code true}, and the
965      *     corresponding bit in the argument has the value {@code false}.
966      * <li>The bit initially has the value {@code false}, and the
967      *     corresponding bit in the argument has the value {@code true}.
968      * </ul>
969      *
970      * @param  set a bit set
971      */
972     public void xor(BitSet set) {
973         int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
974 
975         if (wordsInUse < set.wordsInUse) {
976             ensureCapacity(set.wordsInUse);
977             wordsInUse = set.wordsInUse;
978         }
979 
980         // Perform logical XOR on words in common
981         for (int i = 0; i < wordsInCommon; i++)
982             words[i] ^= set.words[i];
983 
984         // Copy any remaining words
985         if (wordsInCommon < set.wordsInUse)
986             System.arraycopy(set.words, wordsInCommon,
987                              words, wordsInCommon,
988                              set.wordsInUse - wordsInCommon);
989 
990         recalculateWordsInUse();
991         checkInvariants();
992     }
993 
994     /**
995      * Clears all of the bits in this {@code BitSet} whose corresponding
996      * bit is set in the specified {@code BitSet}.
997      *
998      * @param  set the {@code BitSet} with which to mask this
999      *         {@code BitSet}
1000      * @since  1.2
1001      */
1002     public void andNot(BitSet set) {
1003         // Perform logical (a & !b) on words in common
1004         for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
1005             words[i] &= ~set.words[i];
1006 
1007         recalculateWordsInUse();
1008         checkInvariants();
1009     }
1010 
1011     /**
1012      * Returns the hash code value for this bit set. The hash code depends
1013      * only on which bits are set within this {@code BitSet}.
1014      *
1015      * <p>The hash code is defined to be the result of the following
1016      * calculation:
1017      *  <pre> {@code
1018      * public int hashCode() {
1019      *     long h = 1234;
1020      *     long[] words = toLongArray();
1021      *     for (int i = words.length; --i >= 0; )
1022      *         h ^= words[i] * (i + 1);
1023      *     return (int)((h >> 32) ^ h);
1024      * }}</pre>
1025      * Note that the hash code changes if the set of bits is altered.
1026      *
1027      * @return the hash code value for this bit set
1028      */
1029     public int hashCode() {
1030         long h = 1234;
1031         for (int i = wordsInUse; --i >= 0; )
1032             h ^= words[i] * (i + 1);
1033 
1034         return (int)((h >> 32) ^ h);
1035     }
1036 
1037     /**
1038      * Returns the number of bits of space actually in use by this
1039      * {@code BitSet} to represent bit values.
1040      * The maximum element in the set is the size - 1st element.
1041      *
1042      * @return the number of bits currently in this bit set
1043      */
1044     public int size() {
1045         return words.length * BITS_PER_WORD;
1046     }
1047 
1048     /**
1049      * Compares this object against the specified object.
1050      * The result is {@code true} if and only if the argument is
1051      * not {@code null} and is a {@code Bitset} object that has
1052      * exactly the same set of bits set to {@code true} as this bit
1053      * set. That is, for every nonnegative {@code int} index {@code k},
1054      * <pre>((BitSet)obj).get(k) == this.get(k)</pre>
1055      * must be true. The current sizes of the two bit sets are not compared.
1056      *
1057      * @param  obj the object to compare with
1058      * @return {@code true} if the objects are the same;
1059      *         {@code false} otherwise
1060      * @see    #size()
1061      */
1062     public boolean equals(Object obj) {
1063         if (!(obj instanceof BitSet))
1064             return false;
1065         if (this == obj)
1066             return true;
1067 
1068         BitSet set = (BitSet) obj;
1069 
1070         checkInvariants();
1071         set.checkInvariants();
1072 
1073         if (wordsInUse != set.wordsInUse)
1074             return false;
1075 
1076         // Check words in use by both BitSets
1077         for (int i = 0; i < wordsInUse; i++)
1078             if (words[i] != set.words[i])
1079                 return false;
1080 
1081         return true;
1082     }
1083 
1084     /**
1085      * Cloning this {@code BitSet} produces a new {@code BitSet}
1086      * that is equal to it.
1087      * The clone of the bit set is another bit set that has exactly the
1088      * same bits set to {@code true} as this bit set.
1089      *
1090      * @return a clone of this bit set
1091      * @see    #size()
1092      */
1093     public Object clone() {
1094         if (! sizeIsSticky)
1095             trimToSize();
1096 
1097         try {
1098             BitSet result = (BitSet) super.clone();
1099             result.words = words.clone();
1100             result.checkInvariants();
1101             return result;
1102         } catch (CloneNotSupportedException e) {
1103             throw new InternalError(e);
1104         }
1105     }
1106 
1107     /**
1108      * Attempts to reduce internal storage used for the bits in this bit set.
1109      * Calling this method may, but is not required to, affect the value
1110      * returned by a subsequent call to the {@link #size()} method.
1111      */
1112     private void trimToSize() {
1113         if (wordsInUse != words.length) {
1114             words = Arrays.copyOf(words, wordsInUse);
1115             checkInvariants();
1116         }
1117     }
1118 
1119     /**
1120      * Save the state of the {@code BitSet} instance to a stream (i.e.,
1121      * serialize it).
1122      */
1123     private void writeObject(ObjectOutputStream s)
1124         throws IOException {
1125 
1126         checkInvariants();
1127 
1128         if (! sizeIsSticky)
1129             trimToSize();
1130 
1131         ObjectOutputStream.PutField fields = s.putFields();
1132         fields.put("bits", words);
1133         s.writeFields();
1134     }
1135 
1136     /**
1137      * Reconstitute the {@code BitSet} instance from a stream (i.e.,
1138      * deserialize it).
1139      */
1140     private void readObject(ObjectInputStream s)
1141         throws IOException, ClassNotFoundException {
1142 
1143         ObjectInputStream.GetField fields = s.readFields();
1144         words = (long[]) fields.get("bits", null);
1145 
1146         // Assume maximum length then find real length
1147         // because recalculateWordsInUse assumes maintenance
1148         // or reduction in logical size
1149         wordsInUse = words.length;
1150         recalculateWordsInUse();
1151         sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic
1152         checkInvariants();
1153     }
1154 
1155     /**
1156      * Returns a string representation of this bit set. For every index
1157      * for which this {@code BitSet} contains a bit in the set
1158      * state, the decimal representation of that index is included in
1159      * the result. Such indices are listed in order from lowest to
1160      * highest, separated by ",&nbsp;" (a comma and a space) and
1161      * surrounded by braces, resulting in the usual mathematical
1162      * notation for a set of integers.
1163      *
1164      * <p>Example:
1165      * <pre>
1166      * BitSet drPepper = new BitSet();</pre>
1167      * Now {@code drPepper.toString()} returns "{@code {}}".
1168      * <pre>
1169      * drPepper.set(2);</pre>
1170      * Now {@code drPepper.toString()} returns "{@code {2}}".
1171      * <pre>
1172      * drPepper.set(4);
1173      * drPepper.set(10);</pre>
1174      * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}".
1175      *
1176      * @return a string representation of this bit set
1177      */
1178     public String toString() {
1179         checkInvariants();
1180 
1181         int numBits = (wordsInUse > 128) ?
1182             cardinality() : wordsInUse * BITS_PER_WORD;
1183         StringBuilder b = new StringBuilder(6*numBits + 2);
1184         b.append('{');
1185 
1186         int i = nextSetBit(0);
1187         if (i != -1) {
1188             b.append(i);
1189             for (i = nextSetBit(i+1); i >= 0; i = nextSetBit(i+1)) {
1190                 int endOfRun = nextClearBit(i);
1191                 do { b.append(", ").append(i); }
1192                 while (++i < endOfRun);
1193             }
1194         }
1195 
1196         b.append('}');
1197         return b.toString();
1198     }
1199 
1200     /**
1201      * Returns a stream of indices for which this {@code BitSet}
1202      * contains a bit in the set state. The indices are returned
1203      * in order, from lowest to highest. The size of the stream
1204      * is the number of bits in the set state, equal to the value
1205      * returned by the {@link #cardinality()} method.
1206      *
1207      * <p>The bit set must remain constant during the execution of the
1208      * terminal stream operation.  Otherwise, the result of the terminal
1209      * stream operation is undefined.
1210      *
1211      * @return a stream of integers representing set indices
1212      * @since 1.8
1213      */
1214     public IntStream stream() {
1215         class BitSetIterator implements PrimitiveIterator.OfInt {
1216             int next = nextSetBit(0);
1217 
1218             @Override
1219             public boolean hasNext() {
1220                 return next != -1;
1221             }
1222 
1223             @Override
1224             public int nextInt() {
1225                 if (next != -1) {
1226                     int ret = next;
1227                     next = nextSetBit(next+1);
1228                     return ret;
1229                 } else {
1230                     throw new NoSuchElementException();
1231                 }
1232             }
1233         }
1234 
1235         return StreamSupport.intStream(
1236                 () -> Spliterators.spliterator(
1237                         new BitSetIterator(), cardinality(),
1238                         Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED),
1239                 Spliterator.SIZED | Spliterator.SUBSIZED |
1240                         Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED,
1241                 false);
1242     }
1243 }