| /* | |
| * Copyright (c) 1995, 2024, Oracle and/or its affiliates. All rights reserved. | |
| * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
| * | |
| * This code is free software; you can redistribute it and/or modify it | |
| * under the terms of the GNU General Public License version 2 only, as | |
| * published by the Free Software Foundation. Oracle designates this | |
| * particular file as subject to the "Classpath" exception as provided | |
| * by Oracle in the LICENSE file that accompanied this code. | |
| * | |
| * This code is distributed in the hope that it will be useful, but WITHOUT | |
| * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| * version 2 for more details (a copy is included in the LICENSE file that | |
| * accompanied this code). | |
| * | |
| * You should have received a copy of the GNU General Public License version | |
| * 2 along with this work; if not, write to the Free Software Foundation, | |
| * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| * | |
| * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA | |
| * or visit www.oracle.com if you need additional information or have any | |
| * questions. | |
| */ | |
| package java.util; | |
| import java.io.*; | |
| import java.nio.ByteBuffer; | |
| import java.nio.ByteOrder; | |
| import java.nio.LongBuffer; | |
| import java.util.function.IntConsumer; | |
| import java.util.stream.IntStream; | |
| import java.util.stream.StreamSupport; | |
| import jdk.internal.util.ArraysSupport; | |
| /** | |
| * This class implements a vector of bits that grows as needed. Each | |
| * component of the bit set has a {@code boolean} value. The | |
| * bits of a {@code BitSet} are indexed by nonnegative integers. | |
| * Individual indexed bits can be examined, set, or cleared. One | |
| * {@code BitSet} may be used to modify the contents of another | |
| * {@code BitSet} through logical AND, logical inclusive OR, and | |
| * logical exclusive OR operations. | |
| * | |
| * <p>By default, all bits in the set initially have the value | |
| * {@code false}. | |
| * | |
| * <p>Every bit set has a current size, which is the number of bits | |
| * of space currently in use by the bit set. Note that the size is | |
| * related to the implementation of a bit set, so it may change with | |
| * implementation. The length of a bit set relates to logical length | |
| * of a bit set and is defined independently of implementation. | |
| * | |
| * <p>Unless otherwise noted, passing a null parameter to any of the | |
| * methods in a {@code BitSet} will result in a | |
| * {@code NullPointerException}. | |
| * | |
| * <p>A {@code BitSet} is not safe for multithreaded use without | |
| * external synchronization. | |
| * | |
| * @author Arthur van Hoff | |
| * @author Michael McCloskey | |
| * @author Martin Buchholz | |
| * @since 1.0 | |
| */ | |
| public class BitSet implements Cloneable, java.io.Serializable { | |
| /* | |
| * BitSets are packed into arrays of "words." Currently a word is | |
| * a long, which consists of 64 bits, requiring 6 address bits. | |
| * The choice of word size is determined purely by performance concerns. | |
| */ | |
| private static final int ADDRESS_BITS_PER_WORD = 6; | |
| private static final int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD; | |
| private static final int BIT_INDEX_MASK = BITS_PER_WORD - 1; | |
| /* Used to shift left or right for a partial word mask */ | |
| private static final long WORD_MASK = 0xffffffffffffffffL; | |
| /** | |
| * @serialField bits long[] | |
| * | |
| * The bits in this BitSet. The ith bit is stored in bits[i/64] at | |
| * bit position i % 64 (where bit position 0 refers to the least | |
| * significant bit and 63 refers to the most significant bit). | |
| */ | |
| @java.io.Serial | |
| private static final ObjectStreamField[] serialPersistentFields = { | |
| new ObjectStreamField("bits", long[].class), | |
| }; | |
| /** | |
| * The internal field corresponding to the serialField "bits". | |
| */ | |
| private long[] words; | |
| /** | |
| * The number of words in the logical size of this BitSet. | |
| */ | |
| private transient int wordsInUse = 0; | |
| /** | |
| * Whether the size of "words" is user-specified. If so, we assume | |
| * the user knows what he's doing and try harder to preserve it. | |
| */ | |
| private transient boolean sizeIsSticky = false; | |
| /* use serialVersionUID from JDK 1.0.2 for interoperability */ | |
| @java.io.Serial | |
| private static final long serialVersionUID = 7997698588986878753L; | |
| /** | |
| * Given a bit index, return word index containing it. | |
| */ | |
| private static int wordIndex(int bitIndex) { | |
| return bitIndex >> ADDRESS_BITS_PER_WORD; | |
| } | |
| /** | |
| * Every public method must preserve these invariants. | |
| */ | |
| private void checkInvariants() { | |
| assert(wordsInUse == 0 || words[wordsInUse - 1] != 0); | |
| assert(wordsInUse >= 0 && wordsInUse <= words.length); | |
| assert(wordsInUse == words.length || words[wordsInUse] == 0); | |
| } | |
| /** | |
| * Sets the field wordsInUse to the logical size in words of the bit set. | |
| * WARNING:This method assumes that the number of words actually in use is | |
| * less than or equal to the current value of wordsInUse! | |
| */ | |
| private void recalculateWordsInUse() { | |
| // Traverse the bitset until a used word is found | |
| int i; | |
| for (i = wordsInUse-1; i >= 0; i--) | |
| if (words[i] != 0) | |
| break; | |
| wordsInUse = i+1; // The new logical size | |
| } | |
| /** | |
| * Creates a new bit set. All bits are initially {@code false}. | |
| */ | |
| public BitSet() { | |
| initWords(BITS_PER_WORD); | |
| sizeIsSticky = false; | |
| } | |
| /** | |
| * Creates a bit set whose initial size is large enough to explicitly | |
| * represent bits with indices in the range {@code 0} through | |
| * {@code nbits-1}. All bits are initially {@code false}. | |
| * | |
| * @param nbits the initial size of the bit set | |
| * @throws NegativeArraySizeException if the specified initial size | |
| * is negative | |
| */ | |
| public BitSet(int nbits) { | |
| // nbits can't be negative; size 0 is OK | |
| if (nbits < 0) | |
| throw new NegativeArraySizeException("nbits < 0: " + nbits); | |
| initWords(nbits); | |
| sizeIsSticky = true; | |
| } | |
| private void initWords(int nbits) { | |
| words = new long[wordIndex(nbits-1) + 1]; | |
| } | |
| /** | |
| * Creates a bit set using words as the internal representation. | |
| * The last word (if there is one) must be non-zero. | |
| */ | |
| private BitSet(long[] words) { | |
| this.words = words; | |
| this.wordsInUse = words.length; | |
| checkInvariants(); | |
| } | |
| /** | |
| * Returns a new bit set containing all the bits in the given long array. | |
| * | |
| * <p>More precisely, | |
| * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)} | |
| * <br>for all {@code n < 64 * longs.length}. | |
| * | |
| * <p>This method is equivalent to | |
| * {@code BitSet.valueOf(LongBuffer.wrap(longs))}. | |
| * | |
| * @param longs a long array containing a little-endian representation | |
| * of a sequence of bits to be used as the initial bits of the | |
| * new bit set | |
| * @return a {@code BitSet} containing all the bits in the long array | |
| * @since 1.7 | |
| */ | |
| public static BitSet valueOf(long[] longs) { | |
| int n; | |
| for (n = longs.length; n > 0 && longs[n - 1] == 0; n--) | |
| ; | |
| return new BitSet(Arrays.copyOf(longs, n)); | |
| } | |
| /** | |
| * Returns a new bit set containing all the bits in the given long | |
| * buffer between its position and limit. | |
| * | |
| * <p>More precisely, | |
| * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)} | |
| * <br>for all {@code n < 64 * lb.remaining()}. | |
| * | |
| * <p>The long buffer is not modified by this method, and no | |
| * reference to the buffer is retained by the bit set. | |
| * | |
| * @param lb a long buffer containing a little-endian representation | |
| * of a sequence of bits between its position and limit, to be | |
| * used as the initial bits of the new bit set | |
| * @return a {@code BitSet} containing all the bits in the buffer in the | |
| * specified range | |
| * @since 1.7 | |
| */ | |
| public static BitSet valueOf(LongBuffer lb) { | |
| lb = lb.slice(); | |
| int n; | |
| for (n = lb.remaining(); n > 0 && lb.get(n - 1) == 0; n--) | |
| ; | |
| long[] words = new long[n]; | |
| lb.get(words); | |
| return new BitSet(words); | |
| } | |
| /** | |
| * Returns a new bit set containing all the bits in the given byte array. | |
| * | |
| * <p>More precisely, | |
| * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)} | |
| * <br>for all {@code n < 8 * bytes.length}. | |
| * | |
| * <p>This method is equivalent to | |
| * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}. | |
| * | |
| * @param bytes a byte array containing a little-endian | |
| * representation of a sequence of bits to be used as the | |
| * initial bits of the new bit set | |
| * @return a {@code BitSet} containing all the bits in the byte array | |
| * @since 1.7 | |
| */ | |
| public static BitSet valueOf(byte[] bytes) { | |
| return BitSet.valueOf(ByteBuffer.wrap(bytes)); | |
| } | |
| /** | |
| * Returns a new bit set containing all the bits in the given byte | |
| * buffer between its position and limit. | |
| * | |
| * <p>More precisely, | |
| * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)} | |
| * <br>for all {@code n < 8 * bb.remaining()}. | |
| * | |
| * <p>The byte buffer is not modified by this method, and no | |
| * reference to the buffer is retained by the bit set. | |
| * | |
| * @param bb a byte buffer containing a little-endian representation | |
| * of a sequence of bits between its position and limit, to be | |
| * used as the initial bits of the new bit set | |
| * @return a {@code BitSet} containing all the bits in the buffer in the | |
| * specified range | |
| * @since 1.7 | |
| */ | |
| public static BitSet valueOf(ByteBuffer bb) { | |
| bb = bb.slice().order(ByteOrder.LITTLE_ENDIAN); | |
| int n; | |
| for (n = bb.remaining(); n > 0 && bb.get(n - 1) == 0; n--) | |
| ; | |
| long[] words = new long[(n + 7) / 8]; | |
| bb.limit(n); | |
| int i = 0; | |
| while (bb.remaining() >= 8) | |
| words[i++] = bb.getLong(); | |
| for (int remaining = bb.remaining(), j = 0; j < remaining; j++) | |
| words[i] |= (bb.get() & 0xffL) << (8 * j); | |
| return new BitSet(words); | |
| } | |
| /** | |
| * Returns a new byte array containing all the bits in this bit set. | |
| * | |
| * <p>More precisely, if | |
| * <br>{@code byte[] bytes = s.toByteArray();} | |
| * <br>then {@code bytes.length == (s.length()+7)/8} and | |
| * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)} | |
| * <br>for all {@code n < 8 * bytes.length}. | |
| * | |
| * @return a byte array containing a little-endian representation | |
| * of all the bits in this bit set | |
| * @since 1.7 | |
| */ | |
| public byte[] toByteArray() { | |
| int n = wordsInUse; | |
| if (n == 0) | |
| return new byte[0]; | |
| int len = 8 * (n-1); | |
| for (long x = words[n - 1]; x != 0; x >>>= 8) | |
| len++; | |
| byte[] bytes = new byte[len]; | |
| ByteBuffer bb = ByteBuffer.wrap(bytes).order(ByteOrder.LITTLE_ENDIAN); | |
| for (int i = 0; i < n - 1; i++) | |
| bb.putLong(words[i]); | |
| for (long x = words[n - 1]; x != 0; x >>>= 8) | |
| bb.put((byte) (x & 0xff)); | |
| return bytes; | |
| } | |
| /** | |
| * Returns a new long array containing all the bits in this bit set. | |
| * | |
| * <p>More precisely, if | |
| * <br>{@code long[] longs = s.toLongArray();} | |
| * <br>then {@code longs.length == (s.length()+63)/64} and | |
| * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)} | |
| * <br>for all {@code n < 64 * longs.length}. | |
| * | |
| * @return a long array containing a little-endian representation | |
| * of all the bits in this bit set | |
| * @since 1.7 | |
| */ | |
| public long[] toLongArray() { | |
| return Arrays.copyOf(words, wordsInUse); | |
| } | |
| /** | |
| * Ensures that the BitSet can hold enough words. | |
| * @param wordsRequired the minimum acceptable number of words. | |
| */ | |
| private void ensureCapacity(int wordsRequired) { | |
| if (words.length < wordsRequired) { | |
| // Allocate larger of doubled size or required size | |
| int request = Math.max(2 * words.length, wordsRequired); | |
| words = Arrays.copyOf(words, request); | |
| sizeIsSticky = false; | |
| } | |
| } | |
| /** | |
| * Ensures that the BitSet can accommodate a given wordIndex, | |
| * temporarily violating the invariants. The caller must | |
| * restore the invariants before returning to the user, | |
| * possibly using recalculateWordsInUse(). | |
| * @param wordIndex the index to be accommodated. | |
| */ | |
| private void expandTo(int wordIndex) { | |
| int wordsRequired = wordIndex+1; | |
| if (wordsInUse < wordsRequired) { | |
| ensureCapacity(wordsRequired); | |
| wordsInUse = wordsRequired; | |
| } | |
| } | |
| /** | |
| * Checks that fromIndex ... toIndex is a valid range of bit indices. | |
| */ | |
| private static void checkRange(int fromIndex, int toIndex) { | |
| if (fromIndex < 0) | |
| throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex); | |
| if (toIndex < 0) | |
| throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex); | |
| if (fromIndex > toIndex) | |
| throw new IndexOutOfBoundsException("fromIndex: " + fromIndex + | |
| " > toIndex: " + toIndex); | |
| } | |
| /** | |
| * Sets the bit at the specified index to the complement of its | |
| * current value. | |
| * | |
| * @param bitIndex the index of the bit to flip | |
| * @throws IndexOutOfBoundsException if the specified index is negative | |
| * @since 1.4 | |
| */ | |
| public void flip(int bitIndex) { | |
| if (bitIndex < 0) | |
| throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex); | |
| int wordIndex = wordIndex(bitIndex); | |
| expandTo(wordIndex); | |
| words[wordIndex] ^= (1L << bitIndex); | |
| recalculateWordsInUse(); | |
| checkInvariants(); | |
| } | |
| /** | |
| * Sets each bit from the specified {@code fromIndex} (inclusive) to the | |
| * specified {@code toIndex} (exclusive) to the complement of its current | |
| * value. | |
| * | |
| * @param fromIndex index of the first bit to flip | |
| * @param toIndex index after the last bit to flip | |
| * @throws IndexOutOfBoundsException if {@code fromIndex} is negative, | |
| * or {@code toIndex} is negative, or {@code fromIndex} is | |
| * larger than {@code toIndex} | |
| * @since 1.4 | |
| */ | |
| public void flip(int fromIndex, int toIndex) { | |
| checkRange(fromIndex, toIndex); | |
| if (fromIndex == toIndex) | |
| return; | |
| int startWordIndex = wordIndex(fromIndex); | |
| int endWordIndex = wordIndex(toIndex - 1); | |
| expandTo(endWordIndex); | |
| long firstWordMask = WORD_MASK << fromIndex; | |
| long lastWordMask = WORD_MASK >>> -toIndex; | |
| if (startWordIndex == endWordIndex) { | |
| // Case 1: One word | |
| words[startWordIndex] ^= (firstWordMask & lastWordMask); | |
| } else { | |
| // Case 2: Multiple words | |
| // Handle first word | |
| words[startWordIndex] ^= firstWordMask; | |
| // Handle intermediate words, if any | |
| for (int i = startWordIndex+1; i < endWordIndex; i++) | |
| words[i] ^= WORD_MASK; | |
| // Handle last word | |
| words[endWordIndex] ^= lastWordMask; | |
| } | |
| recalculateWordsInUse(); | |
| checkInvariants(); | |
| } | |
| /** | |
| * Sets the bit at the specified index to {@code true}. | |
| * | |
| * @param bitIndex a bit index | |
| * @throws IndexOutOfBoundsException if the specified index is negative | |
| * @since 1.0 | |
| */ | |
| public void set(int bitIndex) { | |
| if (bitIndex < 0) | |
| throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex); | |
| int wordIndex = wordIndex(bitIndex); | |
| expandTo(wordIndex); | |
| words[wordIndex] |= (1L << bitIndex); // Restores invariants | |
| checkInvariants(); | |
| } | |
| /** | |
| * Sets the bit at the specified index to the specified value. | |
| * | |
| * @param bitIndex a bit index | |
| * @param value a boolean value to set | |
| * @throws IndexOutOfBoundsException if the specified index is negative | |
| * @since 1.4 | |
| */ | |
| public void set(int bitIndex, boolean value) { | |
| if (value) | |
| set(bitIndex); | |
| else | |
| clear(bitIndex); | |
| } | |
| /** | |
| * Sets the bits from the specified {@code fromIndex} (inclusive) to the | |
| * specified {@code toIndex} (exclusive) to {@code true}. | |
| * | |
| * @param fromIndex index of the first bit to be set | |
| * @param toIndex index after the last bit to be set | |
| * @throws IndexOutOfBoundsException if {@code fromIndex} is negative, | |
| * or {@code toIndex} is negative, or {@code fromIndex} is | |
| * larger than {@code toIndex} | |
| * @since 1.4 | |
| */ | |
| public void set(int fromIndex, int toIndex) { | |
| checkRange(fromIndex, toIndex); | |
| if (fromIndex == toIndex) | |
| return; | |
| // Increase capacity if necessary | |
| int startWordIndex = wordIndex(fromIndex); | |
| int endWordIndex = wordIndex(toIndex - 1); | |
| expandTo(endWordIndex); | |
| long firstWordMask = WORD_MASK << fromIndex; | |
| long lastWordMask = WORD_MASK >>> -toIndex; | |
| if (startWordIndex == endWordIndex) { | |
| // Case 1: One word | |
| words[startWordIndex] |= (firstWordMask & lastWordMask); | |
| } else { | |
| // Case 2: Multiple words | |
| // Handle first word | |
| words[startWordIndex] |= firstWordMask; | |
| // Handle intermediate words, if any | |
| for (int i = startWordIndex+1; i < endWordIndex; i++) | |
| words[i] = WORD_MASK; | |
| // Handle last word (restores invariants) | |
| words[endWordIndex] |= lastWordMask; | |
| } | |
| checkInvariants(); | |
| } | |
| /** | |
| * Sets the bits from the specified {@code fromIndex} (inclusive) to the | |
| * specified {@code toIndex} (exclusive) to the specified value. | |
| * | |
| * @param fromIndex index of the first bit to be set | |
| * @param toIndex index after the last bit to be set | |
| * @param value value to set the selected bits to | |
| * @throws IndexOutOfBoundsException if {@code fromIndex} is negative, | |
| * or {@code toIndex} is negative, or {@code fromIndex} is | |
| * larger than {@code toIndex} | |
| * @since 1.4 | |
| */ | |
| public void set(int fromIndex, int toIndex, boolean value) { | |
| if (value) | |
| set(fromIndex, toIndex); | |
| else | |
| clear(fromIndex, toIndex); | |
| } | |
| /** | |
| * Sets the bit specified by the index to {@code false}. | |
| * | |
| * @param bitIndex the index of the bit to be cleared | |
| * @throws IndexOutOfBoundsException if the specified index is negative | |
| * @since 1.0 | |
| */ | |
| public void clear(int bitIndex) { | |
| if (bitIndex < 0) | |
| throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex); | |
| int wordIndex = wordIndex(bitIndex); | |
| if (wordIndex >= wordsInUse) | |
| return; | |
| words[wordIndex] &= ~(1L << bitIndex); | |
| recalculateWordsInUse(); | |
| checkInvariants(); | |
| } | |
| /** | |
| * Sets the bits from the specified {@code fromIndex} (inclusive) to the | |
| * specified {@code toIndex} (exclusive) to {@code false}. | |
| * | |
| * @param fromIndex index of the first bit to be cleared | |
| * @param toIndex index after the last bit to be cleared | |
| * @throws IndexOutOfBoundsException if {@code fromIndex} is negative, | |
| * or {@code toIndex} is negative, or {@code fromIndex} is | |
| * larger than {@code toIndex} | |
| * @since 1.4 | |
| */ | |
| public void clear(int fromIndex, int toIndex) { | |
| checkRange(fromIndex, toIndex); | |
| if (fromIndex == toIndex) | |
| return; | |
| int startWordIndex = wordIndex(fromIndex); | |
| if (startWordIndex >= wordsInUse) | |
| return; | |
| int endWordIndex = wordIndex(toIndex - 1); | |
| if (endWordIndex >= wordsInUse) { | |
| toIndex = length(); | |
| endWordIndex = wordsInUse - 1; | |
| } | |
| long firstWordMask = WORD_MASK << fromIndex; | |
| long lastWordMask = WORD_MASK >>> -toIndex; | |
| if (startWordIndex == endWordIndex) { | |
| // Case 1: One word | |
| words[startWordIndex] &= ~(firstWordMask & lastWordMask); | |
| } else { | |
| // Case 2: Multiple words | |
| // Handle first word | |
| words[startWordIndex] &= ~firstWordMask; | |
| // Handle intermediate words, if any | |
| for (int i = startWordIndex+1; i < endWordIndex; i++) | |
| words[i] = 0; | |
| // Handle last word | |
| words[endWordIndex] &= ~lastWordMask; | |
| } | |
| recalculateWordsInUse(); | |
| checkInvariants(); | |
| } | |
| /** | |
| * Sets all of the bits in this BitSet to {@code false}. | |
| * | |
| * @since 1.4 | |
| */ | |
| public void clear() { | |
| while (wordsInUse > 0) | |
| words[--wordsInUse] = 0; | |
| } | |
| /** | |
| * Returns the value of the bit with the specified index. The value | |
| * is {@code true} if the bit with the index {@code bitIndex} | |
| * is currently set in this {@code BitSet}; otherwise, the result | |
| * is {@code false}. | |
| * | |
| * @param bitIndex the bit index | |
| * @return the value of the bit with the specified index | |
| * @throws IndexOutOfBoundsException if the specified index is negative | |
| */ | |
| public boolean get(int bitIndex) { | |
| if (bitIndex < 0) | |
| throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex); | |
| checkInvariants(); | |
| int wordIndex = wordIndex(bitIndex); | |
| return (wordIndex < wordsInUse) | |
| && ((words[wordIndex] & (1L << bitIndex)) != 0); | |
| } | |
| /** | |
| * Returns a new {@code BitSet} composed of bits from this {@code BitSet} | |
| * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive). | |
| * | |
| * @param fromIndex index of the first bit to include | |
| * @param toIndex index after the last bit to include | |
| * @return a new {@code BitSet} from a range of this {@code BitSet} | |
| * @throws IndexOutOfBoundsException if {@code fromIndex} is negative, | |
| * or {@code toIndex} is negative, or {@code fromIndex} is | |
| * larger than {@code toIndex} | |
| * @since 1.4 | |
| */ | |
| public BitSet get(int fromIndex, int toIndex) { | |
| checkRange(fromIndex, toIndex); | |
| checkInvariants(); | |
| int len = length(); | |
| // If no set bits in range return empty bitset | |
| if (len <= fromIndex || fromIndex == toIndex) | |
| return new BitSet(0); | |
| // An optimization | |
| if (toIndex > len) | |
| toIndex = len; | |
| BitSet result = new BitSet(toIndex - fromIndex); | |
| int targetWords = wordIndex(toIndex - fromIndex - 1) + 1; | |
| int sourceIndex = wordIndex(fromIndex); | |
| boolean wordAligned = ((fromIndex & BIT_INDEX_MASK) == 0); | |
| // Process all words but the last word | |
| for (int i = 0; i < targetWords - 1; i++, sourceIndex++) | |
| result.words[i] = wordAligned ? words[sourceIndex] : | |
| (words[sourceIndex] >>> fromIndex) | | |
| (words[sourceIndex+1] << -fromIndex); | |
| // Process the last word | |
| long lastWordMask = WORD_MASK >>> -toIndex; | |
| result.words[targetWords - 1] = | |
| ((toIndex-1) & BIT_INDEX_MASK) < (fromIndex & BIT_INDEX_MASK) | |
| ? /* straddles source words */ | |
| ((words[sourceIndex] >>> fromIndex) | | |
| (words[sourceIndex+1] & lastWordMask) << -fromIndex) | |
| : | |
| ((words[sourceIndex] & lastWordMask) >>> fromIndex); | |
| // Set wordsInUse correctly | |
| result.wordsInUse = targetWords; | |
| result.recalculateWordsInUse(); | |
| result.checkInvariants(); | |
| return result; | |
| } | |
| /** | |
| * Returns the index of the first bit that is set to {@code true} | |
| * that occurs on or after the specified starting index. If no such | |
| * bit exists then {@code -1} is returned. | |
| * | |
| * <p>To iterate over the {@code true} bits in a {@code BitSet}, | |
| * use the following loop: | |
| * | |
| * <pre> {@code | |
| * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) { | |
| * // operate on index i here | |
| * if (i == Integer.MAX_VALUE) { | |
| * break; // or (i+1) would overflow | |
| * } | |
| * }}</pre> | |
| * | |
| * @param fromIndex the index to start checking from (inclusive) | |
| * @return the index of the next set bit, or {@code -1} if there | |
| * is no such bit | |
| * @throws IndexOutOfBoundsException if the specified index is negative | |
| * @since 1.4 | |
| */ | |
| public int nextSetBit(int fromIndex) { | |
| if (fromIndex < 0) | |
| throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex); | |
| checkInvariants(); | |
| int u = wordIndex(fromIndex); | |
| if (u >= wordsInUse) | |
| return -1; | |
| long word = words[u] & (WORD_MASK << fromIndex); | |
| while (true) { | |
| if (word != 0) | |
| return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word); | |
| if (++u == wordsInUse) | |
| return -1; | |
| word = words[u]; | |
| } | |
| } | |
| /** | |
| * Returns the index of the first bit that is set to {@code false} | |
| * that occurs on or after the specified starting index. | |
| * | |
| * @param fromIndex the index to start checking from (inclusive) | |
| * @return the index of the next clear bit | |
| * @throws IndexOutOfBoundsException if the specified index is negative | |
| * @since 1.4 | |
| */ | |
| public int nextClearBit(int fromIndex) { | |
| // Neither spec nor implementation handle bitsets of maximal length. | |
| // See 4816253. | |
| if (fromIndex < 0) | |
| throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex); | |
| checkInvariants(); | |
| int u = wordIndex(fromIndex); | |
| if (u >= wordsInUse) | |
| return fromIndex; | |
| long word = ~words[u] & (WORD_MASK << fromIndex); | |
| while (true) { | |
| if (word != 0) | |
| return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word); | |
| if (++u == wordsInUse) | |
| return wordsInUse * BITS_PER_WORD; | |
| word = ~words[u]; | |
| } | |
| } | |
| /** | |
| * Returns the index of the nearest bit that is set to {@code true} | |
| * that occurs on or before the specified starting index. | |
| * If no such bit exists, or if {@code -1} is given as the | |
| * starting index, then {@code -1} is returned. | |
| * | |
| * <p>To iterate over the {@code true} bits in a {@code BitSet}, | |
| * use the following loop: | |
| * | |
| * <pre> {@code | |
| * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) { | |
| * // operate on index i here | |
| * }}</pre> | |
| * | |
| * @param fromIndex the index to start checking from (inclusive) | |
| * @return the index of the previous set bit, or {@code -1} if there | |
| * is no such bit | |
| * @throws IndexOutOfBoundsException if the specified index is less | |
| * than {@code -1} | |
| * @since 1.7 | |
| */ | |
| public int previousSetBit(int fromIndex) { | |
| if (fromIndex < 0) { | |
| if (fromIndex == -1) | |
| return -1; | |
| throw new IndexOutOfBoundsException( | |
| "fromIndex < -1: " + fromIndex); | |
| } | |
| checkInvariants(); | |
| int u = wordIndex(fromIndex); | |
| if (u >= wordsInUse) | |
| return length() - 1; | |
| long word = words[u] & (WORD_MASK >>> -(fromIndex+1)); | |
| while (true) { | |
| if (word != 0) | |
| return (u+1) * BITS_PER_WORD - 1 - Long.numberOfLeadingZeros(word); | |
| if (u-- == 0) | |
| return -1; | |
| word = words[u]; | |
| } | |
| } | |
| /** | |
| * Returns the index of the nearest bit that is set to {@code false} | |
| * that occurs on or before the specified starting index. | |
| * If no such bit exists, or if {@code -1} is given as the | |
| * starting index, then {@code -1} is returned. | |
| * | |
| * @param fromIndex the index to start checking from (inclusive) | |
| * @return the index of the previous clear bit, or {@code -1} if there | |
| * is no such bit | |
| * @throws IndexOutOfBoundsException if the specified index is less | |
| * than {@code -1} | |
| * @since 1.7 | |
| */ | |
| public int previousClearBit(int fromIndex) { | |
| if (fromIndex < 0) { | |
| if (fromIndex == -1) | |
| return -1; | |
| throw new IndexOutOfBoundsException( | |
| "fromIndex < -1: " + fromIndex); | |
| } | |
| checkInvariants(); | |
| int u = wordIndex(fromIndex); | |
| if (u >= wordsInUse) | |
| return fromIndex; | |
| long word = ~words[u] & (WORD_MASK >>> -(fromIndex+1)); | |
| while (true) { | |
| if (word != 0) | |
| return (u+1) * BITS_PER_WORD -1 - Long.numberOfLeadingZeros(word); | |
| if (u-- == 0) | |
| return -1; | |
| word = ~words[u]; | |
| } | |
| } | |
| /** | |
| * Returns the "logical size" of this {@code BitSet}: the index of | |
| * the highest set bit in the {@code BitSet} plus one. Returns zero | |
| * if the {@code BitSet} contains no set bits. | |
| * | |
| * @return the logical size of this {@code BitSet} | |
| * @since 1.2 | |
| */ | |
| public int length() { | |
| if (wordsInUse == 0) | |
| return 0; | |
| return BITS_PER_WORD * (wordsInUse - 1) + | |
| (BITS_PER_WORD - Long.numberOfLeadingZeros(words[wordsInUse - 1])); | |
| } | |
| /** | |
| * Returns true if this {@code BitSet} contains no bits that are set | |
| * to {@code true}. | |
| * | |
| * @return boolean indicating whether this {@code BitSet} is empty | |
| * @since 1.4 | |
| */ | |
| public boolean isEmpty() { | |
| return wordsInUse == 0; | |
| } | |
| /** | |
| * Returns true if the specified {@code BitSet} has any bits set to | |
| * {@code true} that are also set to {@code true} in this {@code BitSet}. | |
| * | |
| * @param set {@code BitSet} to intersect with | |
| * @return boolean indicating whether this {@code BitSet} intersects | |
| * the specified {@code BitSet} | |
| * @since 1.4 | |
| */ | |
| public boolean intersects(BitSet set) { | |
| for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--) | |
| if ((words[i] & set.words[i]) != 0) | |
| return true; | |
| return false; | |
| } | |
| /** | |
| * Returns the number of bits set to {@code true} in this {@code BitSet}. | |
| * | |
| * @return the number of bits set to {@code true} in this {@code BitSet} | |
| * @since 1.4 | |
| */ | |
| public int cardinality() { | |
| int sum = 0; | |
| for (int i = 0; i < wordsInUse; i++) | |
| sum += Long.bitCount(words[i]); | |
| return sum; | |
| } | |
| /** | |
| * Performs a logical <b>AND</b> of this target bit set with the | |
| * argument bit set. This bit set is modified so that each bit in it | |
| * has the value {@code true} if and only if it both initially | |
| * had the value {@code true} and the corresponding bit in the | |
| * bit set argument also had the value {@code true}. | |
| * | |
| * @param set a bit set | |
| */ | |
| public void and(BitSet set) { | |
| if (this == set) | |
| return; | |
| while (wordsInUse > set.wordsInUse) | |
| words[--wordsInUse] = 0; | |
| // Perform logical AND on words in common | |
| for (int i = 0; i < wordsInUse; i++) | |
| words[i] &= set.words[i]; | |
| recalculateWordsInUse(); | |
| checkInvariants(); | |
| } | |
| /** | |
| * Performs a logical <b>OR</b> of this bit set with the bit set | |
| * argument. This bit set is modified so that a bit in it has the | |
| * value {@code true} if and only if it either already had the | |
| * value {@code true} or the corresponding bit in the bit set | |
| * argument has the value {@code true}. | |
| * | |
| * @param set a bit set | |
| */ | |
| public void or(BitSet set) { | |
| if (this == set) | |
| return; | |
| int wordsInCommon = Math.min(wordsInUse, set.wordsInUse); | |
| if (wordsInUse < set.wordsInUse) { | |
| ensureCapacity(set.wordsInUse); | |
| wordsInUse = set.wordsInUse; | |
| } | |
| // Perform logical OR on words in common | |
| for (int i = 0; i < wordsInCommon; i++) | |
| words[i] |= set.words[i]; | |
| // Copy any remaining words | |
| if (wordsInCommon < set.wordsInUse) | |
| System.arraycopy(set.words, wordsInCommon, | |
| words, wordsInCommon, | |
| wordsInUse - wordsInCommon); | |
| // recalculateWordsInUse() is unnecessary | |
| checkInvariants(); | |
| } | |
| /** | |
| * Performs a logical <b>XOR</b> of this bit set with the bit set | |
| * argument. This bit set is modified so that a bit in it has the | |
| * value {@code true} if and only if one of the following | |
| * statements holds: | |
| * <ul> | |
| * <li>The bit initially has the value {@code true}, and the | |
| * corresponding bit in the argument has the value {@code false}. | |
| * <li>The bit initially has the value {@code false}, and the | |
| * corresponding bit in the argument has the value {@code true}. | |
| * </ul> | |
| * | |
| * @param set a bit set | |
| */ | |
| public void xor(BitSet set) { | |
| int wordsInCommon = Math.min(wordsInUse, set.wordsInUse); | |
| if (wordsInUse < set.wordsInUse) { | |
| ensureCapacity(set.wordsInUse); | |
| wordsInUse = set.wordsInUse; | |
| } | |
| // Perform logical XOR on words in common | |
| for (int i = 0; i < wordsInCommon; i++) | |
| words[i] ^= set.words[i]; | |
| // Copy any remaining words | |
| if (wordsInCommon < set.wordsInUse) | |
| System.arraycopy(set.words, wordsInCommon, | |
| words, wordsInCommon, | |
| set.wordsInUse - wordsInCommon); | |
| recalculateWordsInUse(); | |
| checkInvariants(); | |
| } | |
| /** | |
| * Clears all of the bits in this {@code BitSet} whose corresponding | |
| * bit is set in the specified {@code BitSet}. | |
| * | |
| * @param set the {@code BitSet} with which to mask this | |
| * {@code BitSet} | |
| * @since 1.2 | |
| */ | |
| public void andNot(BitSet set) { | |
| // Perform logical (a & !b) on words in common | |
| for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--) | |
| words[i] &= ~set.words[i]; | |
| recalculateWordsInUse(); | |
| checkInvariants(); | |
| } | |
| /** | |
| * {@return the hash code value for this bit set} | |
| * | |
| * The hash code depends only on which bits are set within this | |
| * {@code BitSet}. | |
| * | |
| * <p>The hash code is defined to be the result of the following | |
| * calculation: | |
| * <pre> {@code | |
| * public int hashCode() { | |
| * long h = 1234; | |
| * long[] words = toLongArray(); | |
| * for (int i = words.length; --i >= 0; ) | |
| * h ^= words[i] * (i + 1); | |
| * return (int)((h >> 32) ^ h); | |
| * }}</pre> | |
| * Note that the hash code changes if the set of bits is altered. | |
| */ | |
| @Override | |
| public int hashCode() { | |
| long h = 1234; | |
| for (int i = wordsInUse; --i >= 0; ) | |
| h ^= words[i] * (i + 1); | |
| return (int)((h >> 32) ^ h); | |
| } | |
| /** | |
| * Returns the number of bits of space actually in use by this | |
| * {@code BitSet} to represent bit values. | |
| * The maximum element in the set is the size - 1st element. | |
| * | |
| * @return the number of bits currently in this bit set | |
| */ | |
| public int size() { | |
| return words.length * BITS_PER_WORD; | |
| } | |
| /** | |
| * Compares this bit set against the specified object. | |
| * The result is {@code true} if and only if the argument is | |
| * not {@code null} and is a {@code BitSet} object that has | |
| * exactly the same set of bits set to {@code true} as this bit | |
| * set. That is, for every nonnegative {@code int} index {@code k}, | |
| * <pre>((BitSet)obj).get(k) == this.get(k)</pre> | |
| * must be true. The current sizes of the two bit sets are not compared. | |
| * | |
| * @param obj the object to compare with | |
| * @return {@code true} if the objects are the same; | |
| * {@code false} otherwise | |
| * @see #size() | |
| */ | |
| @Override | |
| public boolean equals(Object obj) { | |
| if (this == obj) | |
| return true; | |
| if (!(obj instanceof BitSet set)) | |
| return false; | |
| checkInvariants(); | |
| set.checkInvariants(); | |
| if (wordsInUse != set.wordsInUse) | |
| return false; | |
| // Check words in use by both BitSets | |
| return ArraysSupport.mismatch(words, 0, set.words, 0, wordsInUse) == -1; | |
| } | |
| /** | |
| * Cloning this {@code BitSet} produces a new {@code BitSet} | |
| * that is equal to it. | |
| * The clone of the bit set is another bit set that has exactly the | |
| * same bits set to {@code true} as this bit set. | |
| * | |
| * @return a clone of this bit set | |
| * @see #size() | |
| */ | |
| public Object clone() { | |
| if (! sizeIsSticky) | |
| trimToSize(); | |
| try { | |
| BitSet result = (BitSet) super.clone(); | |
| result.words = words.clone(); | |
| result.checkInvariants(); | |
| return result; | |
| } catch (CloneNotSupportedException e) { | |
| throw new InternalError(e); | |
| } | |
| } | |
| /** | |
| * Attempts to reduce internal storage used for the bits in this bit set. | |
| * Calling this method may, but is not required to, affect the value | |
| * returned by a subsequent call to the {@link #size()} method. | |
| */ | |
| private void trimToSize() { | |
| if (wordsInUse != words.length) { | |
| words = Arrays.copyOf(words, wordsInUse); | |
| checkInvariants(); | |
| } | |
| } | |
| /** | |
| * Save the state of the {@code BitSet} instance to a stream (i.e., | |
| * serialize it). | |
| */ | |
| @java.io.Serial | |
| private void writeObject(ObjectOutputStream s) | |
| throws IOException { | |
| checkInvariants(); | |
| if (! sizeIsSticky) | |
| trimToSize(); | |
| ObjectOutputStream.PutField fields = s.putFields(); | |
| fields.put("bits", words); | |
| s.writeFields(); | |
| } | |
| /** | |
| * Reconstitute the {@code BitSet} instance from a stream (i.e., | |
| * deserialize it). | |
| */ | |
| @java.io.Serial | |
| private void readObject(ObjectInputStream s) | |
| throws IOException, ClassNotFoundException { | |
| ObjectInputStream.GetField fields = s.readFields(); | |
| words = (long[]) fields.get("bits", null); | |
| // Assume maximum length then find real length | |
| // because recalculateWordsInUse assumes maintenance | |
| // or reduction in logical size | |
| wordsInUse = words.length; | |
| recalculateWordsInUse(); | |
| sizeIsSticky = (words.length > 0 && words[words.length-1] == 0L); // heuristic | |
| checkInvariants(); | |
| } | |
| /** | |
| * Returns a string representation of this bit set. For every index | |
| * for which this {@code BitSet} contains a bit in the set | |
| * state, the decimal representation of that index is included in | |
| * the result. Such indices are listed in order from lowest to | |
| * highest, separated by ", " (a comma and a space) and | |
| * surrounded by braces, resulting in the usual mathematical | |
| * notation for a set of integers. | |
| * | |
| * <p>Example: | |
| * <pre> | |
| * BitSet drPepper = new BitSet();</pre> | |
| * Now {@code drPepper.toString()} returns "{@code {}}". | |
| * <pre> | |
| * drPepper.set(2);</pre> | |
| * Now {@code drPepper.toString()} returns "{@code {2}}". | |
| * <pre> | |
| * drPepper.set(4); | |
| * drPepper.set(10);</pre> | |
| * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}". | |
| * | |
| * @return a string representation of this bit set | |
| */ | |
| public String toString() { | |
| checkInvariants(); | |
| final int MAX_INITIAL_CAPACITY = ArraysSupport.SOFT_MAX_ARRAY_LENGTH; | |
| int numBits = (wordsInUse > 128) ? | |
| cardinality() : wordsInUse * BITS_PER_WORD; | |
| // Avoid overflow in the case of a humongous numBits | |
| int initialCapacity = (numBits <= (MAX_INITIAL_CAPACITY - 2) / 6) ? | |
| 6 * numBits + 2 : MAX_INITIAL_CAPACITY; | |
| StringBuilder b = new StringBuilder(initialCapacity); | |
| b.append('{'); | |
| int i = nextSetBit(0); | |
| if (i != -1) { | |
| b.append(i); | |
| while (true) { | |
| if (++i < 0) break; | |
| if ((i = nextSetBit(i)) < 0) break; | |
| int endOfRun = nextClearBit(i); | |
| do { b.append(", ").append(i); } | |
| while (++i != endOfRun); | |
| } | |
| } | |
| b.append('}'); | |
| return b.toString(); | |
| } | |
| /** | |
| * Returns a stream of indices for which this {@code BitSet} | |
| * contains a bit in the set state. The indices are returned | |
| * in order, from lowest to highest. The size of the stream | |
| * is the number of bits in the set state, equal to the value | |
| * returned by the {@link #cardinality()} method. | |
| * | |
| * <p>The stream binds to this bit set when the terminal stream operation | |
| * commences (specifically, the spliterator for the stream is | |
| * <a href="Spliterator.html#binding"><em>late-binding</em></a>). If the | |
| * bit set is modified during that operation then the result is undefined. | |
| * | |
| * @return a stream of integers representing set indices | |
| * @since 1.8 | |
| */ | |
| public IntStream stream() { | |
| class BitSetSpliterator implements Spliterator.OfInt { | |
| private int index; // current bit index for a set bit | |
| private int fence; // -1 until used; then one past last bit index | |
| private int est; // size estimate | |
| private boolean root; // true if root and not split | |
| // root == true then size estimate is accurate | |
| // index == -1 or index >= fence if fully traversed | |
| // Special case when the max bit set is Integer.MAX_VALUE | |
| BitSetSpliterator(int origin, int fence, int est, boolean root) { | |
| this.index = origin; | |
| this.fence = fence; | |
| this.est = est; | |
| this.root = root; | |
| } | |
| private int getFence() { | |
| int hi; | |
| if ((hi = fence) < 0) { | |
| // Round up fence to maximum cardinality for allocated words | |
| // This is sufficient and cheap for sequential access | |
| // When splitting this value is lowered | |
| hi = fence = (wordsInUse >= wordIndex(Integer.MAX_VALUE)) | |
| ? Integer.MAX_VALUE | |
| : wordsInUse << ADDRESS_BITS_PER_WORD; | |
| est = cardinality(); | |
| index = nextSetBit(0); | |
| } | |
| return hi; | |
| } | |
| @Override | |
| public boolean tryAdvance(IntConsumer action) { | |
| Objects.requireNonNull(action); | |
| int hi = getFence(); | |
| int i = index; | |
| if (i < 0 || i >= hi) { | |
| // Check if there is a final bit set for Integer.MAX_VALUE | |
| if (i == Integer.MAX_VALUE && hi == Integer.MAX_VALUE) { | |
| index = -1; | |
| action.accept(Integer.MAX_VALUE); | |
| return true; | |
| } | |
| return false; | |
| } | |
| index = nextSetBit(i + 1, wordIndex(hi - 1)); | |
| action.accept(i); | |
| return true; | |
| } | |
| @Override | |
| public void forEachRemaining(IntConsumer action) { | |
| Objects.requireNonNull(action); | |
| int hi = getFence(); | |
| int i = index; | |
| index = -1; | |
| if (i >= 0 && i < hi) { | |
| action.accept(i++); | |
| int u = wordIndex(i); // next lower word bound | |
| int v = wordIndex(hi - 1); // upper word bound | |
| words_loop: | |
| for (; u <= v && i <= hi; u++, i = u << ADDRESS_BITS_PER_WORD) { | |
| long word = words[u] & (WORD_MASK << i); | |
| while (word != 0) { | |
| i = (u << ADDRESS_BITS_PER_WORD) + Long.numberOfTrailingZeros(word); | |
| if (i >= hi) { | |
| // Break out of outer loop to ensure check of | |
| // Integer.MAX_VALUE bit set | |
| break words_loop; | |
| } | |
| // Flip the set bit | |
| word &= ~(1L << i); | |
| action.accept(i); | |
| } | |
| } | |
| } | |
| // Check if there is a final bit set for Integer.MAX_VALUE | |
| if (i == Integer.MAX_VALUE && hi == Integer.MAX_VALUE) { | |
| action.accept(Integer.MAX_VALUE); | |
| } | |
| } | |
| @Override | |
| public OfInt trySplit() { | |
| int hi = getFence(); | |
| int lo = index; | |
| if (lo < 0) { | |
| return null; | |
| } | |
| // Lower the fence to be the upper bound of last bit set | |
| // The index is the first bit set, thus this spliterator | |
| // covers one bit and cannot be split, or two or more | |
| // bits | |
| hi = fence = (hi < Integer.MAX_VALUE || !get(Integer.MAX_VALUE)) | |
| ? previousSetBit(hi - 1) + 1 | |
| : Integer.MAX_VALUE; | |
| // Find the mid point | |
| int mid = (lo + hi) >>> 1; | |
| if (lo >= mid) { | |
| return null; | |
| } | |
| // Raise the index of this spliterator to be the next set bit | |
| // from the mid point | |
| index = nextSetBit(mid, wordIndex(hi - 1)); | |
| root = false; | |
| // Don't lower the fence (mid point) of the returned spliterator, | |
| // traversal or further splitting will do that work | |
| return new BitSetSpliterator(lo, mid, est >>>= 1, false); | |
| } | |
| @Override | |
| public long estimateSize() { | |
| getFence(); // force init | |
| return est; | |
| } | |
| @Override | |
| public int characteristics() { | |
| // Only sized when root and not split | |
| return (root ? Spliterator.SIZED : 0) | | |
| Spliterator.ORDERED | Spliterator.DISTINCT | Spliterator.SORTED; | |
| } | |
| @Override | |
| public Comparator<? super Integer> getComparator() { | |
| return null; | |
| } | |
| } | |
| return StreamSupport.intStream(new BitSetSpliterator(0, -1, 0, true), false); | |
| } | |
| /** | |
| * Returns the index of the first bit that is set to {@code true} | |
| * that occurs on or after the specified starting index and up to and | |
| * including the specified word index | |
| * If no such bit exists then {@code -1} is returned. | |
| * | |
| * @param fromIndex the index to start checking from (inclusive) | |
| * @param toWordIndex the last word index to check (inclusive) | |
| * @return the index of the next set bit, or {@code -1} if there | |
| * is no such bit | |
| */ | |
| private int nextSetBit(int fromIndex, int toWordIndex) { | |
| int u = wordIndex(fromIndex); | |
| // Check if out of bounds | |
| if (u > toWordIndex) | |
| return -1; | |
| long word = words[u] & (WORD_MASK << fromIndex); | |
| while (true) { | |
| if (word != 0) | |
| return (u * BITS_PER_WORD) + Long.numberOfTrailingZeros(word); | |
| // Check if out of bounds | |
| if (++u > toWordIndex) | |
| return -1; | |
| word = words[u]; | |
| } | |
| } | |
| } |