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

Question

Я хочу написать функцию, которая принимает целое число от 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

Я старался:

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

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

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

Answer 2

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

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 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-битного случая. Но я не думаю, что это быстро и не безобразно.