Могу ли я создать битовую маску размером от 1 до 64 бит без условия в Java?

Question

Я хочу написать функцию, которая принимает значение типа int в диапазоне от 1 до 64 и возвращает соответствующую «битовую маску», содержащую столько же 1 бит, сколько вводится.

Я начал так:

/** Computes a bitmaks */
private static long mask(final int bitsPerValue) {
    return (1L << bitsPerValue) - 1L;
}

Но понял, что это дает неправильное значение для 64:

(1L << 64) - 1L == 1L - 1L == 0

Теперь у меня есть это:

/** Computes a bitmaks */
private static long mask(final int bitsPerValue) {
    return (bitsPerValue == 64) ? -1 : ((1L << bitsPerValue) - 1L);
}

Это довольно некрасиво. А условные выражения могут изменить поток управления, поэтому они стоят дороже, чем простые арифметические операции. Я мог бы просто предварительно вычислить маски и поместить их в статический массив, но доступ к массиву также дороже, чем простые арифметические операции, возможно, даже дороже, чем условные.

Есть ли разумный способ написать это без условия? Этот код будет выполняться миллионы раз в секунду, поэтому он должен быть быстрым.

Answer 1

Вот способ сделать это без условий:

private static long mask(final int bitsPerValue) {
    return ((1L << bitsPerValue) - (bitsPerValue >> 6)) - 1L;
}

В Java 1L << bitsPerValue использует только шесть младших битов из bitsPerValue, что означает, что вызов вашей исходной функции с помощью bitsPerValue=64 аналогичен вызову с помощью bitsPerValue=0. Версия, которую я представляю выше, заботится об этом: когда bitsPerValue=64, выражение уменьшается до

(1L - 1L) - 1L == -1L

Теперь, если вы действительно будете называть это "миллионы раз в секунду", я думаю, что лучшая стратегия - это тест всех вариантов кода, включая один с условными и один с таблицей поиска.

Answer 2

Я пытался:

long value = 0xffffffffffffffffl >>> (64 - i); // that's ef ef ef... el.

, но, похоже, это создает проблему при i = 0. В моем схватывании с Java больше нет беззнаковых целых.Вышесказанное работает в ц.Возможно, вышеприведенное будет работать в Java 7, учитывая, что «значение» не имеет знака.

Однако, поскольку вам не нужен ноль, вышеописанное будет работать для вас нормально, то есть значения от 1 до 64.

Answer 3

ИМХО, добавление требования для 65-битного значения недостаточно. Я бы просто использовал операцию ИЛИ для генерации значения, это не должно занимать много времени. Как это:

private static long mask(final int bitsPerValue) {
  long mask = 1;
  long value = 0;
  for (int i=0; i<bitsPerValue; i++ ) {
    value = value | mask;
    mask = mask << 1;
  }
  return value;
}

Я вижу, что вы не хотите использовать статические массивы, но это был бы самый быстрый способ, который просто использует 64 * 8 байтов памяти. Более того, я не думаю, что легко достичь небольшого объема памяти и достаточно хорошей скорости одновременно . Так что, на всякий случай, самый быстрый подход будет:

long valarray[] = new long[64];

private static long[] generateValues() {
  long mask = 1;
  long value = 0;
  for (int i=0; i<64; i++ ) {
    value = value | mask;
    mask = mask << 1;

    valarray[i] = value;
  }
  return valarray;
}

private static long[] mask(final int bitsPerValue) {
  return valarray[bitsPerValue-1];
}

Другой возможный подход - использовать BigInteger для новейшего 64-битного случая. Но я не думаю, что это быстро и не безобразно.