Сдвиг Java BitSet

Question

Я использую java.util.BitSet для хранения плотного вектора битов.

Я хочу реализовать операцию, которая сдвигает биты вправо на 1, аналогично >>> в целых числах.

Есть ли библиотечная функция, которая сдвигает BitSet с?

Если нет, есть ли лучший способ, чем приведенный ниже?

public static void logicalRightShift(BitSet bs) {
  for (int i = 0; (i = bs.nextSetBit(i)) >= 0;) {
    // i is the first bit in a run of set bits.

    // Set any bit to the left of the run.
    if (i != 0) { bs.set(i - 1); }

    // Now i is the index of the bit after the end of the run.
    i = bs.nextClearBit(i);  // nextClearBit never returns -1.
    // Clear the last bit of the run.
    bs.clear(i - 1);

    // 0000111100000...
    //     a   b
    // i starts off the loop at a, and ends the loop at b.
    // The mutations change the run to
    // 0001111000000...
  }
}

Answer 1

Это должно сработать:

BitSet shifted = bs.get(1, bs.length());

Это даст вам набор битов, равный оригинальному, но без самого младшего бита.

РЕДАКТИРОВАТЬ:

Чтобы обобщить это до n битов,

BitSet shifted = bs.get(n, Math.max(n, bs.length()));

Answer 2

Пожалуйста, найдите этот блок кода, где BitSet «сдвинут влево»

/**
 * Shift the BitSet to left.<br>
 * For example : 0b10010 (=18) => 0b100100 (=36) (equivalent to multiplicate by 2)
 * @param bitSet
 * @return shifted bitSet
 */
public static BitSet leftShiftBitSet(BitSet bitSet) {
    final long maskOfCarry = 0x8000000000000000L;
    long[] aLong = bitSet.toLongArray();

    boolean carry = false;
    for (int i = 0; i < aLong.length; ++i) {
        if (carry) {
            carry = ((aLong[i] & maskOfCarry) != 0);
            aLong[i] <<= 1;
            ++aLong[i];
        } else {
            carry = ((aLong[i] & maskOfCarry) != 0);
            aLong[i] <<= 1;
        }
    }

    if (carry) {
        long[] tmp = new long[aLong.length + 1];
        System.arraycopy(aLong, 0, tmp, 0, aLong.length);
        ++tmp[aLong.length];
        aLong = tmp;
    }

    return BitSet.valueOf(aLong);
}

Answer 3

Альтернативой, которая, вероятно, более эффективна, будет работа с базовым long [].

Используйте bitset.toLongArray() для получения базовых данных.Сдвиньте эти длинные соответственно, затем создайте новый BitSet с помощью BitSet.valueOf(long[]). Вы должны быть очень осторожны, перемещая лежащие в основе длинные, так как вам придется взять бит младшего разряда и сдвинуть его в бит старшего разряда на следующем длинноммассив.

Этот должен позволять вам использовать собственные операции сдвига бит на вашем процессоре для перемещения 64 бит за раз, в отличие от итерации каждой из них в отдельности.

РЕДАКТИРОВАТЬ: на основе комментария Луи Вассермана.Это доступно только в Java 1.7 API.Не понял, когда я это написал.

Answer 4

Эти функции имитируют операторы << и >>> соответственно.

/**
 * Shifts a BitSet n digits to the left. For example, 0b0110101 with n=2 becomes 0b10101.
 *
 * @param bits
 * @param n the shift distance.
 * @return
 */
public static BitSet shiftLeft(BitSet bits, int n) {
    if (n < 0)
        throw new IllegalArgumentException("'n' must be >= 0");
    if (n >= 64)
        throw new IllegalArgumentException("'n' must be < 64");

    long[] words = bits.toLongArray();

    // Do the shift
    for (int i = 0; i < words.length - 1; i++) {
        words[i] >>>= n; // Shift current word
        words[i] |= words[i + 1] << (64 - n); // Do the carry
    }
    words[words.length - 1] >>>= n; // shift [words.length-1] separately, since no carry

    return BitSet.valueOf(words);
}

/**
 * Shifts a BitSet n digits to the right. For example, 0b0110101 with n=2 becomes 0b000110101.
 *
 * @param bits
 * @param n the shift distance.
 * @return
 */
public static BitSet shiftRight(BitSet bits, int n) {
    if (n < 0)
        throw new IllegalArgumentException("'n' must be >= 0");
    if (n >= 64)
        throw new IllegalArgumentException("'n' must be < 64");

    long[] words = bits.toLongArray();

    // Expand array if there will be carry bits
    if (words[words.length - 1] >>> (64 - n) > 0) {
        long[] tmp = new long[words.length + 1];
        System.arraycopy(words, 0, tmp, 0, words.length);
        words = tmp;
    }

    // Do the shift
    for (int i = words.length - 1; i > 0; i--) {
        words[i] <<= n; // Shift current word
        words[i] |= words[i - 1] >>> (64 - n); // Do the carry
    }
    words[0] <<= n; // shift [0] separately, since no carry

    return BitSet.valueOf(words);
}

Answer 5

Вы можете использовать BigInteger вместо BitSet. BigInteger уже имеет ShiftRight и ShiftLeft.

Answer 6

Вы можете посмотреть на BitSet toLongArray и valueOf(long[]).
Получите массив long, сдвиньте long s и создайте новый BitSet из смещенного массива.

Answer 7

С java SE8 это может быть достигнуто более кратким способом:

BitSet b = new BitSet();
b.set(1, 3);
BitSet shifted = BitSet.valueOf(Arrays.stream(
       b.toLongArray()).map(v -> v << 1).toArray());

Я пытался выяснить, как использовать LongBuffer для этого, но не совсем заставил его работать. Надеюсь, кто-то, кто знаком с программированием низкого уровня, может указать решение.

Спасибо заранее !!!

Answer 8

Для повышения производительности вы можете расширить реализацию java.util.BitSet и избежать ненужного копирования массива.Вот реализация (я в основном повторно использовал реализацию Джеффа Пирсола):

package first.specific.structure;

import java.lang.reflect.Field;
import java.util.BitSet;

public class BitSetMut extends BitSet {

    private long[] words;
    private static Field wordsField;

    static {
        try {
            wordsField = BitSet.class.getDeclaredField("words");
            wordsField.setAccessible(true);
        } catch (NoSuchFieldException e) {
            throw new IllegalStateException(e);
        }
    }

    public BitSetMut(final int regLength) {
        super(regLength);
        try {
            words = (long[]) wordsField.get(this);
        } catch (IllegalAccessException e) {
            throw new IllegalStateException(e);
        }
    }

    public void shiftRight(int n) {
        if (n < 0)
            throw new IllegalArgumentException("'n' must be >= 0");
        if (n >= 64)
            throw new IllegalArgumentException("'n' must be < 64");

        if (words.length > 0) {
            ensureCapacity(n);

            // Do the shift
            for (int i = words.length - 1; i > 0; i--) {
                words[i] <<= n; // Shift current word
                words[i] |= words[i - 1] >>> (64 - n); // Do the carry
            }
            words[0] <<= n; // shift [0] separately, since no carry
            // recalculateWordInUse() is unnecessary
        }
    }

    private void ensureCapacity(final int n) {
        if (words[words.length - 1] >>> n > 0) {
            long[] tmp = new long[words.length + 3];
            System.arraycopy(words, 0, tmp, 0, words.length);
            words = tmp;
            try {
                wordsField.set(this, tmp);
            } catch (IllegalAccessException e) {
                throw new IllegalStateException(e);
            }
        }
    }
}