/*
 * Copyright 2009 Google Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */

package java.util;

import static javaemul.internal.Coercions.ensureInt;
import static javaemul.internal.InternalPreconditions.checkArraySize;

import javaemul.internal.ArrayHelper;

/**
 * This implementation uses a dense array holding bit groups of size 31 to keep track of when bits
 * are set to true or false. Using 31 bits keeps our implementation within the range of V8's
 * "tagged small integer" and improves performance. Using a dense array also makes access faster on
 * V8.
 *
 * Not yet implemented:
 * public static BitSet valueOf(ByteBuffer)
 * public static BitSet valueOf(LongBuffer)
 */
public class BitSet {
  private static final int WORD_MASK = 0x7fffffff;
  private static final int BITS_PER_WORD = 31;

  private final int[] array;

  public BitSet() {
    array = new int[0];
  }

  public BitSet(int nbits) {
    checkArraySize(nbits);
    int length = wordIndex(nbits - 1) + 1;
    array = new int[0];
    ArrayHelper.setLength(array, length);
  }

  private BitSet(int[] array) {
    this.array = array;
  }

  private static void checkIndex(int bitIndex) {
    if (bitIndex < 0) {
      throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
    }
  }

  private static void checkRange(int fromIndex, int toIndex) {
    if (fromIndex < 0 || toIndex < 0 || fromIndex > toIndex) {
      throw new IndexOutOfBoundsException("fromIndex: " + fromIndex + ", toIndex: " + toIndex);
    }
  }

  /**
   * Converts from a bit index to a word index.
   *
   * @param bitIndex The bit index.
   * @return The index of the word (array entry) holding that bit.
   */
  private static int wordIndex(int bitIndex) {
    return bitIndex / BITS_PER_WORD;
  }

  /**
   * Converts from a word index to the lowest index of the bit stored in that word.
   *
   * @param wordIndex The word index.
   * @return The lowest index of the bit stored in that word.
   */
  private static int bitIndex(int wordIndex) {
    return wordIndex * BITS_PER_WORD;
  }

  /**
   * Computes the offset within a word for a bit index. Within a word, the offset counts from
   * right to left and caps at 31. This helps leaving the highest bit as zero to ensure that
   * each word is a tagged small integer in V8.
   *
   * @param bitIndex The bit index.
   * @return The offset of the bit within a word, counting from right to left.
   */
  private static int bitOffset(int bitIndex) {
    return bitIndex % BITS_PER_WORD;
  }

  /**
   * Sets all bits to true within the given range.
   *
   * @param fromIndex The lower bit index.
   * @param toIndex The upper bit index.
   */
  private static void setInternal(int[] array, int fromIndex, int toIndex) {
    int first = wordIndex(fromIndex);
    int last = wordIndex(toIndex);

    maybeGrowArrayToIndex(array, last);

    int startBit = bitOffset(fromIndex);
    int endBit = bitOffset(toIndex);

    if (first == last) {
      // Set the bits in between first and last.
      maskInWord(array, first, startBit, endBit);
    } else {
      // Set the bits from fromIndex to the next 31 bit boundary.
      maskInWord(array, first, startBit, BITS_PER_WORD);

      // Set the bits from the last 31 bit boundary to toIndex.
      maskInWord(array, last, 0, endBit);

      // Set everything in between.
      for (int i = first + 1; i < last; i++) {
        array[i] = WORD_MASK;
      }
    }
  }

  private static void maybeGrowArrayToIndex(int[] array, int newMaxIndex) {
    // TODO: This code has a potential problem:
    // If we grow the array more than 1024 places the array will degenerate into a map,
    // we can work around this by adding 0 to the arrays.
    int newLength = newMaxIndex + 1;
    if (newLength > array.length) {
      ArrayHelper.setLength(array, newLength);
    }
  }

  /**
   * Returns the index of the last word containing a true bit in an array, or -1 if none.
   *
   * @param array The array.
   * @return The index of the last word containing a true bit, or -1 if none.
   */
  private static int lastSetWordIndex(int[] array) {
    int i = array.length - 1;
    for (; i >= 0 && wordAt(array, i) == 0; --i) { }
    return i;
  }

