转移Java BitSet

Question

我用a java.util.BitSet来存储密集的位向量.

我想实现一个将位向右移1的操作,类似于>>>on int.

有一个库函数可以改变BitSets吗？

如果没有,是否有比下面更好的方法？

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

它会给你一个等于orginial的bitset,但没有最低位.

编辑:

将此概括为n位,

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

Answer 2

可能更有效的替代方案是使用底层的long [].

使用bitset.toLongArray()得到的基础数据.相应地移动那些长点,然后创建一个新的BitSet BitSet.valueOf(long[])你需要非常小心地移动底层长点,因为你必须取低位并将其移入阵列中下一个长位的高位.

这应该允许您使用处理器本机的位移操作一次移动64位,而不是分别迭代每一位.

编辑:根据Louis Wasserman的评论.这仅适用于Java 1.7 API.当我写它时没有意识到.

Answer 3

请找到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 4

您可以使用BigInteger代替BitSet. BigInteger已经有 ShiftRight 和 ShiftLeft。