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