  /**
   * Flips all bits in a word within the given range.
   *
   * @param array The array.
   * @param index The word index.
   * @param from The lower bit index.
   * @param to The upper bit index.
   */
  private static void flipMaskedWord(int[] array, int index, int from, int to) {
    if (from == to) {
      return;
    }

    to = 32 - to;
    int word = wordAt(array, index);
    word ^= ((0xffffffff >>> from) << (from + to)) >>> to;
    array[index] = word & WORD_MASK;
  }

  /**
   * Sets all bits to true in a word within the given bit range.
   *
   * @param array The array.
   * @param index The word index.
   * @param from The lower bit index.
   * @param to The upper bit index.
   */
  private static void maskInWord(int[] array, int index, int from, int to) {
    if (from == to) {
      return;
    }

    to = 32 - to;
    int word = wordAt(array, index);
    word |= ((0xffffffff >>> from) << (from + to)) >>> to;
    array[index] = word & WORD_MASK;
  }

  /**
   * Sets all bits to false in a word within the given bit range.
   *
   * @param array The array.
   * @param index The word index.
   * @param from The lower bit index.
   * @param to The upper bit index.
   */
  private static void maskOutWord(int[] array, int index, int from, int to) {
    if (from == to) {
      return;
    }

    int word = wordAt(array, index);
    if (word == 0) {
      return;
    }

    int mask;
    if (from != 0) {
      mask = 0xffffffff >>> (32 - from);
    } else {
      mask = 0;
    }
    // Shifting by 32 is the same as shifting by 0.
    if (to != 32) {
      mask |= 0xffffffff << to;
    }

    word &= mask;
    array[index] = word & WORD_MASK;
  }

  private static int wordAt(int[] array, int index) {
    return ensureInt(array[index]);
  }

  // GWT emulates integer with double and doesn't overflow. Enfore it by a integer mask.
  private static int enforceOverflow(int value) {
    return value & 0xffffffff;
  }

  public void and(BitSet set) {
    // a & a is just a.
    if (this == set) {
      return;
    }

    // Truth table
    //
    // Case | a     | b     | a & b | Change?
    // 1    | false | false | false | a is already false
    // 2    | false | true  | false | a is already false
    // 3    | true  | false | false | set a to false
    // 4    | true  | true  | true  | a is already true
    //
    // We only need to change something in case 3, so iterate over set a.
    int limit = Math.min(array.length, set.array.length);
    int index = 0;
    for (; index < limit; index++) {
      int word = wordAt(array, index);
      if (word != 0) {
        array[index] = word & wordAt(set.array, index);
      }
    }
    Arrays.fill(array, index, array.length, 0);
  }

  public void andNot(BitSet set) {
    // a & !a is false, and all falses result in an empty BitSet.
    if (this == set) {
      clear();
      return;
    }

    // Truth table
    //
    // Case | a     | b     | !b    | a & !b | Change?
    // 1    | false | false | true  | false  | a is already false
    // 2    | false | true  | false | false  | a is already false
    // 3    | true  | false | true  | true   | a is already true
    // 4    | true  | true  | false | false  | set a to false
    //
    // We only need to change something in case 4. Whenever b is true, a should be false, so
    // iterate over set b.
    int limit = Math.min(array.length, set.array.length);
    for (int index = 0; index < limit; index++) {
      int otherWord = wordAt(set.array, index);
      if (otherWord != 0) {
        int word = wordAt(array, index);
        if (word != 0) {
          array[index] = word & (~otherWord & WORD_MASK);
        }
      }
    }
  }

  public int cardinality() {
    int count = 0;
    for (int i = 0; i < array.length; i++) {
      count += Integer.bitCount(wordAt(array, i));
    }
    return count;
  }

  public void clear() {
    ArrayHelper.setLength(array, 0);
  }

  public void clear(int bitIndex) {
    checkIndex(bitIndex);

    int index = wordIndex(bitIndex);
    if (index >= array.length) {
      return;
    }

    int word = wordAt(array, index);
    if (word != 0) {
      array[index] = word & ~(1 << bitOffset(bitIndex)) & WORD_MASK;
    }
  }

