Блог

Главная - Вопросы по программированию - Как сдвигать биты влево и вправо в BitSet JAVA?

Как сдвигать биты влево и вправо в BitSet JAVA?

#java #bit-manipulation #bit-shift #bitset

#java #манипулирование битами #сдвиг битов #набор битов

Вопрос:

У меня есть набор битов с числом битов 100000. Я хочу максимально эффективно сдвигать его вправо и влево. Я предполагаю, что в классе BitSet нет функции для сдвига битов, поэтому я попытался преобразовать их в длинный массив, используя toLongArray() , но, как и ожидалось, это дает переполнение.

Временное решение, которое я нашел, состояло в том, чтобы преобразовать bitset в BigInteger, а затем сдвинуть BigInteger, а затем преобразовать BigInteger обратно в bitset, но это очень медленно.

Итак, мои вопросы:

  1. Есть ли лучший способ сдвинуть набор битов (под сдвигом я подразумеваю сдвиг влево и вправо)
  2. Когда я преобразую набор битов с числом битов больше 64 в длинный массив, я получаю отрицательные значения в массиве. Почему вообще существует функция toLongArray() , когда BitSet может представлять только биты из 1 числа. Пожалуйста, поправьте меня, если я ошибаюсь.

Ниже приведен код для использования BigInteger.

 public static BitSet toBitSet(BigInteger val) {
  if(val.signum() < 0)
  throw new IllegalArgumentException("Negative value: "   val);
  return BitSet.valueOf(reverse(val.toByteArray()));
}
static byte[] reverse(byte[] bytes) {
  for(int i = 0; i < bytes.length/2; i  ) {
    byte temp = bytes[i];
    bytes[i] = bytes[bytes.length-i-1];
    bytes[bytes.length-i-1] = temp;
  }
  return bytes;
}
public static BigInteger toBigInteger(BitSet val) {
  return new BigInteger(1, reverse(val.toByteArray()));
}
public static BitSet shiftLeft(BitSet bits, int n) {
  BigInteger temp= toBigInteger(bits);
  temp= temp.shiftLeft(n);
  return toBitSet(temp);
}

PS: Все ответы, которые я нашел, были для количества бит <= 64

Комментарии:

1. Если вам это нужно как можно более эффективно, вы можете List<Boolean> вместо этого использовать a , например, a LinkedList<Boolean> должна быть наиболее эффективной структурой данных для сдвига, поскольку вы можете выполнять операции сдвига, вставляя / удаляя элементы O(1) .

2. @Robert да, но я также хочу выполнять такие операции, как и, или, xor. Bitset поддерживает для них inbulit, вот почему я выбрал его.

3. Как вы думаете, почему получение отрицательных длинных значений является проблемой? Если вы используете все 64 бита long, возможны отрицательные значения, вам просто нужно использовать long на битовом уровне, не пытайтесь интерпретировать его как значение. Кстати: глядя на реализацию BitSet, вы можете видеть, что внутренне он используется long[] для хранения битов. Следовательно, вызывая toLongArray() , вы просто получаете копию внутреннего представления.

4. @Роберт. Это была проблема, потому что я думал, что должно быть возвращено только одно значение. Но, как вы сказали, внутренняя реализация использует long[] then, я думаю, имеет смысл получить массив, заполненный значениями -ve в случае переполнения.

Ответ №1:

Когда я преобразую набор битов с числом битов больше 64 в длинный массив, я получаю отрицательные значения в массиве.

Отрицательные элементы в порядке, это просто следствие использования всех 64 бит a long , включая знаковый бит. Это не имеет значения, если вы это ожидаете. В принципе, это выглядит странно только при печати с подписанной интерпретацией, в остальном это неплохо.

итак, я попытался преобразовать их в длинный массив, используя toLongArray() , но, как и ожидалось, это дает переполнение.

Однако это разумная стратегия реализации, так что давайте это исправим. Я предполагаю, что вы сдвинули каждый элемент по отдельности, не обрабатывая «перенос». Что должно произойти для сдвига влево, так это то, что верхний бит (ы) элемента помещается в нижний бит (ы) следующего элемента. Для сдвига вправо все наоборот. Например, n до 63 (не тестировалось)

 static BitSet shiftRight(BitSet bits, int n) {
    long[] raw = bits.toLongArray();
    long carry = 0;
    for (int i = raw.length - 1; i >= 0; i--) {
        long newcarry = raw[i] << -n;
        raw[i] = (raw[i] >>> n) | carry;
        carry = newcarry;
    }
    return BitSet.valueOf(raw);
}

Если n может быть 64 или больше, возникает дополнительная сложность перемещения целых элементов в разные позиции.

Сдвиг влево имеет дополнительную сложность, заключающуюся в том, что результирующий набор может быть больше (не с большим количеством установленных битов, но физически больше, что требует более длинного массива), чем входные данные.