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