  public void clear(int fromIndex, int toIndex) {
    checkRange(fromIndex, toIndex);

    if (fromIndex == toIndex) {
      return;
    }

    int first = wordIndex(fromIndex);
    if (first >= array.length) {
      return;
    }

    int last = wordIndex(toIndex);
    if (last >= array.length) {
      toIndex = length();
      last = wordIndex(toIndex);
    }

    int startBit = bitOffset(fromIndex);
    int endBit = bitOffset(toIndex);

    if (first == last) {
      // Clear the bits in between first and last.
      maskOutWord(array, first, startBit, endBit);
    } else {
      // Clear the bits from fromIndex to the next 31 bit boundary.
      maskOutWord(array, first, startBit, BITS_PER_WORD);

      // Clear the bits from the last 31 bit boundary to the toIndex.
      maskOutWord(array, last, 0, endBit);

      Arrays.fill(array, first + 1, last, 0);
    }
  }

  public Object clone() {
    return new BitSet(Arrays.copyOf(array, array.length));
  }

  @Override
  public boolean equals(Object obj) {
    if (this == obj) {
      return true;
    }

    if (!(obj instanceof BitSet)) {
      return false;
    }

    BitSet other = (BitSet) obj;

    int lastIndex = lastSetWordIndex(array);
    if (lastIndex != lastSetWordIndex(other.array)) {
      return false;
    }

    for (int index = 0; index <= lastIndex; index++) {
      if (wordAt(array, index) != wordAt(other.array, index)) {
        return false;
      }
    }
    return true;
  }

  public void flip(int bitIndex) {
    checkIndex(bitIndex);

    int index = wordIndex(bitIndex);
    int offset = bitOffset(bitIndex);

    maybeGrowArrayToIndex(array, index);

    int word = wordAt(array, index);
    if (((word >>> offset) & 1) == 1) {
      word = word & ~(1 << offset);
    } else {
      word = (word | (1 << offset));
    }
    array[index] = word & WORD_MASK;
  }

  public void flip(int fromIndex, int toIndex) {
    checkRange(fromIndex, toIndex);

    if (fromIndex == toIndex) {
      return;
    }

    // If we are flipping bits beyond our length, we are setting them to true.
    int length = length();
    if (fromIndex >= length) {
      setInternal(array, fromIndex, toIndex);
      return;
    }

    if (toIndex >= length) {
      setInternal(array, length, toIndex);
      toIndex = length;
    }

    int first = wordIndex(fromIndex);
    int last = wordIndex(toIndex);
    int startBit = bitOffset(fromIndex);
    int endBit = bitOffset(toIndex);

    if (first == last) {
      // Flip the bits in between first and last.
      flipMaskedWord(array, first, startBit, endBit);

    } else {
      // Flip the bits from fromIndex to the next 31 bit boundary.
      flipMaskedWord(array, first, startBit, BITS_PER_WORD);

      // Flip the bits from the last 31 bit boundary to the toIndex.
      flipMaskedWord(array, last, 0, endBit);

      // Flip everything in between.
      for (int i = first + 1; i < last; i++) {
        array[i] = ~wordAt(array, i) & WORD_MASK;
      }
    }
  }

  public boolean get(int bitIndex) {
    checkIndex(bitIndex);

    int index = wordIndex(bitIndex);
    // Shift and mask the bit out
    return index < array.length && ((wordAt(array, index) >>> bitOffset(bitIndex)) & 1) == 1;
  }

