1 /* 2 * Copyright (c) 1995, 2011, 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 ", " (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 }