logical - java<=

Cambiando un Java BitSet

Question

Estoy usando un java.util.BitSet para almacenar un vector denso de bits.

Quiero implementar una operación que desplace los bits a la derecha en 1, de forma análoga a >>> en ints.

¿Hay una función de biblioteca que desplaza BitSet s?

Si no, ¿hay una manera mejor que la de abajo?

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

Con el java SE8, se puede lograr de manera más concisa:

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

Estaba tratando de averiguar cómo usar LongBuffer para hacerlo, pero no conseguí que funcionara. Con suerte, alguien que esté familiarizado con la programación de bajo nivel puede señalar una solución.

¡¡¡Gracias por adelantado!!!

Answer 2

Encuentre este bloque de código donde BitSet está "a la izquierda"

/**
 * 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

Eso debería hacer el truco:

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

Le dará un conjunto de bits igual al original, pero sin el bit más bajo.

EDITAR:

Para generalizar esto a n bits,

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

Answer 4

Estas funciones imitan a los operadores << y >>>, respectivamente.

/**
 * 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

Para lograr un mejor rendimiento, puede extender la implementación de java.util.BitSet y evitar la copia innecesaria de matrices. Aquí está la implementación (básicamente he reutilizado la implementación de Jeff Piersol):

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);
            }
        }
    }
}

Answer 6

Puede utilizar BigInteger lugar de BitSet . BigInteger ya tiene ShiftRight y ShiftLeft.

Answer 7

Puede ver el BitSet toLongArray y el valueOf(long[]) .
Básicamente, obtenga la matriz long , cambie la s long y construya un nuevo BitSet partir de la matriz BitSet .

Answer 8

Una alternativa que probablemente sea más eficiente sería trabajar con el subyacente largo [].

Utilice bitset.toLongArray() para obtener los datos subyacentes. Cambie esos largos en consecuencia, luego cree un nuevo BitSet a través de BitSet.valueOf(long[]) Deberá tener mucho cuidado al cambiar los largos subyacentes, ya que tendrá que tomar el bit de orden inferior y cambiarlo al bit de orden superior en el siguiente largo en la matriz.

Esto debería permitirle usar las operaciones de cambio de bits nativas en su procesador para mover 64 bits a la vez, en lugar de iterar a través de cada uno por separado.

EDIT: Basado en el comentario de Louis Wasserman. Esto solo está disponible en Java 1.7 API. No me di cuenta de eso cuando lo escribí.