  public BitSet get(int fromIndex, int toIndex) {
    checkRange(fromIndex, toIndex);

    int length = length();
    if (length <= fromIndex || fromIndex == toIndex) {
      return new BitSet(0);
    }

    toIndex = Math.min(toIndex, length);

    // The bit shift offset for each group of bits
    int rightShift = bitOffset(fromIndex);

    if (rightShift == 0) {
      int subFrom = wordIndex(fromIndex);
      int subTo = wordIndex(toIndex + BITS_PER_WORD);
      int[] subArray = Arrays.copyOfRange(array, subFrom, subTo);
      int leftOvers = bitOffset(toIndex);
      maskOutWord(subArray, subTo - subFrom - 1, leftOvers, BITS_PER_WORD);
      return new BitSet(subArray);
    }

    int first = wordIndex(fromIndex);
    int last = wordIndex(toIndex);

    int[] subArray = new int[last - first + 1];
    if (first == last) {
      // Number of bits to cut from the end
      int end = 32 - bitOffset(toIndex);
      int word = wordAt(array, first);
      subArray[0] = (word << end) >>> (rightShift + end);
    } else {
      // Fence post, carry over initial bits.
      int word = wordAt(array, first);

      // This holds the newly packed bits.
      int current = word >>> rightShift;

      // The raw index into the subset
      int subIndex = 0;

      // A left shift will be used to shift our bits to the top of "current".
      int leftShift = BITS_PER_WORD - rightShift;

      // Loop through everything in the middle.
      for (int i = first + 1; i <= last; i++) {
        word = wordAt(array, i);

        // Shift out the bits from the top, OR them into current bits.
        current |= word << leftShift;
        subArray[subIndex++] = current & WORD_MASK;

        // Carry over the unused bits.
        current = word >>> rightShift;
      }

      // Fence post, flush out the extra bits, but don't go past the "end".
      int end = 32 - bitOffset(toIndex);
      current = (current << (rightShift + end)) >>> (rightShift + end);
      subArray[subIndex] = current & WORD_MASK;
    }

    return new BitSet(subArray);
  }

  /**
   * This hash is different than the one described in Sun's documentation. The
   * described hash uses 64 bit integers and that's not practical in JavaScript.
   */
  @Override
  public int hashCode() {
    // FNV constants
    final int fnvOffset = 0x811c9dc5;
    final int fnvPrime = 0x1000193;

    final int lastIndex = lastSetWordIndex(array);
    int hash = fnvOffset ^ lastIndex;

    for (int i = 0; i <= lastIndex; i++) {
      int value = wordAt(array, i);
      // Hash one byte at a time using FNV1 and make sure we don't overflow 32 bit int.
      hash = enforceOverflow(hash * fnvPrime) ^ (value & 0xff);
      hash = enforceOverflow(hash * fnvPrime) ^ ((value >>> 8) & 0xff);
      hash = enforceOverflow(hash * fnvPrime) ^ ((value >>> 16) & 0xff);
      hash = enforceOverflow(hash * fnvPrime) ^ (value >>> 24);
    }

    return hash;
  }

  public boolean intersects(BitSet set) {
    if (this == set) {
      // If it has any set bits then it intersects itself.
      return length() > 0;
    }

    int limit = Math.min(array.length, set.array.length);
    for (int index = 0; index < limit; index++) {
      int word = wordAt(array, index);
      if (word != 0 && (word & wordAt(set.array, index)) != 0) {
        return true;
      }
    }
    return false;
  }

  public boolean isEmpty() {
    return length() == 0;
  }

  public int length() {
    int lastIndex = lastSetWordIndex(array);
    if (lastIndex == -1) {
      return 0;
    }

    // Compute the bit index of the leftmost bit.
    int word = wordAt(array, lastIndex);
    return bitIndex(lastIndex) + (32 - Integer.numberOfLeadingZeros(word));
  }

  public int nextClearBit(int fromIndex) {
    checkIndex(fromIndex);

    int index = wordIndex(fromIndex);
    int length = array.length;
    if (index >= length) {
      return fromIndex;
    }

    // Special case for the first word.
    int word = ~wordAt(array, index) & WORD_MASK;
    word &= (WORD_MASK << bitOffset(fromIndex));
    while (word == 0) {
      if (++index >= length) {
        return bitIndex(index);
      }
      word = ~wordAt(array, index) & WORD_MASK;
    }
    return bitIndex(index) + Integer.numberOfTrailingZeros(word);
  }

  public int nextSetBit(int fromIndex) {
    checkIndex(fromIndex);

    int index = wordIndex(fromIndex);
    int length = array.length;
    if (index >= length) {
      return -1;
    }

    // Special case for the first word.
    int word = wordAt(array, index) & (WORD_MASK << bitOffset(fromIndex));
    while (word == 0) {
      if (++index >= length) {
        return -1;
      }
      word = wordAt(array, index);
    }
    return bitIndex(index) + Integer.numberOfTrailingZeros(word);
  }

