1 /* 2 * Copyright (c) 1995, 2020, 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 */ wordIndex(int bitIndex)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 */ checkInvariants()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 */ recalculateWordsInUse()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 */ BitSet()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 */ BitSet(int nbits)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 initWords(int nbits)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 */ BitSet(long[] words)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 */ valueOf(long[] longs)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 */ valueOf(LongBuffer lb)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 */ valueOf(byte[] bytes)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 */ valueOf(ByteBuffer bb)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 */ toByteArray()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 */ toLongArray()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 */ ensureCapacity(int wordsRequired)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 */ expandTo(int wordIndex)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 */ checkRange(int fromIndex, int toIndex)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 */ flip(int bitIndex)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 */ flip(int fromIndex, int toIndex)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 */ set(int bitIndex)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 */ set(int bitIndex, boolean value)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 */ set(int fromIndex, int toIndex)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 */ set(int fromIndex, int toIndex, boolean value)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 */ clear(int bitIndex)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 */ clear(int fromIndex, int toIndex)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 */ clear()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 */ get(int bitIndex)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 */ get(int fromIndex, int toIndex)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 */ nextSetBit(int fromIndex)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 */ nextClearBit(int fromIndex)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 */ previousSetBit(int fromIndex)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 */ previousClearBit(int fromIndex)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 */ length()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 */ isEmpty()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 */ intersects(BitSet set)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 */ cardinality()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 */ and(BitSet set)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 */ or(BitSet set)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 */ xor(BitSet set)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 */ andNot(BitSet set)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 */ hashCode()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 */ size()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 */ equals(Object obj)1068 public boolean equals(Object obj) { 1069 if (!(obj instanceof BitSet set)) 1070 return false; 1071 if (this == obj) 1072 return true; 1073 1074 checkInvariants(); 1075 set.checkInvariants(); 1076 1077 if (wordsInUse != set.wordsInUse) 1078 return false; 1079 1080 // Check words in use by both BitSets 1081 for (int i = 0; i < wordsInUse; i++) 1082 if (words[i] != set.words[i]) 1083 return false; 1084 1085 return true; 1086 } 1087 1088 /** 1089 * Cloning this {@code BitSet} produces a new {@code BitSet} 1090 * that is equal to it. 1091 * The clone of the bit set is another bit set that has exactly the 1092 * same bits set to {@code true} as this bit set. 1093 * 1094 * @return a clone of this bit set 1095 * @see #size() 1096 */ clone()1097 public Object clone() { 1098 if (! sizeIsSticky) 1099 trimToSize(); 1100 1101 try { 1102 BitSet result = (BitSet) super.clone(); 1103 result.words = words.clone(); 1104 result.checkInvariants(); 1105 return result; 1106 } catch (CloneNotSupportedException e) { 1107 throw new InternalError(e); 1108 } 1109 } 1110 1111 /** 1112 * Attempts to reduce internal storage used for the bits in this bit set. 1113 * Calling this method may, but is not required to, affect the value 1114 * returned by a subsequent call to the {@link #size()} method. 1115 */ trimToSize()1116 private void trimToSize() { 1117 if (wordsInUse != words.length) { 1118 words = Arrays.copyOf(words, wordsInUse); 1119 checkInvariants(); 1120 } 1121 } 1122 1123 /** 1124 * Save the state of the {@code BitSet} instance to a stream (i.e., 1125 * serialize it). 1126 */ 1127 @java.io.Serial writeObject(ObjectOutputStream s)1128 private void writeObject(ObjectOutputStream s) 1129 throws IOException { 1130 1131 checkInvariants(); 1132 1133 if (! sizeIsSticky) 1134 trimToSize(); 1135 1136 ObjectOutputStream.PutField fields = s.putFields(); 1137 fields.put("bits", words); 1138 s.writeFields(); 1139 } 1140 1141 /** 1142 * Reconstitute the {@code BitSet} instance from a stream (i.e., 1143 * deserialize it). 1144 */ 1145 @java.io.Serial readObject(ObjectInputStream s)1146 private void readObject(ObjectInputStream s) 1147 throws IOException, ClassNotFoundException { 1148 1149 ObjectInputStream.GetField fields = s.readFields(); 1150 words = (long[]) fields.get("bits", null); 1151 1152 // Assume maximum length then find real length 1153 // because recalculateWordsInUse assumes maintenance 1154 // or reduction in logical size 1155 wordsInUse = words.length; 1156 recalculateWordsInUse(); 1157 sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic 1158 checkInvariants(); 1159 } 1160 1161 /** 1162 * Returns a string representation of this bit set. For every index 1163 * for which this {@code BitSet} contains a bit in the set 1164 * state, the decimal representation of that index is included in 1165 * the result. Such indices are listed in order from lowest to 1166 * highest, separated by ", " (a comma and a space) and 1167 * surrounded by braces, resulting in the usual mathematical 1168 * notation for a set of integers. 1169 * 1170 * <p>Example: 1171 * <pre> 1172 * BitSet drPepper = new BitSet();</pre> 1173 * Now {@code drPepper.toString()} returns "{@code {}}". 1174 * <pre> 1175 * drPepper.set(2);</pre> 1176 * Now {@code drPepper.toString()} returns "{@code {2}}". 1177 * <pre> 1178 * drPepper.set(4); 1179 * drPepper.set(10);</pre> 1180 * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}". 1181 * 1182 * @return a string representation of this bit set 1183 */ toString()1184 public String toString() { 1185 checkInvariants(); 1186 1187 final int MAX_INITIAL_CAPACITY = Integer.MAX_VALUE - 8; 1188 int numBits = (wordsInUse > 128) ? 1189 cardinality() : wordsInUse * BITS_PER_WORD; 1190 // Avoid overflow in the case of a humongous numBits 1191 int initialCapacity = (numBits <= (MAX_INITIAL_CAPACITY - 2) / 6) ? 1192 6 * numBits + 2 : MAX_INITIAL_CAPACITY; 1193 StringBuilder b = new StringBuilder(initialCapacity); 1194 b.append('{'); 1195 1196 int i = nextSetBit(0); 1197 if (i != -1) { 1198 b.append(i); 1199 while (true) { 1200 if (++i < 0) break; 1201 if ((i = nextSetBit(i)) < 0) break; 1202 int endOfRun = nextClearBit(i); 1203 do { b.append(", ").append(i); } 1204 while (++i != endOfRun); 1205 } 1206 } 1207 1208 b.append('}'); 1209 return b.toString(); 1210 } 1211 1212 /** 1213 * Returns a stream of indices for which this {@code BitSet} 1214 * contains a bit in the set state. The indices are returned 1215 * in order, from lowest to highest. The size of the stream 1216 * is the number of bits in the set state, equal to the value 1217 * returned by the {@link #cardinality()} method. 1218 * 1219 * <p>The stream binds to this bit set when the terminal stream operation 1220 * commences (specifically, the spliterator for the stream is 1221 * <a href="Spliterator.html#binding"><em>late-binding</em></a>). If the 1222 * bit set is modified during that operation then the result is undefined. 1223 * 1224 * @return a stream of integers representing set indices 1225 * @since 1.8 1226 */ stream()1227 public IntStream stream() { 1228 class BitSetSpliterator implements Spliterator.OfInt { 1229 private int index; // current bit index for a set bit 1230 private int fence; // -1 until used; then one past last bit index 1231 private int est; // size estimate 1232 private boolean root; // true if root and not split 1233 // root == true then size estimate is accurate 1234 // index == -1 or index >= fence if fully traversed 1235 // Special case when the max bit set is Integer.MAX_VALUE 1236 1237 BitSetSpliterator(int origin, int fence, int est, boolean root) { 1238 this.index = origin; 1239 this.fence = fence; 1240 this.est = est; 1241 this.root = root; 1242 } 1243 1244 private int getFence() { 1245 int hi; 1246 if ((hi = fence) < 0) { 1247 // Round up fence to maximum cardinality for allocated words 1248 // This is sufficient and cheap for sequential access 1249 // When splitting this value is lowered 1250 hi = fence = (wordsInUse >= wordIndex(Integer.MAX_VALUE)) 1251 ? Integer.MAX_VALUE 1252 : wordsInUse << ADDRESS_BITS_PER_WORD; 1253 est = cardinality(); 1254 index = nextSetBit(0); 1255 } 1256 return hi; 1257 } 1258 1259 @Override 1260 public boolean tryAdvance(IntConsumer action) { 1261 Objects.requireNonNull(action); 1262 1263 int hi = getFence(); 1264 int i = index; 1265 if (i < 0 || i >= hi) { 1266 // Check if there is a final bit set for Integer.MAX_VALUE 1267 if (i == Integer.MAX_VALUE && hi == Integer.MAX_VALUE) { 1268 index = -1; 1269 action.accept(Integer.MAX_VALUE); 1270 return true; 1271 } 1272 return false; 1273 } 1274 1275 index = nextSetBit(i + 1, wordIndex(hi - 1)); 1276 action.accept(i); 1277 return true; 1278 } 1279 1280 @Override 1281 public void forEachRemaining(IntConsumer action) { 1282 Objects.requireNonNull(action); 1283 1284 int hi = getFence(); 1285 int i = index; 1286 index = -1; 1287 1288 if (i >= 0 && i < hi) { 1289 action.accept(i++); 1290 1291 int u = wordIndex(i); // next lower word bound 1292 int v = wordIndex(hi - 1); // upper word bound 1293 1294 words_loop: 1295 for (; u <= v && i <= hi; u++, i = u << ADDRESS_BITS_PER_WORD) { 1296 long word = words[u] & (WORD_MASK << i); 1297 while (word != 0) { 1298 i = (u << ADDRESS_BITS_PER_WORD) + Long.numberOfTrailingZeros(word); 1299 if (i >= hi) { 1300 // Break out of outer loop to ensure check of 1301 // Integer.MAX_VALUE bit set 1302 break words_loop; 1303 } 1304 1305 // Flip the set bit 1306 word &= ~(1L << i); 1307 1308 action.accept(i); 1309 } 1310 } 1311 } 1312 1313 // Check if there is a final bit set for Integer.MAX_VALUE 1314 if (i == Integer.MAX_VALUE && hi == Integer.MAX_VALUE) { 1315 action.accept(Integer.MAX_VALUE); 1316 } 1317 } 1318 1319 @Override 1320 public OfInt trySplit() { 1321 int hi = getFence(); 1322 int lo = index; 1323 if (lo < 0) { 1324 return null; 1325 } 1326 1327 // Lower the fence to be the upper bound of last bit set 1328 // The index is the first bit set, thus this spliterator 1329 // covers one bit and cannot be split, or two or more 1330 // bits 1331 hi = fence = (hi < Integer.MAX_VALUE || !get(Integer.MAX_VALUE)) 1332 ? previousSetBit(hi - 1) + 1 1333 : Integer.MAX_VALUE; 1334 1335 // Find the mid point 1336 int mid = (lo + hi) >>> 1; 1337 if (lo >= mid) { 1338 return null; 1339 } 1340 1341 // Raise the index of this spliterator to be the next set bit 1342 // from the mid point 1343 index = nextSetBit(mid, wordIndex(hi - 1)); 1344 root = false; 1345 1346 // Don't lower the fence (mid point) of the returned spliterator, 1347 // traversal or further splitting will do that work 1348 return new BitSetSpliterator(lo, mid, est >>>= 1, false); 1349 } 1350 1351 @Override 1352 public long estimateSize() { 1353 getFence(); // force init 1354 return est; 1355 } 1356 1357 @Override 1358 public int characteristics() { 1359 // Only sized when root and not split 1360 return (root ? Spliterator.SIZED : 0) | 1361 Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED; 1362 } 1363 1364 @Override 1365 public Comparator<? super Integer> getComparator() { 1366 return null; 1367 } 1368 } 1369 return StreamSupport.intStream(new BitSetSpliterator(0, -1, 0, true), false); 1370 } 1371 1372 /** 1373 * Returns the index of the first bit that is set to {@code true} 1374 * that occurs on or after the specified starting index and up to and 1375 * including the specified word index 1376 * If no such bit exists then {@code -1} is returned. 1377 * 1378 * @param fromIndex the index to start checking from (inclusive) 1379 * @param toWordIndex the last word index to check (inclusive) 1380 * @return the index of the next set bit, or {@code -1} if there 1381 * is no such bit 1382 */ nextSetBit(int fromIndex, int toWordIndex)1383 private int nextSetBit(int fromIndex, int toWordIndex) { 1384 int u = wordIndex(fromIndex); 1385 // Check if out of bounds 1386 if (u > toWordIndex) 1387 return -1; 1388 1389 long word = words[u] & (WORD_MASK << fromIndex); 1390 1391 while (true) { 1392 if (word != 0) 1393 return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word); 1394 // Check if out of bounds 1395 if (++u > toWordIndex) 1396 return -1; 1397 word = words[u]; 1398 } 1399 } 1400 1401 } 1402