public ByteKey interpolateKey(double fraction) {
    checkArgument(
        fraction >= 0.0 && fraction < 1.0, "Fraction %s must be in the range [0, 1)", fraction);
    byte[] startBytes = startKey.getBytes();
    byte[] endBytes = endKey.getBytes();
    // If the endKey is unspecified, add a leading 1 byte to it and a leading 0 byte to all other
    // keys, to get a concrete least upper bound for the desired range.
    if (endKey.isEmpty()) {
      startBytes = addHeadByte(startBytes, (byte) 0);
      endBytes = addHeadByte(endBytes, (byte) 1);
    }

    // Pad to the longest key.
    int paddedKeyLength = Math.max(startBytes.length, endBytes.length);
    BigInteger rangeStartInt = paddedPositiveInt(startBytes, paddedKeyLength);
    BigInteger rangeEndInt = paddedPositiveInt(endBytes, paddedKeyLength);

    // If the keys are equal subject to padding by 0, we can't interpolate.
    BigInteger range = rangeEndInt.subtract(rangeStartInt);
    checkState(
        !range.equals(BigInteger.ZERO),
        "Refusing to interpolate for near-empty %s where start and end keys differ only by trailing"
            + " zero bytes.",
        this);

    // Add precision so that range is at least 53 (double mantissa length) bits long. This way, we
    // can interpolate small ranges finely, e.g., split the range key 3 to key 4 into 1024 parts.
    // We add precision to range by adding zero bytes to the end of the keys, aka shifting the
    // underlying BigInteger left by a multiple of 8 bits.
    int bytesNeeded = ((53 - range.bitLength()) + 7) / 8;
    if (bytesNeeded > 0) {
      range = range.shiftLeft(bytesNeeded * 8);
      rangeStartInt = rangeStartInt.shiftLeft(bytesNeeded * 8);
      paddedKeyLength += bytesNeeded;
    }

    BigInteger interpolatedOffset =
        new BigDecimal(range).multiply(BigDecimal.valueOf(fraction)).toBigInteger();

    int outputKeyLength = endKey.isEmpty() ? (paddedKeyLength - 1) : paddedKeyLength;
    return ByteKey.copyFrom(
        fixupHeadZeros(rangeStartInt.add(interpolatedOffset).toByteArray(), outputKeyLength));
  }
@Test
  public void testInterpolateKey() {
    /* 0x80 is halfway between [] and [] */
    assertEqualExceptPadding(ByteKey.of(0x80), ByteKeyRange.ALL_KEYS.interpolateKey(0.5));

    /* 0x80 is halfway between [00] and [] */
    ByteKeyRange after0 = ByteKeyRange.of(ByteKey.of(0), ByteKey.EMPTY);
    assertEqualExceptPadding(ByteKey.of(0x80), after0.interpolateKey(0.5));

    /* 0x80 is halfway between [0000] and [] -- padding to longest key */
    ByteKeyRange after00 = ByteKeyRange.of(ByteKey.of(0, 0), ByteKey.EMPTY);
    assertEqualExceptPadding(ByteKey.of(0x80), after00.interpolateKey(0.5));

    /* 0x7f is halfway between [] and [fe] */
    ByteKeyRange upToFE = ByteKeyRange.of(ByteKey.EMPTY, ByteKey.of(0xfe));
    assertEqualExceptPadding(ByteKey.of(0x7f), upToFE.interpolateKey(0.5));

    /* 0x40 is one-quarter of the way between [] and [] */
    assertEqualExceptPadding(ByteKey.of(0x40), ByteKeyRange.ALL_KEYS.interpolateKey(0.25));

    /* 0x40 is halfway between [] and [0x80] */
    ByteKeyRange upTo80 = ByteKeyRange.of(ByteKey.EMPTY, ByteKey.of(0x80));
    assertEqualExceptPadding(ByteKey.of(0x40), upTo80.interpolateKey(0.5));

    /* 0x40 is halfway between [0x30] and [0x50] */
    ByteKeyRange range30to50 = ByteKeyRange.of(ByteKey.of(0x30), ByteKey.of(0x50));
    assertEqualExceptPadding(ByteKey.of(0x40), range30to50.interpolateKey(0.5));

    /* 0x40 is halfway between [0x30, 0, 1] and [0x4f, 0xff, 0xff, 0, 0]  */
    ByteKeyRange range31to4f =
        ByteKeyRange.of(ByteKey.of(0x30, 0, 1), ByteKey.of(0x4f, 0xff, 0xff, 0, 0));
    assertEqualExceptPadding(ByteKey.of(0x40), range31to4f.interpolateKey(0.5));
  }