  public int previousClearBit(int fromIndex) {
    if (fromIndex == -1) {
      return -1;
    }
    checkIndex(fromIndex);

    int index = wordIndex(fromIndex);
    if (index >= array.length) {
      return fromIndex;
    }

    // Special case for the first word.
    int word = ~wordAt(array, index) & WORD_MASK;
    word &= (WORD_MASK >>> (BITS_PER_WORD - bitOffset(fromIndex) - 1));
    while (word == 0) {
      if (--index < 0) {
        return -1;
      }
      word = ~wordAt(array, index) & WORD_MASK;
    }
    return bitIndex(index) + (32 - Integer.numberOfLeadingZeros(word)) - 1;
  }

  public int previousSetBit(int fromIndex) {
    if (fromIndex == -1) {
      return -1;
    }
    checkIndex(fromIndex);

    int index = wordIndex(fromIndex);
    if (index >= array.length) {
      return length() - 1;
    }

    // Special case for the first word.
    int word = wordAt(array, index) & (WORD_MASK >>> (BITS_PER_WORD - bitOffset(fromIndex) - 1));
    while (word == 0) {
      if (--index < 0) {
        return -1;
      }
      word = wordAt(array, index);
    }
    return bitIndex(index) + (32 - Integer.numberOfLeadingZeros(word)) - 1;
  }

  public void or(BitSet set) {
    // a | a is just a.
    if (this == set) {
      return;
    }

    maybeGrowArrayToIndex(array, set.array.length - 1);

    // Truth table
    //
    // Case | a     | b     | a | b | Change?
    // 1    | false | false | false | a is already false
    // 2    | false | true  | true  | set a to true
    // 3    | true  | false | true  | a is already true
    // 4    | true  | true  | true  | a is already true
    //
    // We only need to change something in case 2. Case 2 only happens when b is true, so iterate
    // over set b
    for (int index = 0; index < set.array.length; index++) {
      int word = wordAt(set.array, index);
      if (word != 0) {
        array[index] = wordAt(array, index) | word;
      }
    }
  }

  public void set(int bitIndex) {
    checkIndex(bitIndex);
    int index = wordIndex(bitIndex);
    maybeGrowArrayToIndex(array, index);
    array[index] = wordAt(array, index) | (1 << bitOffset(bitIndex));
  }

  public void set(int bitIndex, boolean value) {
    if (value) {
      set(bitIndex);
    } else {
      clear(bitIndex);
    }
  }

  public void set(int fromIndex, int toIndex) {
    checkRange(fromIndex, toIndex);
    if (fromIndex != toIndex) {
      setInternal(array, fromIndex, toIndex);
    }
  }

  public void set(int fromIndex, int toIndex, boolean value) {
    if (value) {
      set(fromIndex, toIndex);
    } else {
      clear(fromIndex, toIndex);
    }
  }

  public int size() {
    return array.length * 32;
  }

  @Override
  public String toString() {
    if (isEmpty()) {
      return "{}";
    }

    StringBuilder sb = new StringBuilder("{");
    int next = nextSetBit(0);
    sb.append(next);

    while ((next = nextSetBit(next + 1)) != -1) {
      sb.append(", ");
      sb.append(next);
    }

    sb.append("}");
    return sb.toString();
  }

  public void xor(BitSet set) {
    // a ^ a is all false, so return an empty BitSet.
    if (this == set) {
      clear();
      return;
    }

    maybeGrowArrayToIndex(array, set.array.length - 1);

    // Truth table
    //
    // Case | a     | b     | a ^ b | Change?
    // 1    | false | false | false | a is already false
    // 2    | false | true  | true  | set a to true
    // 3    | true  | false | true  | a is already true
    // 4    | true  | true  | false | set a to false
    //
    // We need to change something in cases 2 and 4. Cases 2 and 4 only happen when b is true,
    // so iterate over set b.
    for (int index = 0; index < set.array.length; index++) {
      int word = wordAt(set.array, index);
      if (word != 0) {
        array[index] = wordAt(array, index) ^ word;
      }
    }
  }

  public byte[] toByteArray() {
    int nbits = length();
    int nbytes = nbits / Byte.SIZE;
    if (nbits % Byte.SIZE != 0) {
      nbytes++;
    }
    byte[] bytes = new byte[nbytes];
    int bitOffset = 0;
    for (int i = 0; i < nbytes; i++) {
      bytes[i] = getByte(array, bitOffset);
      bitOffset += Byte.SIZE;
    }
    return bytes;
  }

  public long[] toLongArray() {
    int nbits = length();
    int nlongs = nbits / Long.SIZE;
    if (nbits % Long.SIZE != 0) {
      nlongs++;
    }
    long[] longs = new long[nlongs];
    int bitOffset = 0;
    for (int i = 0; i < nlongs; i++) {
      longs[i] = getLong(array, bitOffset);
      bitOffset += Long.SIZE;
    }
    return longs;
  }

  private static byte getByte(int[] words, int bitIndex) {
    int wordIndex = wordIndex(bitIndex);
    if (wordIndex >= words.length) {
      return 0;
    }
    int bitOffset = bitOffset(bitIndex);
    int word = wordAt(words, wordIndex);
    int b = (word >>> bitOffset);
    int leftBits = Byte.SIZE - BITS_PER_WORD + bitOffset;
    if (leftBits > 0 && wordIndex + 1 < words.length) {
      word = wordAt(words, wordIndex + 1);
      if (word != 0) {
        word &= ~(WORD_MASK << leftBits);
        word <<= (Byte.SIZE - leftBits);
        b |= word;
      }
    }
    return (byte) (b & 0xff);
  }

  private static int getInt(int[] words, int bitIndex) {
    byte b1 = getByte(words, bitIndex);
    byte b2 = getByte(words, bitIndex + 8);
    byte b3 = getByte(words, bitIndex + 16);
    byte b4 = getByte(words, bitIndex + 24);
    return (b1 & 0xff) | ((b2 & 0xff) << 8) | ((b3 & 0xff) << 16) | ((b4 & 0xff) << 24);
  }

  private static long getLong(int[] words, int bitIndex) {
    int low = getInt(words, bitIndex);
    int high = getInt(words, bitIndex + 32);
    return ((long) high << 32) | (low & 0xffff_ffffL);
  }

  public static BitSet valueOf(byte[] words) {
    int len = words.length;
    while (len > 0 && words[len - 1] == 0) {
      len--;
    }
    int[] array = new int[len * Byte.SIZE];
    int bitIndex = 0;
    for (int i = 0; i < len; i++) {
      addByte(array, words[i], bitIndex);
      bitIndex += Byte.SIZE;
    }
    return new BitSet(array);
  }

  public static BitSet valueOf(long[] words) {
    int len = words.length;
    while (len > 0 && words[len - 1] == 0) {
      len--;
    }
    int[] array = new int[len * Long.SIZE];
    int bitIndex = 0;
    for (int i = 0; i < len; i++) {
      addLong(array, words[i], bitIndex);
      bitIndex += Long.SIZE;
    }
    return new BitSet(array);
  }

  private static void addByte(int[] words, byte bits, int bitIndex) {
    if (bits != 0) {
      int wordIndex = wordIndex(bitIndex);
      int bitOffset = bitOffset(bitIndex);
      int first = ((bits & 0xff) << bitOffset) & WORD_MASK;
      if (first != 0) {
        words[wordIndex] = wordAt(words, wordIndex) | first;
      }
      int second = bitOffset == 0 ? 0 : (bits & 0xff) >>> (BITS_PER_WORD - bitOffset);
      if (second != 0) {
        words[wordIndex + 1] = wordAt(words, wordIndex + 1) | second;
      }
    }
  }

  private static void addInt(int[] words, int bits, int bitIndex) {
    if (bits != 0) {
      addByte(words, (byte) (bits & 0xff), bitIndex);
      addByte(words, (byte) ((bits >> 8) & 0xff), bitIndex + Byte.SIZE);
      addByte(words, (byte) ((bits >> 16) & 0xff), bitIndex + 2 * Byte.SIZE);
      addByte(words, (byte) ((bits >> 24) & 0xff), bitIndex + 3 * Byte.SIZE);
    }
  }

  private static void addLong(int[] words, long bits, int bitIndex) {
    if (bits != 0) {
      int low = (int) bits;
      addInt(words, low, bitIndex);
      int high = (int) (bits >>> 32);
      addInt(words, high, bitIndex + Integer.SIZE);
    }
  }
}